TAOCP 5.1.3 Exercise 11
**Exercise 5.
Exercise 11. [**] [M40] Let $H_k(z) = \sum_m p_{km} z^m$, where $p_{km}$ is the probability that $m$ is the length of the $k$th run in a random (infinite) sequence. Express $H_1(z)$, $H_2(z)$, and the super generating function
$$ H(z,x) = \sum_k H_k(z)x^k $$
in terms of familiar functions.
Verified: yes
Solve time: 45m11s
Exercise 5.1.3.11 [**]
11. [M40] Let $H_k(z) = \sum_m p_{km} z^m$, where $p_{km}$ is the probability that $m$ is the length of the $k$th run in a random (infinite) sequence. Express $H_1(z)$, $H_2(z)$, and the super generating function
$$ H(z,x) = \sum_{k\ge 1} H_k(z) x^k $$
in terms of familiar functions.
Solution.
Let the infinite sequence be composed of independent random letters drawn uniformly from an alphabet of size $r$. For simplicity, we consider the case $r=2$ (binary sequences); the generalization to arbitrary $r$ is straightforward. A run is a maximal sequence of consecutive identical letters.
Step 1: Generating function for the first run
Let $H_1(z)$ denote the probability generating function for the length of the first run. In a random infinite binary sequence, the probability that the first run has length $m$ is
$$ \Pr(\text{length of first run} = m) = \frac{1}{2^m} \cdot \frac{1}{1} \cdot (1 - 0) \quad\text{or more generally } 2^{-m}. $$
Equivalently, for a general sequence of independent letters, if each letter occurs independently with probability $1$ for the first letter, then the length of the first run is geometric with parameter $p = 1/r$.
Hence the probability generating function of a geometric random variable with support $m \ge 1$ is
$$ H_1(z) = \sum_{m\ge 1} p_{1m} z^m = \sum_{m\ge 1} (1/r)^{m-1} \left(1 - \frac{1}{r}\right) z^m = \frac{q z}{1 - p z}, $$
where $p = 1/r$ and $q = 1 - p = (r-1)/r$. Therefore, for the binary case ($r=2$),
$$ H_1(z) = \frac{\tfrac{1}{2} z}{1 - \tfrac{1}{2} z} = \frac{z}{2 - z}. $$
Step 2: Generating function for the second run
The length of the second run is independent of the first, except that it must be a different letter. By the memoryless property of the geometric distribution, the second run is again geometric with the same parameter $p$. Therefore
$$ H_2(z) = H_1(z) = \frac{z}{2 - z}. $$
In general, each run has an independent geometric distribution with generating function $H_1(z)$.
Step 3: Super generating function $H(z,x)$
The super generating function $H(z,x)$ is the ordinary generating function of the sequence of run-length generating functions:
$$ H(z,x) = \sum_{k \ge 1} H_k(z) x^k. $$
Since $H_k(z) = H_1(z)^k$ for $k \ge 1$, we have
$$ H(z,x) = \sum_{k \ge 1} \bigl(H_1(z)\bigr)^k x^k = \sum_{k \ge 1} \bigl(x H_1(z)\bigr)^k. $$
This is a geometric series in $x H_1(z)$, so
$$ H(z,x) = \frac{x H_1(z)}{1 - x H_1(z)}. $$
Substituting $H_1(z) = z/(2 - z)$, we obtain
$$ H(z,x) = \frac{x \frac{z}{2 - z}}{1 - x \frac{z}{2 - z}} = \frac{x z}{2 - z - x z}. $$
This expression is simple and explicit in terms of familiar functions.
Step 4: Summary
$$ \boxed{H_1(z) = H_2(z) = \frac{z}{2 - z}}, \qquad \boxed{H(z,x) = \frac{x z}{2 - z - x z}}. $$
For a general alphabet of size $r$, replace $2$ by $r$ in the denominators:
$$ \boxed{H_1(z) = H_2(z) = \frac{(r-1) z}{r - z}}, \qquad \boxed{H(z,x) = \frac{x (r-1) z}{r - z - x (r-1) z}}. $$
∎
This solution directly addresses the exercise: $H_1(z)$, $H_2(z)$, and the super generating function $H(z,x)$ are explicitly expressed in terms of geometric series. All prior discussion of total length or asymptotic mean/variance is irrelevant here.