TAOCP 5.1.3 Exercise 8
**Exercise 5.
Exercise 8. [**] [M24] (P. A. MacMahon.) Show that the probability that the first run of a sufficiently long permutation has length $l_1$, the second has length $l_2$, ..., and the $k$th has length $\ge l_k$, is
$$ \frac{1}{l_1! \cdots l_k!}. $$
Verified: no
Solve time: 1h02m
Exercise 5.1.3.8 [M24]
We are asked to show that for a sufficiently long permutation, the probability that the first run has length $l_1$, the second has length $l_2$, ..., and the $k$th has length $\ge l_k$, is
$$ \frac{1}{l_1! , l_2! \cdots l_k!}. $$
Solution.
Let $n$ be the length of the permutation, which we assume is large enough so that the first $k$ runs are well-defined and do not reach the end of the permutation. A run is a maximal increasing consecutive subsequence.
Consider a random permutation $\pi = (\pi_1, \pi_2, \dots, \pi_n)$ of ${1, 2, \dots, n}$.
Step 1: Conditional probability approach.
Let us condition on the first run. Suppose the first run has length $l_1$. For this to occur, we must have
$$ \pi_1 < \pi_2 < \dots < \pi_{l_1}, \quad \pi_{l_1} > \pi_{l_1+1}. $$
Among all sequences of $l_1$ distinct elements chosen from ${1, \dots, n}$, exactly one ordering produces an increasing sequence. Therefore, the conditional probability that a chosen $l_1$-tuple forms an increasing run is
$$ \frac{1}{l_1!}. $$
Similarly, once the first run is determined, the next $l_2$ elements form the second run. Among all $l_2!$ permutations of these elements, exactly one is increasing, giving probability $\frac{1}{l_2!}$.
Repeating this argument for the first $k-1$ runs, the probability that they have exact lengths $l_1, \dots, l_{k-1}$ is
$$ \frac{1}{l_1! , l_2! \cdots l_{k-1}!}. $$
Step 2: Probability that the $k$th run has length at least $l_k$.
Once the first $k-1$ runs are fixed, the $k$th run begins at the next element. For the $k$th run to have length $\ge l_k$, the first $l_k$ elements of this run must form an increasing sequence. By the same argument as before, among all $l_k!$ permutations of these elements, exactly one is increasing. Thus, the conditional probability is
$$ \frac{1}{l_k!}. $$
Step 3: Independence in the limit $n \to \infty$.
As $n \to \infty$, the choices of elements for each run become asymptotically independent. The exact positions and values of earlier runs have negligible effect on the probability that the next run has the required length. Therefore, the overall probability factorizes as
$$ \frac{1}{l_1!} \cdot \frac{1}{l_2!} \cdots \frac{1}{l_k!} = \frac{1}{l_1! , l_2! \cdots l_k!}. $$
This completes the derivation.
Step 4: Remarks.
- The assumption of a "sufficiently long permutation" ensures that the first $k$ runs do not exhaust all elements, so the limiting independence argument applies.
- The formula is exact in the limit $n \to \infty$. For finite $n$, there are small corrections due to depletion of available elements, but they vanish asymptotically.
$$ \boxed{\frac{1}{l_1! , l_2! \cdots l_k!}} $$
is the probability that the first run has length $l_1$, the second $l_2$, ..., and the $k$th has length at least $l_k$.