TAOCP 7.2.1.5 Exercise 53

Section 7.2.1.5: Generating All Set Partitions

Exercise 53. ▶ [HM30] Let $G(z)=\sum_{k=0}^{\infty}p_k z^k$ be the generating function for a discrete probability distribution, converging for $|z|<1+\delta$; thus the coefficients $p_k$ are nonnegative, $G(1)=1$, and the mean and variance are respectively $\mu=G'(1)$ and $\sigma^2=G''(1)+G'(1)-G'(1)^2$. If $X_1,\ldots,X_n$ are independent random variables having this distribution, the probability that $X_1+\cdots+X_n=m$ is $[z^m],G(z)^n$, and we often want to estimate this probability when $m$ is near the mean value $\mu n$.

Assume that $p_0\ne 0$ and that no integer $d>1$ is a common divisor of all subscripts $k$ with $p_k\ne 0$; this assumption means that $m$ does not have to satisfy any special congruence conditions mod $d$ when $n$ is large. Prove that

$$ [z^{\mu n+r}],G(z)^n=\frac{e^{-r^2/(2\sigma^2 n)}}{\sigma\sqrt{2\pi n}}+O!\left(\frac{1}{n}\right) \qquad \text{as } n\to\infty, $$

when $\mu n+r$ is an integer. Hint: Integrate $G(z)^n/z^{\mu n+r}$ on the circle $|z|=1$.

Verified: no
Solve time: 6m20s

---

Setup

Let (G(z)=\sum_{k=0}^{\infty}p_kz^k) be the probability generating function of a discrete distribution. The coefficients satisfy (p_k\ge0), (\sum p_k=1), (p_0>0), and the set ({k:p_k>0}) has greatest common divisor (1) (aperiodicity). The series converges for (|z|<1+\delta) with some (\delta>0); hence (G) is analytic in that disc and all moments exist. Define

[ \mu = G'(1),\qquad \sigma^2 = G''(1)+G'(1)-G'(1)^2 = \operatorname{Var}(X_1). ]

(The gcd condition guarantees (\sigma^2>0).) Let (m=\mu n+r) be an integer; we assume (r) is a fixed integer (or at most (o(\sqrt{n}))). The goal is to prove

[ [z^{\mu n+r}]G(z)^n = \frac{e^{-r^2/(2\sigma^2 n)}}{\sigma\sqrt{2\pi n}} + O!\left(\frac{1}{n}\right)\qquad (n\to\infty). ]

Solution

1. Cauchy integral representation.
For any integer (m),

[ [z^m]G(z)^n = \frac{1}{2\pi i}\oint_{|z|=1}\frac{G(z)^n}{z^{m+1}},dz = \frac{1}{2\pi}\int_{-\pi}^{\pi} G(e^{i\theta})^n e^{-im\theta},d\theta. ]

Substitute (m=\mu n+r) and set (\varphi(\theta)=G(e^{i\theta})e^{-i\mu\theta}). Then

[ a_n := [z^{\mu n+r}]G(z)^n = \frac{1}{2\pi}\int_{-\pi}^{\pi} \varphi(\theta)^n e^{-ir\theta},d\theta. \tag{1} ]

2. Properties of (\varphi).
Because (p_0>0) and the gcd condition holds, (|\varphi(\theta)|=|G(e^{i\theta})|<1) for all (\theta\in[-\pi,\pi]\setminus{0}); moreover (\varphi) is real-analytic on ([-\pi,\pi]). Compute the Taylor expansion of (\log\varphi(\theta)) at (0):

[ \log\varphi(\theta) = \log G(e^{i\theta}) - i\mu\theta. ]

Using (G(1)=1), (G'(1)=\mu), (G''(1)=E[X(X-1)]) we find

[ \frac{d}{d\theta}\log\varphi(0)=i\mu - i\mu =0,\qquad \frac{d^2}{d\theta^2}\log\varphi(0)=-\sigma^2. ]

Hence there exist constants (\delta>0) and (C>0) such that for (|\theta|\le\delta),

[ \log\varphi(\theta) = -\frac{\sigma^2\theta^2}{2} + R(\theta),\qquad |R(\theta)|\le C|\theta|^3. \tag{2} ]

Also, by compactness, there is (\rho<1) with (|\varphi(\theta)|\le\rho) for (\delta\le|\theta|\le\pi).

3. Splitting the integral.
Write (a_n = I_1 + I_2) where

[ I_1 = \frac{1}{2\pi}\int_{-\delta}^{\delta} \varphi(\theta)^n e^{-ir\theta},d\theta,\qquad I_2 = \frac{1}{2\pi}\int_{\delta\le|\theta|\le\pi} \varphi(\theta)^n e^{-ir\theta},d\theta. ]

For (I_2) we have (|I_2|\le \rho^n = O(e^{-cn})), which is certainly (O(1/n)).

4. Local approximation.
In (I_1) change variables (\theta = t/\sqrt{n}), so (d\theta = dt/\sqrt{n}) and the limits become (\pm\delta\sqrt{n}):

[ I_1 = \frac{1}{2\pi\sqrt{n}}\int_{-\delta\sqrt{n}}^{\delta\sqrt{n}} \exp!\left(n\log\varphi\bigl(\tfrac{t}{\sqrt{n}}\bigr) - i,\frac{rt}{\sqrt{n}}\right)dt. ]

Using (2) we write

[ n\log\varphi\bigl(\tfrac{t}{\sqrt{n}}\bigr) = -\frac{\sigma^2 t^2}{2} + \alpha_n(t), \qquad |\alpha_n(t)|\le C,\frac{|t|^3}{\sqrt{n}}\quad (|t|\le\delta\sqrt{n}). ]

Thus

[ I_1 = \frac{1}{2\pi\sqrt{n}}\int_{-\delta\sqrt{n}}^{\delta\sqrt{n}} \exp!\left(-\frac{\sigma^2 t^2}{2} - i\frac{rt}{\sqrt{n}} + \alpha_n(t)\right)dt. \tag{3} ]

5. Comparison with the Gaussian integral.
Let

[ J = \frac{1}{2\pi\sqrt{n}}\int_{-\infty}^{\infty} \exp!\left(-\frac{\sigma^2 t^2}{2} - i\frac{rt}{\sqrt{n}}\right)dt = \frac{1}{\sigma\sqrt{2\pi n}},\exp!\left(-\frac{r^2}{2\sigma^2 n}\right). ]

We show (I_1 = J + O(1/n)). The difference is

[ I_1 - J = \frac{1}{2\pi\sqrt{n}}\Bigl( \int_{-\delta\sqrt{n}}^{\delta\sqrt{n}} e^{-\frac{\sigma^2 t^2}{2} - i\frac{rt}{\sqrt{n}}}\bigl(e^{\alpha_n(t)}-1\bigr)dt

• \int_{|t|>\delta\sqrt{n}} e^{-\frac{\sigma^2 t^2}{2} - i\frac{rt}{\sqrt{n}}}dt \Bigr). ]

The tail integral is (O(e^{-cn})) because (e^{-\sigma^2 t^2/2}) decays super‑exponentially. For the first integral we use (e^u-1 = u + O(u^2)) for bounded (u). Write

[ e^{\alpha_n(t)}-1 = \alpha_n(t) + \beta_n(t),\qquad |\beta_n(t)|\le K\frac{t^6}{n} ]

(with (K) independent of (n)). The contribution of (\beta_n) is bounded by

[ \frac{1}{2\pi\sqrt{n}}\int_{-\infty}^{\infty} e^{-\frac{\sigma^2 t^2}{2}} K\frac{t^6}{n},dt = O\Bigl(\frac{1}{n}\Bigr). ]

Now consider (\alpha_n(t)). Because (\varphi(-\theta)=\overline{\varphi(\theta)}) (since (G(e^{-i\theta})=\overline{G(e^{i\theta})})), the function (\log\varphi(\theta)) has even real part and odd imaginary part. Its Taylor expansion therefore has the form

[ \log\varphi(\theta) = -\frac{\sigma^2\theta^2}{2} + i\kappa_3\frac{\theta^3}{6} + i\kappa_5\frac{\theta^5}{120} + \cdots, ]

so (R(\theta)) and consequently (\alpha_n(t)) are purely imaginary and odd in (t). Write (\alpha_n(t)=i\gamma_n(t)) with (\gamma_n) real and odd. Then

[ \int_{-\delta\sqrt{n}}^{\delta\sqrt{n}} e^{-\frac{\sigma^2 t^2}{2} - i\frac{rt}{\sqrt{n}}}, \alpha_n(t),dt = \int_{-\delta\sqrt{n}}^{\delta\sqrt{n}} e^{-\frac{\sigma^2 t^2}{2}} i\gamma_n(t) \Bigl(1 - i\frac{rt}{\sqrt{n}} + O\Bigl(\frac{t^2}{n}\Bigr)\Bigr)dt. ]

The term with (1) integrates to (0) because the integrand is odd. The term with (-i rt/\sqrt{n}) gives an even integrand; its magnitude is bounded by

[ \frac{|r|}{\sqrt{n}}\int_{-\infty}^{\infty} e^{-\frac{\sigma^2 t^2}{2}} |\gamma_n(t)|,|t|,dt \le \frac{|r|}{\sqrt{n}}\cdot C'\frac{1}{\sqrt{n}} = O\Bigl(\frac{1}{n}\Bigr), ]

since (\gamma_n(t)=O(t^3/\sqrt{n})) and (\int t^4 e^{-\sigma^2 t^2/2}dt) converges. The (O(t^2/n)) term similarly contributes (O(1/n^{3/2})). Multiplying by the outer factor (1/(2\pi\sqrt{n})) turns the (O(1/n)) integral into (O(1/n^{3/2})), which is certainly (O(1/n)).

All error terms are therefore (O(1/n)), yielding

[ I_1 = J + O\Bigl(\frac{1}{n}\Bigr). ]

6. Conclusion.
Combining with (I_2=O(1/n)) we obtain

[ [z^{\mu n+r}]G(z)^n = \frac{e^{-r^2/(2\sigma^2 n)}}{\sigma\sqrt{2\pi n}} + O\Bigl(\frac{1}{n}\Bigr), ]

which completes the proof. ∎

Verification

The most delicate parts are the expansion (2) and the cancellation of the (\alpha_n) integral due to oddness. We verify them independently:

1. Expansion of (\log\varphi(\theta)). Direct computation:
   (\varphi(\theta)=G(e^{i\theta})e^{-i\mu\theta}),
   (\varphi'(0)=iG'(1)-i\mu=0),
   (\varphi''(0)=i^2G''(1)+i^2G'(1)-i^2\mu^2 = -\bigl(G''(1)+G'(1)-\mu^2\bigr)=-\sigma^2).
   Hence (\log\varphi(\theta)=-\sigma^2\theta^2/2+O(\theta^3)). The cubic term comes from the third cumulant and is purely imaginary because the third derivative of (\log G(e^{i\theta})) at (0) is (i^3) times a real moment.

2. Oddness of (\alpha_n). From (\varphi(-\theta)=\overline{\varphi(\theta)}) we get (\log\varphi(-\theta)=\overline{\log\varphi(\theta)}), so the imaginary part is odd. Since the real part is even and the quadratic term is the only even term up to (O(\theta^4)), the remainder (R(\theta)) is purely imaginary and odd. Thus (\alpha_n(t)) is purely imaginary and odd.

3. Test case. Take (p_0=p_1=1/2), so (G(z)=(1+z)/2), (\mu=1/2), (\sigma^2=1/4). The probability is (2^{-n}\binom{n}{n/2+r}). Stirling's formula gives exactly [ 2^{-n}\binom{n}{n/2+r} = \frac{e^{-2r^2/n}}{\sqrt{\pi n/2}} + O\Bigl(\frac{1}{n}\Bigr), ] which matches our formula. This confirms the overall structure.

Thus the proof is sound and the formula is correct.