Hashing and Load Balancing

CS 265/CME309: Randomized Algorithms — Lecture 6 Gregory Valiant, updated by Mary Wootters (Stanford, Fall 2020)

Table of Contents

• #1. The Balls-in-Bins Model|1. The Balls-in-Bins Model
  • #1.1 Setup and Basic Probabilities|1.1 Setup and Basic Probabilities
  • #1.2 The Birthday Paradox|1.2 The Birthday Paradox
  • #1.3 Coupon Collector as Balls-in-Bins|1.3 Coupon Collector as Balls-in-Bins
• #2. Maximum Bin Load|2. Maximum Bin Load
  • #2.1 Upper Bound|2.1 Upper Bound
  • #2.2 Lower Bound|2.2 Lower Bound
• #3. Poisson Distribution and Poissonization|3. Poisson Distribution and Poissonization
  • #3.1 The Poisson Distribution|3.1 The Poisson Distribution
  • #3.2 The Poissonization Theorem|3.2 The Poissonization Theorem
  • #3.3 Application: Coupon Collector Exact Limit|3.3 Application: Coupon Collector Exact Limit
  • #3.4 Lower Bound via Poissonization|3.4 Lower Bound via Poissonization
• #4. The Power of Two Choices|4. The Power of Two Choices
  • #4.1 Setup and Theorem|4.1 Setup and Theorem
  • #4.2 Proof via Load-Level Recursion|4.2 Proof via Load-Level Recursion
  • #4.3 Stochastic Dominance and Formal Justification|4.3 Stochastic Dominance and Formal Justification
  • #4.4 Extension to d Choices|4.4 Extension to d Choices
• #5. Exercises|5. Exercises
• #References|References

1. The Balls-in-Bins Model 🎲

1.1 Setup and Basic Probabilities

The balls-in-bins model is one of the most versatile abstractions in the analysis of randomized algorithms. It captures hashing, load balancing, coupon collecting, and birthday-style coincidences within a single probabilistic framework.

Setup. Toss \(n\) balls independently and uniformly at random into \(m\) bins. Each ball lands in bin \(j\) with probability \(1/m\), independently of all other balls.

The central questions are: 1. Collision: When do two balls first land in the same bin? 2. Coverage: When has every bin received at least one ball? 3. Load: What is the maximum number of balls in any single bin?

1.2 The Birthday Paradox

The birthday paradox asks: how large must \(n\) be before the probability of at least one collision exceeds \(1/2\)?

Proposition 1 (Birthday Threshold). When \(n\) balls are tossed into \(m\) bins, the probability that all \(n\) balls land in distinct bins is

\[\Pr[\text{no collision}] = \prod_{i=0}^{n-1}\left(1 - \frac{i}{m}\right).\]

Using \(1 - x \leq e^{-x}\),

\[\Pr[\text{no collision}] \leq \exp\!\left(-\sum_{i=0}^{n-1}\frac{i}{m}\right) = \exp\!\left(-\frac{n(n-1)}{2m}\right).\]

This is \(\leq 1/2\) once \(n(n-1) \geq 2m\ln 2\), i.e., \(n \approx \sqrt{2m\ln 2} \approx 1.177\sqrt{m}\).

Key conclusion: \(n = \Theta(\sqrt{m})\) is the collision threshold.

For the standard birthday problem, \(m = 365\) gives \(n \approx 23\), which famously surprises most people.

Exercise 1 is placed in #5. Exercises|Section 5.

1.3 Coupon Collector as Balls-in-Bins

The coupon collector problem asks: how many balls must be tossed into \(m\) bins so that every bin is non-empty in expectation?

When \(j\) distinct bins are already occupied, each new ball hits a new bin with probability \((m-j)/m\). The number of additional balls needed is geometrically distributed with mean \(m/(m-j)\). Summing over \(j = 0, 1, \ldots, m-1\),

\[\mathbb{E}[\text{balls to fill all bins}] = \sum_{j=0}^{m-1}\frac{m}{m-j} = m\sum_{k=1}^{m}\frac{1}{k} = m H_m \approx m\ln m.\]

So the expected number of balls needed to cover all \(m\) bins is \(m \ln m\). An exact distributional characterization — not just the expectation — is established in #3.3 Application: Coupon Collector Exact Limit|Section 3.3 via Poissonization.

2. Maximum Bin Load 📊

2.1 Upper Bound

The most practically important question in load balancing is: how overloaded can any single bin become?

Proposition 2 (Max Load Upper Bound). When \(n\) balls are tossed into \(n\) bins, the maximum bin load satisfies

\[\Pr\!\left[\max_j \text{load}(j) \geq \frac{c\ln n}{\ln\ln n}\right] \leq \frac{1}{n^{c-1}}\]

for any constant \(c > 1\), with high probability (i.e., probability \(1 - o(1)\) for \(c > 2\)).

Proof. Set \(k = \lceil c\ln n / \ln\ln n \rceil\). The probability that bin 1 receives at least \(k\) balls is

\[\Pr[\text{load}(1) \geq k] = \sum_{j=k}^{n}\binom{n}{j}\left(\frac{1}{n}\right)^j\left(1-\frac{1}{n}\right)^{n-j} \leq \sum_{j=k}^{n}\frac{n^j}{j!}\cdot\frac{1}{n^j} = \sum_{j=k}^{\infty}\frac{1}{j!}.\]

Since \(\sum_{j=k}^{\infty} 1/j! \leq 2/k!\) for large \(k\), we have

\[\Pr[\text{load}(1) \geq k] \leq \frac{2}{k!}.\]

Now bound \(k!\) from below using Stirling’s inequality \(k! \geq (k/e)^k\):

\[\frac{1}{k!} \leq \left(\frac{e}{k}\right)^k.\]

Substituting \(k = c\ln n / \ln\ln n\):

\[\frac{e}{k} = \frac{e\ln\ln n}{c\ln n},\]

so

\[\left(\frac{e}{k}\right)^k = \left(\frac{e\ln\ln n}{c\ln n}\right)^{c\ln n/\ln\ln n}.\]

Taking the logarithm:

\[k\ln(e/k) = \frac{c\ln n}{\ln\ln n}\left(1 + \ln\ln\ln n - \ln c - \ln\ln n\right) = \frac{c\ln n}{\ln\ln n}\left(-\ln\ln n + O(\ln\ln\ln n)\right).\]

\[= -c\ln n + O\!\left(\frac{\ln n \cdot \ln\ln\ln n}{\ln\ln n}\right) = -c\ln n + o(\ln n) = -(c - o(1))\ln n.\]

Therefore \(1/k! \leq n^{-(c-o(1))}\), so

\[\Pr[\text{load}(1) \geq k] \leq n^{-(c-o(1))}.\]

By the union bound over all \(n\) bins,

\[\Pr\!\left[\max_j \text{load}(j) \geq k\right] \leq n \cdot n^{-(c-o(1))} = n^{-(c-1-o(1))}.\]

For \(c > 2\), this probability is \(o(1)\), so the maximum load is at most \(c\ln n/\ln\ln n\) with high probability. \(\square\)

2.2 Lower Bound

Proposition 5 (Max Load Lower Bound). When \(n\) balls are tossed into \(n\) bins, there exists a constant \(c > 0\) such that

\[\Pr\!\left[\max_j \text{load}(j) \geq \frac{c\ln n}{\ln\ln n}\right] \geq 1 - o(1).\]

The proof uses Poissonization to make the bin loads independent, enabling a second-moment argument. The details appear in #3.4 Lower Bound via Poissonization|Section 3.4 after we develop the necessary machinery.

3. Poisson Distribution and Poissonization ⚗️

3.1 The Poisson Distribution

Definition (Poisson Distribution). A random variable \(X\) is Poisson with parameter \(\lambda\), written \(X \sim \text{Poi}(\lambda)\), if

\[\Pr[X = k] = e^{-\lambda}\frac{\lambda^k}{k!}, \quad k = 0, 1, 2, \ldots\]

Direct computation gives \(\mathbb{E}[X] = \lambda\) and \(\text{Var}(X) = \lambda\).

Key properties: 1. Additivity. If \(X_1 \sim \text{Poi}(\lambda_1)\) and \(X_2 \sim \text{Poi}(\lambda_2)\) are independent, then \(X_1 + X_2 \sim \text{Poi}(\lambda_1 + \lambda_2)\). 2. Tail bound. For \(X \sim \text{Poi}(\lambda)\) and any \(c > 0\), \[\Pr[|X - \lambda| \geq c] \leq 2\exp\!\left(-\frac{c^2}{2(c+\lambda)}\right).\] 3. MGF. \(\mathbb{E}[e^{tX}] = e^{\lambda(e^t - 1)}\) for all \(t \in \mathbb{R}\).

3.2 The Poissonization Theorem

The central technical tool of this lecture is Poissonization: by randomizing the number of balls, we gain independence between bin loads — a property that fails dramatically in the fixed-\(n\) model.

Theorem 1 (Poissonization). Suppose the number of balls \(K \sim \text{Poi}(n)\) and each ball is placed independently and uniformly into one of \(m\) bins. Let \(L_j\) denote the load in bin \(j\). Then:

1. Each \(L_j \sim \text{Poi}(n/m)\).
2. The loads \(L_1, L_2, \ldots, L_m\) are mutually independent.

Proof. Let \(B_j\) be the number of balls in bin \(j\), and let \(\mathbf{B} = (B_1, \ldots, B_m)\). We compute the joint PMF.

Fix counts \((k_1, k_2, \ldots, k_m)\) with \(k_1 + \cdots + k_m = N\) for some \(N \geq 0\). Conditioning on \(K = N\):

\[\Pr[B_1 = k_1, \ldots, B_m = k_m \mid K = N] = \frac{N!}{k_1!\cdots k_m!}\cdot\frac{1}{m^N}.\]

The unconditional joint PMF is

\[\Pr[B_1 = k_1, \ldots, B_m = k_m] = \sum_{N=0}^{\infty}\Pr[K = N]\cdot \mathbf{1}\!\left[\sum_j k_j = N\right]\cdot\frac{N!}{k_1!\cdots k_m!}\cdot\frac{1}{m^N}.\]

Since the indicator forces \(N = \sum_j k_j\), setting \(N = k_1 + \cdots + k_m\):

\[= e^{-n}\frac{n^N}{N!}\cdot\frac{N!}{k_1!\cdots k_m!}\cdot\frac{1}{m^N} = e^{-n}\prod_{j=1}^{m}\frac{(n/m)^{k_j}}{k_j!}.\]

Recognizing \(e^{-n} = e^{-n/m \cdot m} = \prod_{j=1}^{m}e^{-n/m}\):

\[\Pr[B_1 = k_1, \ldots, B_m = k_m] = \prod_{j=1}^{m}\left(e^{-n/m}\frac{(n/m)^{k_j}}{k_j!}\right).\]

This is the product of \(m\) independent \(\text{Poi}(n/m)\) PMFs, completing the proof. \(\square\)

Exercise 3 is placed in #5. Exercises|Section 5.

3.3 Application: Coupon Collector Exact Limit

Poissonization yields a strikingly precise distributional result for the Coupon Collector problem.

Proposition 4 (Coupon Collector Limit). Let \(T\) be the number of balls needed to cover all \(n\) bins. For any constant \(c \in \mathbb{R}\),

\[\Pr[T \geq n\ln n + cn] \xrightarrow{n\to\infty} 1 - e^{-e^{-c}}.\]

Proof (via Poissonization). Work in the Poisson model with \(K \sim \text{Poi}(n\ln n + cn)\) balls. By Theorem 1, each bin load is \(\text{Poi}(\ln n + c)\), independently. The probability that any fixed bin is empty is

\[\Pr[L_j = 0] = e^{-(\ln n + c)} = \frac{e^{-c}}{n}.\]

Let \(Z\) = number of empty bins. Since the \(L_j\) are independent,

\[Z = \sum_{j=1}^{n}\mathbf{1}[L_j = 0]\]

and these indicators are independent. Thus \(Z \sim \text{Bin}(n, e^{-c}/n)\), which converges in distribution to \(\text{Poi}(e^{-c})\) as \(n \to \infty\).

Coverage fails if and only if \(Z \geq 1\):

\[\Pr[\text{some bin empty}] = \Pr[Z \geq 1] \to 1 - \Pr[\text{Poi}(e^{-c}) = 0] = 1 - e^{-e^{-c}}.\]

To transfer back from the Poisson model (\(K\) random) to the fixed-\(n\ln n + cn\) model: since \(K\) concentrates within \(O(\sqrt{n\ln n})\) of its mean, and \(T\) is monotone in the number of balls, a coupling argument shows \(\Pr[T \geq n\ln n + cn]\) differs from the Poisson quantity by \(o(1)\). \(\square\)

3.4 Lower Bound via Poissonization

Proof of Proposition 5. Set \(k = \lfloor (1/2)\ln n / \ln\ln n \rfloor\) and use the Poisson model with \(K \sim \text{Poi}(n)\). By Theorem 1, each bin load \(L_j \sim \text{Poi}(1)\) independently.

The probability that a single bin has load at least \(k\) is

\[\Pr[L_j \geq k] = \sum_{\ell=k}^{\infty}e^{-1}\frac{1}{\ell!} \geq e^{-1}\frac{1}{k!}.\]

By Stirling, \(1/k! \geq (e/k)^k / \sqrt{2\pi k}\), so

\[\Pr[L_j \geq k] \geq \frac{1}{e}\cdot\frac{1}{\sqrt{2\pi k}}\left(\frac{e}{k}\right)^k.\]

Taking logs: \(k\ln(e/k) = k(1-\ln k)\). With \(k = \ln n / (2\ln\ln n)\):

\[k\ln k = \frac{\ln n}{2\ln\ln n}\cdot\ln\!\left(\frac{\ln n}{2\ln\ln n}\right) = \frac{\ln n}{2\ln\ln n}\cdot(\ln\ln n - O(\ln\ln\ln n)) = \frac{\ln n}{2} - o(\ln n).\]

Therefore \(k(1-\ln k) = k - k\ln k \leq \ln n/(2\ln\ln n) - \ln n/2 + o(\ln n) = -\ln n/2 + o(\ln n)\), giving

\[\Pr[L_j \geq k] \geq n^{-1/2 + o(1)}.\]

Since the loads are independent (Theorem 1), the expected number of bins with load \(\geq k\) is

\[\mathbb{E}\!\left[\sum_j \mathbf{1}[L_j \geq k]\right] = n \cdot \Pr[L_1 \geq k] \geq n^{1/2 + o(1)} \to \infty.\]

By a second-moment argument (or the Lovász Local Lemma), the max load is at least \(k = \Omega(\ln n / \ln\ln n)\) with high probability. De-Poissonizing completes the proof. \(\square\)

Key conclusion: The max load when \(n\) balls are thrown into \(n\) bins is \(\Theta(\ln n / \ln\ln n)\) with high probability.

4. The Power of Two Choices ⚡

4.1 Setup and Theorem

Uniform hashing gives max load \(\Theta(\ln n / \ln\ln n)\). Can we do dramatically better with a tiny amount of coordination?

The protocol: Each ball independently and uniformly samples two bins. It is placed in the less full of the two (breaking ties arbitrarily).

Theorem 2 (Power of Two Choices). When \(n\) balls are placed using the two-choice protocol into \(n\) bins, the maximum bin load is at most \(\log_2 \log_2 n + O(1)\) with high probability.

This is an exponential improvement over the \(\Theta(\log n / \log\log n)\) bound for uniform hashing — all from one additional random sample per ball.

4.2 Proof via Load-Level Recursion

Proof of Theorem 2. Define \(B_i\) = number of bins with load at least \(i\) after all \(n\) balls have been placed. We track these load-level counts and show they decay doubly exponentially.

Base case. Trivially, \(B_1 \leq n\) (at most \(n\) bins have load \(\geq 1\)). We claim \(B_2 \leq n/2\) with high probability.

Each ball is placed in a bin with load \(\geq 2\) only if both sampled bins already have load \(\geq 1\). Since \(B_1 \leq n\), the probability that a single ball increases the load of an already-loaded bin is at most \((B_1/n)^2 \leq 1\). But in fact, for \(B_2\) to be large, many balls must both land in bins already having \(\geq 1\) ball. A careful analysis using linearity of expectation gives \(\mathbb{E}[B_2] \leq n/2\), and concentration then gives \(B_2 \leq n/2\) whp.

Inductive step. Suppose \(B_i \leq n / \beta^{2^{i-2}}\) for some base \(\beta > 0\) to be determined. A ball contributes to \(B_{i+1}\) — i.e., becomes the \((i+1)\)-th ball in some bin — only if both sampled bins already have load \(\geq i\). The probability of this event for a given ball is at most

\[\left(\frac{B_i}{n}\right)^2 \leq \frac{1}{\beta^{2^{i-1}}}.\]

By linearity of expectation, the expected number of balls placed into bins of load \(\geq i+1\) is

\[\mathbb{E}[B_{i+1}] \leq n \cdot \left(\frac{B_i}{n}\right)^2 = \frac{B_i^2}{n}.\]

This gives the recursion

\[B_{i+1} \approx \frac{B_i^2}{n}.\]

Solving the recursion. Write \(B_i = n / f_i\). Then:

\[\frac{n}{f_{i+1}} \approx \frac{(n/f_i)^2}{n} = \frac{n}{f_i^2} \implies f_{i+1} \approx f_i^2.\]

Starting from \(f_2 = 2\) (i.e., \(B_2 \leq n/2\)):

The maximum load is reached at the first \(i^*\) for which \(B_{i^*} < 1\), i.e., \(2^{2^{i^*-2}} > n\):

\[2^{i^*-2} > \log_2 n \implies i^* > 2 + \log_2\log_2 n.\]

Therefore the maximum load is at most \(\log_2\log_2 n + O(1)\) with high probability. \(\square\)

The recursion is illustrated by the following diagram:

graph TD
    B2["B_2 ≤ n/2"] -->|"B_{i+1} ≈ B_i^2/n"| B3["B_3 ≤ n/4"]
    B3 -->|"B_{i+1} ≈ B_i^2/n"| B4["B_4 ≤ n/16"]
    B4 -->|"B_{i+1} ≈ B_i^2/n"| B5["B_5 ≤ n/256"]
    B5 -->|"B_{i+1} ≈ B_i^2/n"| Bstar["B_{i*} lt 1"]
    Bstar --> Done["Max load ≤ log2 log2 n + O(1)"]

4.3 Stochastic Dominance and Formal Justification

To make the above argument rigorous, we need to handle the dependency between ball placements.

Lemma 6 (Stochastic Dominance). Let \(X_1, \ldots, X_n\) be Bernoulli random variables (not necessarily independent) where \(X_j = 1\) if the \(j\)-th ball lands in a bin of load \(\geq i+1\). Suppose that for each \(j\) and any history of the first \(j-1\) placements,

\[\Pr[X_j = 1 \mid X_1, \ldots, X_{j-1}] \leq p.\]

Then \(B_{i+1} = \sum_j X_j\) is stochastically dominated by \(\text{Bin}(n, p)\).

In other words, even though the \(X_j\) are dependent, an upper bound \(p\) on each conditional probability suffices to apply Chernoff bounds.

Applying the lemma. Given the history of placements, if currently \(B_i\) bins have load \(\geq i\), then the probability the next ball increases some bin’s load from \(i\) to \(i+1\) is at most \((B_i/n)^2\). As long as \(B_i \leq n/\beta^{2^{i-2}}\) (an event we condition on), Lemma 6 allows us to bound \(B_{i+1}\) by a binomial, and then apply Chernoff to show \(B_{i+1}\) is concentrated near its expectation \(n \cdot (B_i/n)^2 = B_i^2/n\).

A union bound over all \(O(\log\log n)\) levels completes the proof.

4.4 Extension to d Choices

The two-choice result generalizes naturally.

Theorem 3 (d Choices). When each ball samples \(d \geq 2\) bins uniformly at random and is placed in the least-loaded bin, the maximum load satisfies

\[\max_j \text{load}(j) \leq \frac{\ln\ln n}{\ln d} + O(1)\]

with high probability.

Proof sketch. The load-level recursion becomes \(B_{i+1} \approx B_i^d / n^{d-1}\). Writing \(B_i = n/f_i\) gives \(f_{i+1} \approx f_i^d\), so \(f_i \approx d^{d^{i-2}}\) (a tower with base \(d\)). The max level \(i^*\) satisfies \(d^{d^{i^*-2}} \approx n\), giving \(d^{i^*-2} \approx \log_d n\), so \(i^* \approx 2 + \log_d \log_d n = \ln\ln n / \ln d + O(1)\). \(\square\)

Key conclusion: Each additional choice reduces the exponent of the iterated logarithm by a factor of \(\ln d\). Even \(d = 2\) gives a superexponential speedup over \(d = 1\) (uniform hashing).

5. Exercises 📝

References