Skip to main content

Data Structures · Hash tables and probabilistic performance

Throw n balls independently and uniformly into n bins

Problem

Data Structures practice problem

Throw nn balls independently and uniformly into nn bins. Let XiX_i be the number of balls in bin ii, and let X=max⁡iXiX=\max_i X_i. You may use linearity of expectation and Markov’s inequality. You may not use Chernoff bounds, moment-generating functions, or the known Θ(log⁡n/log⁡log⁡n)\Theta(\log n/\log\log n) maximum-load theorem.

(a) Prove that E[Xi(Xi−1)]=1−1/n\mathbb{E}[X_i(X_i-1)]=1-1/n for each ii.

(b) Prove that E[Xi2]≤2\mathbb{E}[X_i^2]\le 2.

(c) Let YY be the number of bins with Xi≥nX_i\ge\sqrt n. Using Markov’s inequality on a random variable built from the XiX_i (specify it), prove that Pr⁡[X≥n]=O(1/n)\Pr[X\ge\sqrt n]=O(1/\sqrt n) for n≥1n\ge 1, or give any bound of the form Pr⁡[X≥n]≤c/n\Pr[X\ge\sqrt n]\le c/\sqrt n with an explicit constant cc.

(d) Deduce that E[X]=O(n)\mathbb{E}[X]=O(\sqrt n). (Use X≤nX\le n always, and split the expectation according to whether X≥nX\ge\sqrt n.)

Hint

Hint

Xi(Xi−1)X_i(X_i-1) counts ordered pairs of distinct balls in bin ii.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Data Structures sample problem: Try the free sample problem.

More Data Structures practice problems

Back to Data Structures

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.