Section 5.1.3: Runs

Exercise 10. [**] [HM30] Find the asymptotic behavior of the mean and variance of the distributions $h_k(z)$ in the preceding exercise, for large $k$.

Verified: yes
Solve time: 51m13s

---

$$ h_k(z)=\sum_{m\ge k}p_{km}z^m $$

is the probability generating function of the total length

$$ S_k=L_1+\cdots+L_k $$

of the first $k$ runs. The preceding exercise gives

$$ h_k(z)=\left(\frac{z(1-z)}{e^{-z}-1+z}\right)^k . $$

Indeed, if

$$ g(z)=\sum_{l\ge1}\frac{z^l}{(l+1)!} =\frac{e^z-1-z}{z}, $$

then Exercise 5.1.3.9 yields

$$ h_k(z)=\left(\frac{1}{g(z)}\right)^k =\left(\frac{z}{e^z-1-z}\right)^k, $$

and multiplying numerator and denominator by $e^{-z}$ gives the equivalent form above. Since $h_k(1)=1$, it is a probability generating function.

For a probability generating function $H(z)$,

$$ \mathbb E[X]=H'(1),\qquad \operatorname{Var}(X)=H''(1)+H'(1)-H'(1)^2. $$

It is convenient to write

$$ h_k(z)=A(z)^k, \qquad A(z)=\frac{z(1-z)}{e^{-z}-1+z}. $$

Since $A(1)=1$,

$$ \log h_k(z)=k\log A(z). $$

Hence

$$ \mathbb E[S_k] =h_k'(1) =kA'(1), $$

and

$$ \operatorname{Var}(S_k) =kA''(1)+kA'(1)-kA'(1)^2. $$

Therefore it suffices to compute the first two derivatives of $A$ at $1$.

Let

$$ D(z)=e^{-z}-1+z. $$

Then $D(1)=e^{-1}$, $D'(1)=1-e^{-1}$, and

$$ A(z)=\frac{z(1-z)}{D(z)}. $$

Instead of differentiating $A$ directly, expand around $z=1$. Put

$$ z=1+t. $$

Then

$$ D(1+t) =e^{-1}e^{-t}+t =e^{-1} +(1-e^{-1})t +\frac{e^{-1}}2t^2 -\frac{e^{-1}}6t^3 +O(t^4), $$

while

$$ z(1-z)=-(t+t^2). $$

Therefore

$$ A(1+t) =\frac{-(t+t^2)} {e^{-1}+(1-e^{-1})t+\frac{e^{-1}}2t^2+O(t^3)}. $$

After inversion of the denominator and simplification,

$$ A(1+t)

1+(e-1)t+\frac{1}{2}(4e-e^2-1)t^2+O(t^3). $$

Hence

$$ A'(1)=e-1, $$

and

$$ A''(1)=4e-e^2-1. $$

Consequently

$$ \mathbb E[S_k] =k(e-1). $$

For the variance,

$$ \begin{aligned} \operatorname{Var}(S_k) &= kA''(1)+kA'(1)-kA'(1)^2\ &= k\Bigl[(4e-e^2-1)+(e-1)-(e-1)^2\Bigr]\ &= k(3e-e^2). \end{aligned} $$

Thus the mean and variance are exactly linear in $k$, and therefore their asymptotic behavior is

$$ \boxed{\mathbb E[S_k]\sim (e-1)k}, $$

and

$$ \boxed{\operatorname{Var}(S_k)\sim (3e-e^2)k}. $$

Numerically,

$$ e-1=1.718281828\ldots, \qquad 3e-e^2=0.765789386\ldots. $$

Therefore, for large $k$,

$$ \boxed{ \mathbb E[S_k]=(e-1)k, \qquad \operatorname{Var}(S_k)=(3e-e^2)k. } $$

No appeal to independence or asymptotic covariance estimates is needed; both quantities follow directly from the generating function $h_k(z)$. ∎_