TAOCP 5.1.3 Exercise 28
The expected length \(z_m\) of the \(m\)th ascending run in a random infinite sequence of distinct numbers is \[ z_m = \sum_{k=m}^{\infty} \frac{1}{k!
Exercise 28. [HM35] Find the asymptotic value of the numbers $z_m$ in Fig. 3 as $m \to \infty$, and prove that $\sum_{m \ge 0} (z_m - z_{m+1})^2$ converges.
Verified: yes
Solve time: 1h40m
The expected length (z_m) of the (m)th ascending run in a random infinite sequence of distinct numbers is [ z_m = \sum_{k=m}^{\infty} \frac{1}{k!}\left\langle k \atop m-1 \right\rangle,\qquad m\ge 1, ] where (\left\langle n \atop k \right\rangle) are the Eulerian numbers (see Eq.,(1) and the discussion following Eq.,(22) in the text). Define the generating function [ Z(x) = \sum_{m=1}^{\infty} z_m x^m. ] Interchanging the order of summation gives [ Z(x) = \sum_{m=1}^{\infty}\sum_{k=m}^{\infty} \frac{1}{k!}\left\langle k \atop m-1 \right\rangle x^m = \sum_{k=1}^{\infty} \frac{1}{k!} \sum_{m=1}^{k} \left\langle k \atop m-1 \right\rangle x^m = x\sum_{k=1}^{\infty} \frac{A_k(x)}{k!}, ] where (A_k(x) = \sum_{j=0}^{k-1}\left\langle k \atop j \right\rangle x^j) is the Eulerian polynomial ((A_0(x)=1)). The super generating function of the text, Eq.,(20), states [ \sum_{k=0}^{\infty} \frac{A_k(z)}{k!},t^k = \frac{1-z}{e^{(z-1)t}-z}. ] Setting (t=1) and subtracting the (k=0) term yields [ \sum_{k=1}^{\infty} \frac{A_k(x)}{k!} = \frac{1-x}{e^{x-1}-x} - 1, ] so that [ Z(x) = x\left(\frac{1-x}{e^{x-1}-x} - 1\right). \tag{1} ]
The singularities of (Z(x)) are the zeros of (e^{x-1}-x). We prove that the only zero with (|x|\le 1) is (x=1). Let (x=re^{i\theta}) with (0\le r\le 1). If (e^{x-1}=x) then [ |x| = e^{\Re(x)-1} ;\Longrightarrow; r = e^{r\cos\theta-1} ;\Longrightarrow; \ln r = r\cos\theta-1, \tag{2} ] and [ \arg x = \Im(x) \pmod{2\pi} ;\Longrightarrow; \theta = r\sin\theta + 2\pi k. ] Because (|\theta|\le\pi) and (|r\sin\theta|\le r\le 1), we must have (k=0), hence [ \theta = r\sin\theta. \tag{3} ] If (\theta=0), then (2) gives (r = e^{r-1}). The function (f(r)=e^{r-1}-r) satisfies (f(r)>0) for (0\le r<1) and (f(1)=0), so (r=1) is the only solution. If (\theta\neq 0), then (3) implies (r = \theta/\sin\theta). For (\theta\neq 0) we have (|\sin\theta|<|\theta|), so (r>1), contradicting (r\le 1). Thus (x=1) is the unique zero in (|x|\le 1). Moreover, at (x=1) the denominator has a double zero because [ e^{x-1}-x = \tfrac{1}{2}(x-1)^2 + O\bigl((x-1)^3\bigr). ]
Consequently, (Z(x)) has a simple pole at (x=1) and is analytic for (|x|<R) where (R>1) is the modulus of the next zero of (e^{x-1}-x) (such zeros exist and have modulus (>1) because the function is entire). Expanding (1) near (x=1): [ \frac{1-x}{e^{x-1}-x} = \frac{-(x-1)}{\frac{1}{2}(x-1)^2 + O((x-1)^3)} = -\frac{2}{x-1} + O(1), ] so [ Z(x) = x\left(-\frac{2}{x-1} + O(1)\right) = \frac{2}{1-x} + H(x), ] where (H(x)) is analytic in (|x|<R) with (R>1). Writing (H(x)=\sum_{m\ge 0} h_m x^m), we have (z_m = 2 + h_m) for (m\ge 1). Because (H) is analytic in a disk of radius (>1), its coefficients decay exponentially: (h_m = O(r^m)) for some (r<1). Hence [ \lim_{m\to\infty} z_m = 2. ] For the differences, [ z_m - z_{m+1} = h_m - h_{m+1} = O(r^m), ] so ((z_m - z_{m+1})^2 = O(r^{2m})). The series (\sum_{m\ge 1}(z_m - z_{m+1})^2) therefore converges by comparison with a geometric series. The term for (m=0) (if (z_0) is defined) is finite and does not affect convergence.
This completes the proof. ∎