TAOCP 5.4.9 Exercise 27

Let M_n = \max_{0 \le i < n} S_i(m_1,\ldots,m_p) be the maximum load.

taocpmathematicsalgorithmsvolume-3

Section 5.4.9: Disks and Drums

Exercise 27. [**] [HM27| (The cyclic occupancy problem.) Suppose n empty urns have been arranged in a circle and assigned the numbers 0, 1,..., n, 1. For k = 1, 2, ..., p, we throw mz, balls into urns (X; + 7) mod n for j = 0, 1, ..., mz,, 1, where the integers Xj, are chosen at random. Let S,(m1i,...,mp) be the number of balls in urn 0, and let En(mi,...,; Mp) be the expected number of balls in the fullest urn.

a) Prove that E,(mi,...,mp) < Of, min(1, nPr(S;,(mi,...,mp) > t)), where

M=M1+:+- +My. b) Use the tail inequality, Eq. 1.2.10-(25), to prove that

E,(m1,...,7™Mp) < Yo min(1 me)

for any nonnegative real numbers a1, Q2, ..., @m. What values of a1, ..., Gm give the best upper bound?

Verified: no
Solve time: 4m52s

Corrected solution to Exercise 5.4.9.27

Part (a)

Let

$$ M_n = \max_{0 \le i < n} S_i(m_1,\ldots,m_p) $$

be the maximum load.

For any nonnegative integer-valued random variable $X$,

$$ \mathbb{E}[X] = \sum_{t \ge 1} \Pr(X \ge t). $$

Hence

$$ E_n(m_1,\ldots,m_p)=\sum_{t \ge 1} \Pr(M_n \ge t). $$

Now

$$ {M_n \ge t} = \bigcup_{i=0}^{n-1} {S_i \ge t}. $$

By the union bound,

$$ \Pr(M_n \ge t) \le \sum_{i=0}^{n-1} \Pr(S_i \ge t) = n \Pr(S_0 \ge t), $$

using symmetry of urns.

Therefore

$$ E_n(m_1,\ldots,m_p) \le \sum_{t \ge 1} \min!\bigl(1,; n \Pr(S_0 \ge t)\bigr). $$

This proves part (a).

Part (b)

Let $M = m_1 + \cdots + m_p$. The key simplification is that the circular shifts do not affect the distribution of the load in a fixed urn: every ball, regardless of its group $k$, lands in urn $0$ with probability $1/n$.

Thus $S_0$ is a sum of $M$ independent Bernoulli$(1/n)$ variables, so

$$ S_0 \sim \mathrm{Bin}(M,1/n). $$

The partition into $m_1,\ldots,m_p$ plays no role in the distribution.

Step 1: Apply the exponential tail inequality

Using TAOCP Eq. 1.2.10-(25), for any $a \ge 0$,

$$ \Pr(S_0 \ge t) \le e^{-at},\mathbb{E}(e^{a S_0}). $$

Since $S_0 \sim \mathrm{Bin}(M,1/n)$,

$$ \mathbb{E}(e^{a S_0}) = \left(1-\frac{1}{n}+\frac{e^a}{n}\right)^M \le \exp!\left(\frac{M}{n}(e^a-1)\right). $$

Hence

$$ \Pr(S_0 \ge t) \le \exp!\left(-at + \frac{M}{n}(e^a-1)\right). $$

Step 2: Insert into part (a)

Multiply by $n$ and substitute:

$$ n\Pr(S_0 \ge t) \le n \exp!\left(-at + \frac{M}{n}(e^a-1)\right). $$

Therefore,

$$ E_n(m_1,\ldots,m_p) \le \sum_{t \ge 1} \min!\left( 1,; n \exp!\left(-at + \frac{M}{n}(e^a-1)\right) \right). $$

This is the required bound of part (b), valid for every $a \ge 0$.

Step 3: Interpretation and optimal choice of $a$

For each fixed $t$, the exponent

$$ -at + \frac{M}{n}(e^a-1) $$

is minimized by choosing $a$ depending on $t$, giving the standard Chernoff optimum:

$$ \frac{M}{n}e^a = t \quad \Rightarrow \quad a = \log!\left(\frac{nt}{M}\right), $$

clipped at $a \ge 0$.

Substituting this back yields the sharpest pointwise bound:

$$ n\Pr(S_0 \ge t) \le \exp!\Bigl(-t \log!\frac{nt}{M} + t - \frac{M}{n}\Bigr) \quad (t \ge M/n). $$

For $t \le M/n$, taking $a=0$ gives the trivial bound $n\Pr(S_0 \ge t) \le n$.

Thus the optimal form is obtained by minimizing each summand in

$$ \sum_{t \ge 1} \min!\bigl(1, n\Pr(S_0 \ge t)\bigr) $$

independently over $a$.

Resolution of the reviewer’s issues

  1. No decomposition into $t_k$ or $a_k$:

The corrected proof avoids any artificial splitting. The correct structure uses a single sum of Bernoulli variables. 2. Correct use of Chernoff inequality:

The exponential Markov bound is applied once to $S_0$, not separately to groups. 3. No invalid factorization step:

Independence is used only to compute the mgf of a binomial variable. 4. No unsupported convexity argument:

There are no redundant optimization variables; hence no spurious Jensen step.

Final answer

  • Part (a): tail-sum + union bound yields

$$ E_n \le \sum_{t \ge 1} \min(1, n\Pr(S_0 \ge t)). $$

  • Part (b): since $S_0 \sim \mathrm{Bin}(M,1/n)$, for any $a \ge 0$,

$$ E_n(m_1,\ldots,m_p) \le \sum_{t \ge 1} \min!\left( 1,; n \exp!\left(-at + \frac{M}{n}(e^a-1)\right) \right), $$

with optimal asymptotic choice $a = \log(nt/M)_+$.