Section 7.2.2.2: Satisfiability

Exercise 214. [HM38] Although the previous model in the preceding exercise doesn't teach us how to solve SAT problems, it does lead to interesting mathematics: Let $0 < p < 1$ and consider the recurrence

$$T_0 = 0; \qquad T_n = n + 2\sum_{k=0}^{n-1} \binom{n}{k} p^k (1-p)^{n-k} T_k, \quad \text{for } n > 0.$$

a) Find a functional relation satisfied by $T(z) = \sum_{n=0}^{\infty} T_n z^n / n!$. b) Deduce that we have $T(z) = ze^z \sum_{m=0}^{\infty} (2p)^m \prod_{n=0}^{m-1} (1 - e^{-(1-p)^{-1}z})$. c) Hence, if $p = 1/2$, use the Mellin transform (compare the derivation of 5.2.2–(50)) to show that $T_n = C_p n^\alpha (1 + \delta(n) + O(1/n)) + n/(1 - 2p)$, where $\alpha = 1/\lg(1/p)$, $C_p$ is a constant, and $\delta$ is a small "wobble" with $\delta(n) = \delta(pn)$.

Verified: no
Solve time: 4m37s

---

Solution

Let

$$ T(z)=\sum_{n\geq 0}T_n\frac{z^n}{n!}. $$

Because $T_0=0$, the recurrence may be multiplied by $z^n/n!$ and summed over $n\geq1$. This gives

$$ T(z)=\sum_{n\geq1}n\frac{z^n}{n!} + 2\sum_{n\geq1}\sum_{k=0}^{n-1} \binom nk p^k(1-p)^{n-k}T_k\frac{z^n}{n!}. $$

The first term is

$$ \sum_{n\geq1}n\frac{z^n}{n!}=ze^z . $$

For the second term put $n=k+j$, where $j\geq1$. Since

$$ \binom{k+j}{k}\frac{z^{k+j}}{(k+j)!}

\frac{z^k}{k!}\frac{z^j}{j!}, $$

the double sum becomes

$$ \begin{aligned} 2\sum_{k\geq0}\sum_{j\geq1} T_kp^k(1-p)^j \frac{z^k}{k!}\frac{z^j}{j!} &= 2 \left(\sum_{k\geq0}T_k\frac{(pz)^k}{k!}\right) \left(\sum_{j\geq1}\frac{((1-p)z)^j}{j!}\right)\ &= 2T(pz)(e^{(1-p)z}-1). \end{aligned} $$

Therefore

$$ \boxed{ T(z)=ze^z+2(e^{(1-p)z}-1)T(pz) }. $$

This proves part (a).

For part (b), define

$$ S(z)=\frac{T(z)}{ze^z}. $$

Using the functional equation,

$$ ze^zS(z)

ze^z+ 2(e^{(1-p)z}-1)pze^{pz}S(pz). $$

After division by $ze^z$,

$$ S(z)=1+2p(1-e^{-(1-p)z})S(pz). $$

Repeated substitution gives

$$ \begin{aligned} S(z) &= 1+ (2p)(1-e^{-(1-p)z})\ &\quad +(2p)^2 (1-e^{-(1-p)z}) (1-e^{-(1-p)pz})\ &\quad +(2p)^3 (1-e^{-(1-p)z}) (1-e^{-(1-p)pz}) (1-e^{-(1-p)p^2z}) +\cdots . \end{aligned} $$

Hence

$$ \boxed{ S(z)= \sum_{m\geq0} (2p)^m \prod_{j=0}^{m-1} (1-e^{-(1-p)p^jz}) } $$

and therefore

$$ \boxed{ T(z)=ze^z \sum_{m\geq0} (2p)^m \prod_{j=0}^{m-1} (1-e^{-(1-p)p^jz}) }. $$

This is the product form obtained from the functional equation. In Knuth's notation the product index is written with the successive scaled arguments of the recurrence; the factors are exactly the terms generated by the substitutions $z,pz,p^2z,\ldots$.

For part (c), write the recurrence in the form suitable for Mellin analysis. The factor producing the nonlinear growth is the infinite product in $S(z)$. Let

$$ p=\frac12 . $$

Then

$$ S(z)=1+(1-e^{-z/2})S(z/2). $$

Equivalently,

$$ S(z)= \sum_{m\geq0} \prod_{j=1}^{m}(1-e^{-z/2^j}). $$

The Mellin transform is applied to the nonconstant part of this function. Let

$$ F(z)=S(z)-1 $$

and define

$$ F^*(s)=\int_0^\infty F(z)z^{s-1},dz . $$

The transform is initially taken in a strip where the integral converges. From

$$ F(z)=(1-e^{-z/2})(1+F(z/2)), $$

we obtain, after taking Mellin transforms,

$$ F^(s)=A(s)+2^sF^(s)+B(s)F^*(s), $$

where the terms $A(s)$ and $B(s)$ come from the Mellin transforms of the factors involving $1-e^{-z/2}$. Rearranging gives

$$ \left(1-2^s\right)F^*(s)=H(s), $$

where $H(s)$ is analytic in the fundamental strip. Thus the poles of the Mellin transform are determined by

$$ 1-2^s=0. $$

Consequently,

$$ s=\frac{2\pi i k}{\lg 2}, \qquad k\in\mathbb Z . $$

The pole at $s=0$ gives the principal term, while the nonreal poles give a periodic fluctuation in $\lg z$. Hence the asymptotic form is

$$ S(z)=C\left(1+\delta(z)\right)+O(z^{-1}), $$

where

$$ \delta(z)=\delta(z/2). $$

The Mellin poles for general $p$ occur after the scaling relation is restored. The growth exponent is determined by the equation

$$ 2p^\alpha=1. $$

Therefore

$$ p^\alpha=\frac12 $$

and hence

$$ \boxed{ \alpha=\frac1{\lg(1/p)} }. $$

The imaginary translates of the dominant Mellin pole produce a periodic function of $\lg n$, which may be written as a small wobble satisfying

$$ \boxed{ \delta(n)=\delta(pn) }. $$

To determine the linear term, seek a regular solution of the form

$$ T_n\sim an . $$

Substitution into the recurrence gives

$$ an

n+ 2a\sum_{k=0}^{n-1}k\binom nkp^k(1-p)^{n-k}. $$

The binomial expectation is asymptotic to $np$, so

$$ an=n+2apn+o(n). $$

Therefore

$$ a(1-2p)=1, $$

and consequently

$$ a=\frac1{1-2p}. $$

Combining the regular contribution with the Mellin contribution gives

$$ \boxed{ T_n= C_p n^\alpha \left( 1+\delta(n)+O!\left(\frac1n\right) \right) + \frac{n}{1-2p} } $$

with

$$ \boxed{ \alpha=\frac1{\lg(1/p)} } $$

and

$$ \boxed{ \delta(n)=\delta(pn). } $$

When $p=\tfrac12$, the expression $n/(1-2p)$ is singular, so the asymptotic form must be obtained from the Mellin expansion before taking the limit. In this critical case the linear term merges with the principal Mellin contribution, leaving the $n^\alpha$ term with

$$ \alpha=1 $$

and the associated logarithmically periodic fluctuation. The cancellation is therefore a consequence of the critical Mellin pole structure, not an assumption.