COMPX270 — Randomised and Advanced Algorithms
Chapter 3: Balls in Bins
Birthday Paradox, Coupon Collector, Load Balancing, and the Power of Two Choices
Stirling's approximation, harmonic numbers, Poisson distribution, binomial coefficient bounds
The Balls-in-Bins Framework
Setup: We have \(m\) balls and \(n\) bins. Each ball is thrown independently and uniformly at random into one of the \(n\) bins.
Despite its simplicity, this model captures a surprising range of real-world problems: hashing, task scheduling, resource allocation, distribution testing, and more.
Three Things We Care About
1. Collisions
How many pairs of balls share the same bin? Leads to the Birthday Paradox.
2. Coverage
How many balls until every bin has at least one? The Coupon Collector problem.
3. Maximum Load
What is the maximum number of balls in any bin? Load Balancing and the Power of Two Choices.
Collisions & the Birthday Paradox
Theorem 15 (Birthday Paradox)
If you gather 23 people in a room, then with probability at least 50% there will be two people sharing a birthday.
Theorem 16 (Exact Collision Probability)
The probability \(p_{m,n}\) of at least one collision when throwing \(m\) balls into \(n\) bins is:
\[p_{m,n} = 1 - \frac{n!}{n^m (n-m)!} = 1 - \frac{m!}{n^m}\binom{n}{m}\]For \(m = 23\) and \(n = 366\): \(p_{23,366} \approx 0.506 \geq 1/2\). ✓
Expected Number of Collisions
For each pair of balls \((i,j)\), define the indicator \(\mathbf{1}[X_i = X_j]\) where \(X_i\) is the bin of ball \(i\). Since balls are thrown independently and uniformly:
\[\Pr[X_i = X_j] = \frac{1}{n}\]By linearity of expectation:
\[c(m,n) = \mathbb{E}[C] = \sum_{(i,j) \text{ pair}} \Pr[X_i = X_j] = \binom{m}{2} \cdot \frac{1}{n}\]The expected number of collisions grows roughly as \(\frac{m^2}{2n}\). This becomes constant when \(m = \Theta(\sqrt{n})\), which is exactly when we should expect collisions to appear!
Variance: The "Magic Cancellation"
Even though the indicator variables \(\mathbf{1}[X_i = X_j]\) are not independent across pairs, the variance calculation yields a surprisingly clean result:
We compute \(\mathbb{E}[C^2]\) by expanding the double sum over pairs \((i,j)\) and \((k,\ell)\). There are three cases:
Case 1: Same pair \((i,j) = (k,\ell)\). Then \(\mathbf{1}[X_i = X_j]^2 = \mathbf{1}[X_i = X_j]\), so the contribution is \(\frac{1}{n}\). There are \(\binom{m}{2}\) such terms.
Case 2: Disjoint pairs \(\{i,j\} \cap \{k,\ell\} = \emptyset\). The indicators are independent, so the contribution is \(\frac{1}{n^2}\). There are \(\binom{m}{2}\binom{m-2}{2}\) such terms.
Case 3: Overlapping pairs (share exactly one element). Then \(\mathbf{1}[X_i = X_j]\mathbf{1}[X_k = X_\ell] = \mathbf{1}[X_i = X_j = X_k]\), and by uniformity:
\[\mathbb{E}[\mathbf{1}[X_i = X_j = X_k]] = \sum_{b=1}^{n} \Pr[X_i = b, X_j = b, X_k = b] = \frac{n}{n^3} = \frac{1}{n^2}\]There are \(6\binom{m}{3}\) such terms. Sanity check: \(\binom{m}{2} + \binom{m}{2}\binom{m-2}{2} + 6\binom{m}{3} = \binom{m}{2}^2\). ✓
Combining:
\[\mathbb{E}[C^2] = \binom{m}{2}\frac{1}{n} + \binom{m}{2}\binom{m-2}{2}\frac{1}{n^2} + 6\binom{m}{3}\frac{1}{n^2} = \binom{m}{2}\frac{1}{n}\!\left(1 - \frac{1}{n}\right) + \binom{m}{2}^2 \frac{1}{n^2}\]Therefore:
\[\operatorname{Var}[C] = \mathbb{E}[C^2] - \mathbb{E}[C]^2 = \binom{m}{2}\frac{1}{n}\!\left(1 - \frac{1}{n}\right)\]This is exactly what we'd get if the indicators were independent! The key is that the overlapping case contributes \(\frac{1}{n^2}\), the same as the disjoint case, thanks to the uniformity of bin assignments. □
Theorem 17 (Collision Threshold)
The probability of at least one collision when throwing \(m\) balls independently and uniformly into \(n\) bins is:
- Less than 1/2 when \(m \leq \sqrt{n}\) (by Markov: \(\Pr[C \geq 1] \leq \mathbb{E}[C] \leq m^2/(2n)\))
- At least 1/2 when \(m \geq \sqrt{3n}\) (by Chebyshev: \(\Pr[C = 0] \leq \operatorname{Var}[C]/\mathbb{E}[C]^2 \leq 1/\mathbb{E}[C] \leq 1/2\))
Therefore the collision threshold is \(m = \Theta(\sqrt{n})\).
Interactive: Birthday Paradox Simulation
Choose the number of people and run experiments to observe when birthday collisions occur.
The Coupon Collector Problem
Problem: How many balls \(M(n)\) do we need to throw (uniformly at random into \(n\) bins) before every bin contains at least one ball?
Equivalently: how many cereal boxes must you buy to collect all \(n\) different coupons?
Theorem 18 (Coupon Collector)
The expected number of balls needed to hit all \(n\) bins is:
\[M(n) = nH_n = n\sum_{k=1}^{n} \frac{1}{k} = n\ln n + \gamma n + O(1)\]where \(H_n\) is the \(n\)-th harmonic number and \(\gamma \approx 0.5772\) is the Euler–Mascheroni constant.
Key idea: Decompose \(m(n) = T_1 + T_2 + \cdots + T_n\), where \(T_i\) is the number of balls needed, after hitting \(i-1\) distinct bins, to hit a new one.
\(T_1 = 1\) always (the first ball always hits a new bin). After hitting \(i-1\) bins, the probability of hitting a new bin with each ball is:
\[p_i = \frac{n - (i-1)}{n} = \frac{n - i + 1}{n}\]So \(T_i \sim \text{Geometric}(p_i)\), and \(\mathbb{E}[T_i] = \frac{1}{p_i} = \frac{n}{n-i+1}\).
By linearity of expectation:
\[M(n) = \sum_{i=1}^{n} \mathbb{E}[T_i] = \sum_{i=1}^{n} \frac{n}{n-i+1} = n\sum_{j=1}^{n} \frac{1}{j} = nH_n \quad \square\]Theorem 19 (Variance Bound)
The variance of the number of balls needed satisfies:
\[\operatorname{Var}[m(n)] \leq \frac{\pi^2}{6} n^2\]The crucial observation is that \(T_1, \ldots, T_n\) are independent (by the memorylessness property of the geometric distribution). Therefore:
\[\operatorname{Var}[m(n)] = \sum_{i=1}^{n} \operatorname{Var}[T_i]\]Since \(T_i \sim \text{Geometric}(p_i)\), its variance is \(\frac{1-p_i}{p_i^2} \leq \frac{1}{p_i^2} = \frac{n^2}{(n-i+1)^2}\).
\[\operatorname{Var}[m(n)] \leq n^2 \sum_{i=1}^{n} \frac{1}{(n-i+1)^2} = n^2 \sum_{j=1}^{n} \frac{1}{j^2} \leq n^2 \cdot \frac{\pi^2}{6}\]using the Basel identity \(\sum_{k=1}^{\infty} \frac{1}{k^2} = \frac{\pi^2}{6}\).
By Chebyshev's inequality, this gives us:
\[m(n) = nH_n \pm O(n) = n\ln n \pm O(n)\]with probability at least 0.99. □
Interactive: Coupon Collector Simulation
Choose the number of bins \(n\), then run the experiment to see how many balls are needed to fill all bins.
Load Balancing
Problem: Throw \(n\) balls into \(n\) bins uniformly and independently at random. What is the expected maximum load \(L(n) = \mathbb{E}[\max_{1 \leq i \leq n} L_i]\)?
Each bin \(L_i \sim \text{Bin}(n, 1/n)\), so \(\mathbb{E}[L_i] = 1\) and \(\operatorname{Var}[L_i] = n \cdot \frac{1}{n}(1 - \frac{1}{n}) \leq 1\).
Simple Bound via Chebyshev + Union Bound
By Chebyshev's inequality with \(t = \sqrt{2n}\):
\[\Pr\!\left[L_i \geq 1 + \sqrt{2n}\right] \leq \frac{\operatorname{Var}[L_i]}{2n} \leq \frac{1}{2n}\]Taking a union bound over all \(n\) bins:
\[\Pr\!\left[\max_i L_i \geq 1 + \sqrt{2n}\right] \leq n \cdot \frac{1}{2n} = \frac{1}{2}\]So the max load is \(O(\sqrt{n})\) with constant probability. But can we do better?
Theorem 20 (Maximum Load)
The expected maximum load when throwing \(n\) balls uniformly and independently into \(n\) bins satisfies:
\[L(n) = \Theta\!\left(\frac{\log n}{\log \log n}\right)\]Step 1: Bound the probability that a single bin has load \(\geq \ell\).
For a fixed bin \(i\), allowing double-counting over all subsets of exactly \(\ell\) balls:
\[\Pr[L_i \geq \ell] \leq \binom{n}{\ell} \frac{1}{n^\ell}\]Using the binomial coefficient bound (Fact 20.1): \(\binom{n}{\ell} \leq \left(\frac{en}{\ell}\right)^\ell\):
\[\Pr[L_i \geq \ell] \leq \left(\frac{en}{\ell}\right)^\ell \cdot \frac{1}{n^\ell} = \frac{e^\ell}{\ell^\ell}\]Step 2: Union bound over all bins.
\[\Pr[L \geq \ell] \leq \frac{n \cdot e^\ell}{\ell^\ell}\]Step 3: Split the expectation sum.
Let \(\ell^*(n)\) be the smallest \(\ell\) such that \(\ell^\ell e^{-\ell} \geq n\). For \(\ell \leq \ell^*\), use the trivial bound \(\Pr[L \geq \ell] \leq 1\). For \(\ell > \ell^*\), use the union bound.
\[L(n) = \sum_{\ell=1}^{\infty} \Pr[L \geq \ell] \leq \ell^*(n) + \sum_{\ell=\ell^*+1}^{\infty} \frac{ne^\ell}{\ell^\ell}\]The tail sum is bounded by a geometric series that sums to at most 1 (since \(\ell^* \geq 2e\)):
\[L(n) \leq \ell^*(n) + 1\]Step 4: Bound \(\ell^*(n)\).
From \((\ell^* - 1)^{\ell^*-1} e^{-(\ell^*-1)} < n\), taking logarithms: \((\ell^*-1)\log(e^{-1}(\ell^*-1)) < \log n\). One can show:
\[\ell^*(n) = \Theta\!\left(\frac{\log n}{\log \log n}\right)\]giving \(L(n) = O\!\left(\frac{\log n}{\log \log n}\right)\). □
Alternative MGF Proof (Advanced)
Using Jensen's inequality and the moment-generating function trick:
\[L(n) = \frac{1}{t}\mathbb{E}\!\left[\ln e^{t \max_i L_i}\right] \leq \frac{1}{t}\ln\!\left(n \cdot \mathbb{E}[e^{tL_1}]\right)\]For \(L_1 \sim \text{Bin}(n, 1/n)\), the MGF is \(\mathbb{E}[e^{tL_1}] = \left(1 + \frac{e^t - 1}{n}\right)^n\). Using \(\ln(1+x) \leq x\):
\[L(n) \leq \frac{1}{t}\left(\ln n + e^t - 1\right)\]Balancing the two terms by setting \(t = \ln\ln(en)\) gives:
\[L(n) \leq \frac{2\ln n}{\ln\ln(en)}\]Interactive: Load Balancing Simulation
Throw \(n\) balls into \(n\) bins and observe the maximum load.
The Power of Two Choices
Strategy: Instead of throwing each ball into a uniformly random bin, each ball selects two bins uniformly at random and goes into the least loaded of the two (ties broken arbitrarily).
This seemingly minor change has a dramatic effect on the maximum load.
Theorem 21 (Power of Two Choices)
The expected maximum load \(\hat{L}(n)\) when throwing \(n\) balls into \(n\) bins using the "best of two choices" strategy satisfies:
\[\hat{L}(n) = \log\log n + O(1)\]Intuition: The Recurrence
Let \(B_i\) denote the number of bins with at least \(i\) balls. The key insight is that \(B_2 \leq n/2\) (otherwise we'd need more than \(n\) balls), and we get the recurrence:
\[B_{i+1} \leq \frac{B_i^2}{n}\]Starting from \(B_2 \leq n/2\), solving by induction gives \(B_i \leq \frac{n}{2^{2^{i-2}}}\). This reaches 1 when:
\[2^{2^{i-2}} \geq n \implies i \leq \log_2 \log_2 n + 2\]So the maximum load is at most \(\log\log n + O(1)\). This is exponentially smaller than the \(\Theta(\frac{\log n}{\log\log n})\) bound for uniform allocation!
| Strategy | Expected Max Load | Growth |
|---|---|---|
| Uniform (1 choice) | \(\Theta\!\left(\dfrac{\log n}{\log\log n}\right)\) | Slow |
| Best of 2 choices | \(\log\log n + O(1)\) | Very slow (exponential improvement!) |
Interactive: Uniform vs Two-Choices Comparison
Compare the maximum load under uniform random allocation versus the power of two choices.
Tutorial Problems
Work through these problems to reinforce your understanding of the balls-in-bins model.
Problem 1 Warm-up
Generalise Eq. (22) of the lecture notes to \(m > n\) balls, to compute \(\mathbb{E}[\text{empty bins after } m \text{ balls}]\), and solve for \(m\) to get this expectation to be at most \(1/2\). Show you retrieve the \(\Theta(n \log n)\) bound.
By linearity of expectation:
\[\mathbb{E}[\text{empty bins after } m \text{ balls}] = \sum_{i=1}^{n} \Pr[\text{bin } i \text{ empty}] = n\!\left(1 - \frac{1}{n}\right)^m \leq n \cdot e^{-m/n}\]Setting \(n \cdot e^{-m/n} \leq \frac{1}{2}\) and taking logarithms:
\[\ln(2n) \leq \frac{m}{n} \implies m = \Omega(n \log n)\]So we need \(m = \Theta(n \log n)\) balls to expect all bins to be covered. □
Problem 2 Warm-up
Use Chebyshev's inequality to bound the probability that \(m(n)\), the number of balls needed to hit every bin at least once, is greater than \(\alpha n \ln n\) (for \(\alpha > 1\)).
We have \(\mathbb{E}[m(n)] = nH_n = n\log n + O(n) \leq 2n\log n\) and \(\operatorname{Var}[m(n)] \leq \frac{\pi^2}{6}n^2\).
By Chebyshev with \(t = (\alpha - 2)n\log n\):
\[\Pr[m \geq \alpha n\log n] \leq \Pr[|m - \mathbb{E}[m]| \geq t] \leq \frac{\operatorname{Var}[m]}{t^2} = \frac{\pi^2 n^2/6}{((\alpha-2)n\log n)^2} = O\!\left(\frac{1}{\log^2 n}\right)\]This goes to zero, but only polynomially in \(\log n\). □
Problem 3 Warm-up
Show that the expected number of balls \(M_2(n)\) needed before each bin contains at least two balls is \(\Theta(n \log n)\).
Lower bound: \(M_2(n) \geq M(n) = \Theta(n\log n)\), since to have 2 balls in each bin we first need at least 1.
Upper bound: Wait until each bin has at least one ball (expected time \(M(n)\)). Then "restart from scratch" — forget all current loads, and wait until each bin receives at least one new ball. This second stage also takes \(M(n)\) in expectation. After both stages, each bin has at least \(1 + 1 = 2\) balls.
Therefore \(M_2(n) \leq 2M(n) = O(n\log n)\), giving \(M_2(n) = \Theta(n\log n)\). □
Problem 4 Problem Solving
Let \(c > 0\) be a constant. When throwing \(m = cn\ln n\) balls into \(n\) bins, show that with high probability every bin has \(\Theta(\ln n)\) balls.
(a) Compute \(\mathbb{E}[L_i]\) and \(\operatorname{Var}[L_i]\). Use Chebyshev to bound \(\Pr\!\left[L_i \notin \left[\frac{c}{2}\ln n, \frac{3c}{2}\ln n\right]\right]\). Is it enough after a union bound?
(b) Use a Chernoff bound to show \(\Pr\!\left[L_i \notin \left[\frac{c}{2}\ln n, \frac{3c}{2}\ln n\right]\right] \leq \frac{2}{n^{c/12}}\).
(c) Pick a suitable \(c\) to conclude that all loads are \(\Theta(\ln n)\) with probability \(\geq 1 - 2/n\).
Since \(L_i \sim \text{Bin}(m, 1/n)\), we have \(\mathbb{E}[L_i] = c\ln n\) and \(\operatorname{Var}[L_i] \leq c\ln n\).
(a) Chebyshev gives \(\Pr[|L_i - c\ln n| \geq \frac{c}{2}\ln n] \leq \frac{4}{c\ln n}\). After a union bound over \(n\) bins, we get \(\frac{4n}{c\ln n}\), which is vacuous (greater than 1). Not enough!
(b) By the Chernoff bound (with \(\delta = 1/2\)): \(\Pr[|L_i - c\ln n| \geq \frac{c}{2}\ln n] \leq 2\exp\!\left(-\frac{c\ln n}{12}\right) = \frac{2}{n^{c/12}}\).
(c) Union bound: \(\Pr[\exists i: L_i \text{ bad}] \leq \frac{2n}{n^{c/12}} = \frac{2}{n^{c/12 - 1}}\). Choosing \(c = 24\) gives \(\leq 2/n\). □
Problem 5 Problem Solving
Suppose bin \(i\) has probability \(p_i\) (with \(\sum p_i = 1\)) instead of \(1/n\).
(a) What is the probability of a collision when \(m = 2\)?
(b) What is the expected number of collisions \(\mathbb{E}[c(m,n)]\) for general \(m\)?
(a) The probability of a collision with 2 balls is:
\[\Pr[\text{collision}] = \sum_{i=1}^{n} p_i^2 = \|p\|_2^2\](b) By linearity of expectation over all \(\binom{m}{2}\) pairs:
\[\mathbb{E}[c(m,n)] = \binom{m}{2} \|p\|_2^2\]Sanity check: for the uniform distribution \(p_i = 1/n\), we get \(\|p\|_2^2 = 1/n\), recovering the standard result. □
Problem 6 Problem Solving
(Guided) Sketch a proof of Theorem 21 (Power of Two Choices):
(a) Explain why \(B_2 \leq n/2\).
(b) Argue that \(B_i \leq B'_i\) where \(B'_i\) counts balls that were \(i\)-th or more in their bin when thrown.
(c)–(d) Show \(\mathbb{E}[B'_{i+1}] \leq B_i^2/n\) and derive the recurrence \(B_{i+1} \leq B_i^2/n\).
(e)–(f) Solve the recurrence to get \(B_i \leq n/2^{2^{i-2}}\) and conclude max load \(\leq \log\log n + 2\).
(a) If \(B_2 > n/2\), then more than \(n/2\) bins have \(\geq 2\) balls, meaning \(> n\) balls total. Contradiction since we only threw \(n\) balls.
(b) Every bin with \(\geq i\) balls after all throws has a ball that was the \(i\)-th or more when thrown, so \(B_i \leq B'_i\).
(c) At any time step, at most \(B_i\) bins have \(\geq i\) balls. With two choices, the probability a ball goes into such a bin is \(\leq (B_i/n)^2\). Summing over \(n\) balls: \(\mathbb{E}[B'_{i+1}] \leq n \cdot (B_i/n)^2 = B_i^2/n\).
(d)–(e) Assuming \(B_i \approx \mathbb{E}[B_i]\) (handwaving), the recurrence \(B_{i+1} \leq B_i^2/n\) with \(B_2 \leq n/2\) gives by induction:
\[B_i \leq \frac{n}{2^{2^{i-2}}}\](f) Setting \(B_i \geq 1\): \(2^{2^{i-2}} \leq n \implies i \leq \log_2\log_2 n + 2\). So the max load is at most \(\log_2\log_2 n + 2 = \log\log n + O(1)\). □
Problem 7 Warm-up
Show that for large enough \(n\), the expected number of empty bins when throwing \(n\) balls into \(n\) bins approaches \(n/e\).
The expected number of empty bins is \(n(1 - 1/n)^n\). It remains to show:
\[\lim_{n \to \infty} \left(1 - \frac{1}{n}\right)^n = e^{-1}\]Write \((1 - 1/n)^n = e^{n\ln(1 - 1/n)}\). Setting \(f(x) = \ln(1-x)\), we need \(\lim_{n\to\infty} \frac{\ln(1-1/n)}{1/n} = f'(0) = -1\), giving the limit \(e^{-1}\).
Therefore \(\mathbb{E}[\text{empty bins}] = n(1 - 1/n)^n \to n/e\). □
Problem 8 Problem Solving
You play the Australian 1st Division lottery: guess 6 numbers out of 45.
(a) What is the probability \(p\) that a single ticket wins?
(b) With a \(\$1{,}000{,}000\) prize and \(\$0.60\) ticket cost, what is the expected reward for 1 ticket? For 100 tickets?
(c) You suspect half the outcomes never appear. How many tickets to get statistical evidence?
(a) \(p = \frac{1}{\binom{45}{6}} = \frac{1}{8{,}145{,}060}\).
(b) Expected reward for 1 ticket: \(10^6 \cdot p - 0.60 \approx 0.123 - 0.60 \approx -\$0.48\). For 100 tickets: \(\approx -\$48\). The expected gain is negative (as with all real lotteries).
(c) To distinguish the uniform distribution over all \(n = \binom{45}{6}\) outcomes from a distribution supported on \(n/2\) outcomes, you need to observe a collision (by the birthday paradox). This requires \(\Omega(\sqrt{n}) \approx \Omega(2{,}854)\) tickets. Without collisions, the observed sequences are equally consistent with both hypotheses. □
Problem 9 Advanced
(Poissonization) Instead of throwing \(m\) balls, draw \(M \sim \text{Poi}(m)\) and throw \(M\) balls. Let \(N_j\) be the count in bin \(j\).
(a) Show \(N_1, \ldots, N_n\) are independent with \(N_j \sim \text{Poi}(mp_j)\).
(b) Rewrite the collision count \(\tilde{c}(m,n)\) in terms of the \(N_j\).
(c) Compute \(\mathbb{E}[\tilde{c}(m,n)]\).
(d) Compute \(\operatorname{Var}[\tilde{c}(m,n)]\).
(a) By the multinomial theorem and the Poisson splitting property: if the total count is \(M \sim \text{Poi}(m)\), then \(N_j \sim \text{Poi}(mp_j)\) independently. The joint distribution factors as a product of marginals.
(b) Collisions in bin \(j\) equal \(\binom{N_j}{2}\), so \(\tilde{c}(m,n) = \sum_{j=1}^{n} \binom{N_j}{2} = \sum_{j=1}^{n} \frac{N_j^2 - N_j}{2}\).
(c) Using Poisson moments (\(\mathbb{E}[N_j^2 - N_j] = (mp_j)^2\)):
\[\mathbb{E}[\tilde{c}(m,n)] = \sum_{j=1}^{n} \frac{(mp_j)^2}{2} = \frac{m^2}{2}\|p\|_2^2\](d) By independence of the \(N_j\):
\[\operatorname{Var}[\tilde{c}(m,n)] = \frac{1}{4}\sum_{j=1}^{n} \operatorname{Var}[N_j^2 - N_j] = \frac{1}{4}m^4\|p\|_4^4 + m^3\|p\|_3^3 + \frac{1}{4}m^2\|p\|_2^2\]□
Problem 10 Advanced
Using the MGF-based approach from the lecture, show that if \(X_1, \ldots, X_n\) are (not necessarily independent) Gaussian r.v.s with mean 0 and variance \(\sigma^2\), then:
\[\mathbb{E}\!\left[\max_{1 \leq i \leq n} X_i\right] \leq \sqrt{2\sigma^2 \ln n}\]As a corollary, show \(\mathbb{E}[\max_i |X_i|] \leq \sqrt{2\sigma^2 \ln(2n)}\).
Following the Jensen + MGF approach:
\[\mathbb{E}\!\left[\max_i X_i\right] \leq \frac{1}{t}\ln\!\left(n \cdot \mathbb{E}[e^{tX_1}]\right) = \frac{1}{t}\ln\!\left(n \cdot e^{\sigma^2 t^2/2}\right) = \frac{\ln n}{t} + \frac{\sigma^2 t}{2}\]Balancing the two terms: set \(t = \sqrt{2\ln n/\sigma^2}\), giving:
\[\mathbb{E}\!\left[\max_i X_i\right] \leq \sqrt{2\sigma^2 \ln n}\]Corollary: \(\max_i |X_i| = \max_i \max(X_i, -X_i)\). Since \(-X_i \sim \mathcal{N}(0, \sigma^2)\) as well, we can apply the bound to \(2n\) variables \(X_1, -X_1, \ldots, X_n, -X_n\) (independence is not required!):
\[\mathbb{E}\!\left[\max_i |X_i|\right] \leq \sqrt{2\sigma^2 \ln(2n)} \quad \square\]Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).