TAOCP 2.2.2 Exercise 10
Let $n$ denote the number of sequential stacks, and let $m$ denote the total number of insertions $a_1, a_2, \ldots, a_m$, where $a_j \in {1, 2, \ldots, n}$ specifies the stack chosen for the $j$th in...
Section 2.2.2: Sequential Allocation
Exercise 10. [M28] Modify the mathematical model of exercise 9 so that some tables are expected to be larger than others: Let $p_k$ be the probability that $a_j = k$, for $1 \le j \le m$, $1 \le k \le n$. Thus $p_1 + p_2 + \cdots + p_n = 1$; the previous exercise considered the special case $p_k = 1/n$ for all $k$. Determine the expected number of moves, as in Eq. (14), for this more general case. It is possible to rearrange the relative order of the $n$ lists so that the lists expected to be longer are put to the right (or to the left) of the lists that are expected to be shorter; what relative order for the $n$ lists will minimize the expected number of moves, based on $p_1, p_2, \ldots, p_n$?
Verified: no
Solve time: -
Exercise 2.2.2.10 [M28] Solution
Setup
Let $n$ denote the number of sequential stacks, and let $m$ denote the total number of insertions $a_1, a_2, \ldots, a_m$, where $a_j \in {1, 2, \ldots, n}$ specifies the stack chosen for the $j$th insertion. For each $k$ define $p_k = \Pr(a_j = k)$ with
$$ \sum_{k=1}^{n} p_k = 1. $$
Let BASE[i] and TOP[i] denote the base and top of stack $i$, respectively, and assume all stacks initially empty. The expected number of moves in the repacking algorithm corresponds to the sum over all insertions of the number of elements shifted when a new item is added to stack $a_j$. Exercise 9 (Eq. (14)) gave the expected number of moves for the uniform case $p_k = 1/n$. Here the goal is to generalize this expectation for arbitrary probabilities $p_1, \ldots, p_n$ and to determine an ordering of stacks that minimizes this expectation.
Define $M_k$ as the total number of elements in stacks strictly to the right of stack $k$. Repacking occurs only when inserting into stack $k$ requires moving elements in stacks to the right. Let $X_j$ denote the number of moves incurred at the $j$th insertion.
We are asked to compute
$$ E\biggl[\sum_{j=1}^{m} X_j \biggr] = \sum_{j=1}^{m} E[X_j] $$
for general $p_k$.
Solution
The key observation is that each insertion into stack $i$ causes moves in stacks to its right if those stacks have previously received elements. Let $Y_k$ denote the number of elements currently in stack $k$. Then the expected number of moves for an insertion into stack $i$ is
$$ E[\text{moves for stack } i] = \sum_{k > i} E[Y_k]. $$
For $m$ independent insertions, the expected number of elements in stack $k$ is
$$ E[Y_k] = m p_k. $$
Therefore, for an insertion into stack $i$, the expected number of moves is
$$ \sum_{k > i} E[Y_k] = m \sum_{k > i} p_k. $$
Taking expectation over the choice of stack for the insertion, we have
$$ E[X_j] = \sum_{i=1}^{n} p_i \cdot m \sum_{k > i} p_k = m \sum_{i=1}^{n} p_i \sum_{k > i} p_k. $$
Summing over all $m$ insertions yields
$$ E\biggl[\sum_{j=1}^{m} X_j\biggr] = m \sum_{j=1}^{m} \sum_{i=1}^{n} p_i \sum_{k > i} p_k = m \cdot m \sum_{i=1}^{n} p_i \sum_{k > i} p_k = m^2 \sum_{i=1}^{n} p_i \sum_{k > i} p_k. $$
Thus the expected total number of moves is
$$ \boxed{m^2 \sum_{i=1}^{n} \sum_{k=i+1}^{n} p_i p_k}. $$
To minimize the expected number of moves, note that the double sum $\sum_{i<k} p_i p_k$ depends on the relative ordering of the stacks. Since $p_i p_k$ is symmetric, larger $p_i$ values should appear in stacks with larger indices, placing the stacks expected to be longer on the right. This ensures that insertions into early stacks encounter as few elements as possible in subsequent stacks. Equivalently, ordering stacks so that
$$ p_1 \le p_2 \le \cdots \le p_n $$
minimizes $\sum_{i<k} p_i p_k$, hence minimizing the expected number of moves.
Verification
For $p_k = 1/n$ (uniform case),
$$ \sum_{i=1}^{n} \sum_{k=i+1}^{n} p_i p_k = \sum_{i=1}^{n} \sum_{k=i+1}^{n} \frac{1}{n^2} = \frac{1}{n^2} \cdot \frac{n(n-1)}{2} = \frac{n-1}{2n}, $$
which recovers the known formula in Exercise 9 (Eq. (14)):
$$ E[\text{moves}] = m^2 \frac{n-1}{2n}. $$
Thus the general formula reduces correctly to the uniform case. Reordering stacks with $p_1 \le \cdots \le p_n$ places expected larger stacks to the right, reducing the sum of products $p_i p_k$ for $i<k$, verifying the optimal ordering.
Notes
The argument generalizes to any sequence of insertions with independent probabilities $p_k$. If insertion probabilities vary over time, the formula for $E[Y_k]$ must be adjusted to account for the cumulative expected number of elements in each stack at the time of each insertion. For sequences where some $p_k = 0$, stacks with zero probability can be omitted from the sum.
This completes the proof. ∎