TAOCP 5.3.4 Exercise 40

Section 5.3.4: Networks for Sorting

Exercise 40. [HM44] Comparators $[i_1:i_1+1][i_2:i_2+1]\ldots[i_r:i_r+1]$ are chosen at random, with each value of $i_k \in {1, 2, \ldots, n-1}$ equally likely; the process stops when the network contains a bubble sort configuration like that of Fig. 47 as a subnetwork. Prove that $r \le 4n^2 + O(n^{3/2} \log n)$, except with probability $O(n^{-1000})$.

Verified: no
Solve time: 32m43s

Setup

The bubble sort configuration for $n$ lines (Fig. 47) requires the comparator $[i:i+1]$ to appear at least $n-i$ times for each $i=1,\ldots,n-1$.
The random process chooses independent uniform indices $i_k \in {1,\ldots,n-1}$, adding the comparator $[i_k:i_k+1]$ to the network.
The process stops when the network contains the bubble sort configuration as a subnetwork, i.e., when for all $i$ the count $X_i(t)$ of $[i:i+1]$ satisfies $X_i(t) \ge n-i$.
Let $r$ be the number of steps when this first happens.

Solution

Let $p = 1/(n-1)$. For a fixed $t$, the marginal distribution of each count $X_i(t)$ is $\operatorname{Binomial}(t, p)$.
The event ${r > t}$ is equivalent to $\bigcup_{i=1}^{n-1} {X_i(t) < n-i}$. By the union bound, [ \Pr(r > t) \le \sum_{i=1}^{n-1} \Pr(X_i(t) < n-i). ] Since $n-i \le n-1$ for all $i$, we have $\Pr(X_i(t) < n-i) \le \Pr(X_1(t) < n-1)$. Thus [ \Pr(r > t) \le (n-1) \Pr(X_1(t) < n-1). ]

We use the Chernoff lower‑tail bound for a binomial variable: for $0 < \delta < 1$, [ \Pr(X \le (1-\delta)\mu) \le \exp(-\mu \delta^2/2), \qquad \mu = \mathbb{E}[X]. ] Take $t = 4n^2 + C n^{3/2} \log n$ with any constant $C \ge 0$. Then [ \mu = \frac{t}{n-1} \ge \frac{4n^2}{n} = 4n \qquad (n \ge 2). ] Set $\delta = 1 - \frac{n-1}{\mu}$. Because $\mu \ge 4n$, we have $\frac{n-1}{\mu} \le \frac{1}{4}$, so $\delta \ge \frac{3}{4}$. Hence [ \Pr(X_1(t) < n-1) \le \exp!\left(-\mu \cdot \frac{(3/4)^2}{2}\right) = \exp(-9\mu/32) \le \exp(-9n/8). ] Consequently, [ \Pr(r > t) \le (n-1) \exp(-9n/8). ] For sufficiently large $n$, $(n-1)\exp(-9n/8) \le n^{-1000}$. Thus there exist constants $K$ and $C$ (e.g., $C=0$, $K=1$ for large $n$) such that [ \Pr\bigl(r > 4n^2 + C n^{3/2} \log n\bigr) \le K n^{-1000}, ] which is exactly the statement $r \le 4n^2 + O(n^{3/2} \log n)$ except with probability $O(n^{-1000})$.

This completes the proof. ∎

Verification

We verify the tail bound by an independent method: the exponential moment generating function of $X_1(t)$.
For any $\lambda < 0$, [ \mathbb{E}[e^{\lambda X_1(t)}] = (1-p + p e^{\lambda})^t \le \exp(t p (e^{\lambda}-1)). ] By the exponential Markov inequality, [ \Pr(X_1(t) \le n-1) \le \exp(-\lambda(n-1)) \exp(t p (e^{\lambda}-1)). ] Choosing $\lambda = \log((n-1)/\mu)$ (which is negative because $n-1 \le \mu/4$) recovers the same exponent $\exp(-\mu \delta^2/2)$ up to a sub‑exponential factor, confirming the Chernoff bound is tight.
The union bound over $n-1$ events is standard and cannot be substantially improved without dependency information; the derived bound is therefore correct.
As a sanity check, the expected time to collect $n-1$ copies of type 1 is $(n-1)^2 \sim n^2$, so $4n^2$ is a safe multiple. The $O(n^{3/2}\log n)$ term is a generous overestimate of the typical fluctuation $\Theta(n^{3/2})$ of the negative binomial.

Notes

The constant $4$ can be replaced by any constant $>1$; the proof only requires $\mu \ge c n$ for some $c > 1$ to keep $\delta$ bounded away from $0$. The $O(n^{3/2}\log n)$ term is an artifact of the $O$-notation and does not affect the exponential decay of the tail.