🎩 Classic puzzles

These ten puzzles come up again and again in quant and ML interviews. Each one teaches a reusable trick: complements, recurrences, linearity of expectation, symmetry, counting information, or Bayes. Play with every widget. Your gut is usually wrong the first time, and seeing the simulation is what fixes it.

PuzzleAnswer to rememberThe trick
Birthday23 people → 50.7%complement; collisions start around $\sqrt d$
Gambler's ruinfair: $a/N$, duration $a(N-a)$first-step recurrence, martingale
Random walkspread $\sim\sqrt n$variances add
Coupon collector$nH_n\approx n\ln n$split into geometric phases
Weighing coins$\lceil\log_3 k\rceil$ weighingscount the information
Reservoir samplingreplace with prob $1/n$induction
Secretaryskip $n/e$, win w.p. $1/e$sum over best's position
Monty Hallswitch: $2/3$Bayes; Monty's choice carries information
Longest run$\approx\log_2 n$expected # of runs of length $\ell$ ≈ 1
Balls into bins37% / 37% / 26%indicators, $(1-1/m)^m\to 1/e$

Birthday problem

Problem. How many people $n$ do you need in a room before the probability that two of them share a birthday exceeds 50%? (Ignore leap years and assume birthdays are uniform over $d=365$ days.)

The trap is thinking about your birthday. A collision can happen between any pair, and the number of pairs grows like $n^2$: with 23 people there are $\binom{23}{2}=253$ pairs. Each pair matches with probability $1/365$, so the expected number of matching pairs is $253/365\approx 0.69$. That is already close to 1, so a coin-flip chance of at least one match is not surprising.

Solution. "At least one collision" is messy, but its complement "all birthdays different" is easy. Seat people one at a time. Each new person must avoid all the birthdays already taken:

$$P(\text{collision}) = 1 - P(\text{all unique}),$$ $$P(\text{all unique})=\frac{d}{d}\cdot\frac{d-1}{d}\cdot\frac{d-2}{d}\cdots\frac{d-n+1}{d}=\frac{d!}{(d-n)!\, d^n}.$$

Plugging in $d=365$: $n=22$ gives 47.6%, and $n=23$ gives 50.7%. So the answer is 23.

Using $1-x\approx e^{-x}$ on each factor, $\prod_{i=0}^{n-1}\big(1-\tfrac id\big)\approx e^{-\sum i/d}=e^{-n(n-1)/(2d)}$, so

$$P(\text{collision})\approx 1-e^{-n(n-1)/(2d)}.$$

Setting this to $\tfrac12$ gives $n\approx\sqrt{2d\ln 2}\approx 1.18\sqrt d$. Collisions show up after about $\sqrt d$ draws, not $d/2$. For $d=365$ this predicts $22.5$.

Fill the room
Drag $n$ to move along the exact curve (solid) and the $e^{-n(n-1)/2d}$ approximation (dashed). Click New room to give $n$ random people birthdays on a 365-day calendar. Days with two or more people light up in pink. Simulate 2,000 rooms checks the curve empirically.

"Someone shares my birthday" is a different question. That probability is $1-(364/365)^{n-1}$, which needs $n\approx 254$ people to reach 50%. Read the question carefully.

The same math is behind hash collisions, where a $b$-bit hash collides after about $2^{b/2}$ items (the "birthday attack"), and behind estimating population size by counting repeats. Common follow-ups: the expected number of shared pairs is $\binom n2/d$ (by linearity), and the expected number of people until the first repeat is about $\sqrt{\pi d/2}\approx 24.6$.

With $d$ equally likely values, roughly how many draws until you probably see a repeat if $d$ is multiplied by 100?
  • 100× more draws
  • 10× more draws
  • About the same
  • $\log 100$ more draws
The threshold scales like $\sqrt d$, so 100× more values needs only $\sqrt{100}=10$× more draws.

Gambler's ruin

Problem. You start with $a$ dollars. Each round you win 1 dollar with probability $p$ and lose 1 dollar with probability $q=1-p$. You stop when you reach $N$ dollars (you win) or 0 dollars (you're ruined). What is the probability that you reach $N$?

This is a random walk with absorbing barriers at $0$ and $N$. In a fair game your expected wealth never changes, so the only way to "average out" to your starting $a$ is to hit $N$ with probability $a/N$. If the game is even slightly unfair, the drift wins over long games and ruin becomes almost certain, especially when $N$ is large.

Setup (first-step analysis). Let $P_i$ be the probability of reaching $N$ starting from $i$ dollars. Condition on the first round:

$$P_i = p\,P_{i+1} + q\,P_{i-1}\quad(0\lt i\lt N),\qquad P_0=0,\ P_N=1.$$

This is a second-order linear recurrence with two boundary conditions. See first-step analysis and absorbing Markov chains for the general pattern.

The original notes switch between $P_i$ and $q_i$ for the same quantity, and write the boundary condition as "$q_i=0$" instead of $P_0=0$. Its dollar amounts (written with a literal dollar sign right before the math) also render as broken TeX. Here $P_i$ is the win probability throughout, $q=1-p$ is the loss probability, and amounts are written in words.

Fair game ($p=\tfrac12$): $P_a=a/N$

Approach 1: expected value at the stopping time. Let $T$ be the time you stop and $W_T$ your wealth then. Each bet has zero expected gain, so $\E[W_T]=a$. But $W_T$ is either $N$ (with probability $P_a$) or $0$, so

$$\E[W_T]=P_a\cdot N + (1-P_a)\cdot 0 = P_a N \;\Longrightarrow\; P_a=\frac aN.$$

Approach 2: solve the recurrence.

$$P_i=\tfrac12P_{i-1}+\tfrac12P_{i+1}\;\Longrightarrow\;P_{i+1}-P_i=P_i-P_{i-1}.$$

All consecutive differences are equal, so $P_i$ is a linear function of $i$. With $P_0=0$ and $P_N=1$ we get $P_i=i/N$.

Martingale. A sequence $M_0,M_1,\dots$ is a martingale if, given the whole past, the next value is expected to equal the current one:

$$\E[M_{n+1}\mid M_0,\dots,M_n]=M_n.$$

Taking expectations gives $\E[M_0]=\E[M_1]=\cdots$. A fair gambler's wealth is the classic example. The optional stopping theorem says $\E[M_T]=\E[M_0]$ at a stopping time $T$, provided $T$ is well-behaved (for example bounded, or bounded increments with $\E[T]<\infty$). That is exactly what Approach 1 used.

The original defines a martingale only as "$\E[M_1]=\cdots=\E[M_n]$". That's a consequence of being a martingale, not the definition. For example, $M_n=(-1)^n Z$ with $Z\sim\N(0,1)$ has constant mean 0 but is not a martingale. The conditional definition above is the correct one.

Expected duration. In the fair game the expected number of rounds starting from $i$ is $h_i=i(N-i)$. It is tricky to derive, but easy to verify. First-step analysis gives $h_i=1+\tfrac12h_{i-1}+\tfrac12h_{i+1}$ with $h_0=h_N=0$, and

$$1+\tfrac12\big[(i-1)(N-i+1)+(i+1)(N-i-1)\big]=1+\tfrac12\big[2i(N-i)-2\big]=i(N-i).\ \checkmark$$

Unfair game ($p\ne\tfrac12$)

$$P_a=\frac{1-(q/p)^a}{1-(q/p)^N},\qquad \E[T]=\frac{a}{q-p}-\frac{N}{q-p}\cdot\frac{1-(q/p)^a}{1-(q/p)^N}.$$
Proof: solve the recurrence with a characteristic equation

Try $P_i=x^i$ in $P_i=pP_{i+1}+qP_{i-1}$: $\;px^2-x+q=0$, which has roots $x=1$ and $x=q/p$. The general solution is $P_i=A+B(q/p)^i$. Then $P_0=0$ gives $A=-B$, and $P_N=1$ gives $B=-1/(1-(q/p)^N)$, so

$$P_i=\frac{1-(q/p)^i}{1-(q/p)^N}.$$

Martingale alternative: $(q/p)^{W_n}$ is a martingale, because $\E[(q/p)^{W_{n+1}}\mid W_n]=(q/p)^{W_n}\big(p\cdot\tfrac qp+q\cdot\tfrac pq\big)=(q/p)^{W_n}$. Optional stopping then gives $(q/p)^a=P_a(q/p)^N+(1-P_a)$, which is the same answer.

For the duration, $W_n-n(p-q)$ is a martingale, so $a=\E[W_T]-(p-q)\E[T]=NP_a-(p-q)\E[T]$. Solving for $\E[T]$ gives the formula above.

Play the gambler
Each path is one game: wealth over time until it hits $0$ (ruin) or $N$ (win). Play 1 game animates a single path. Run 2,000 games compares the empirical win rate and average duration with the formulas. Try $p=0.49$ with $N=40$: a 1% edge for the house is brutal. The lower plot shows $P_a$ for every starting point, with your empirical estimate as a dot.

Follow-ups to expect: (1) A symmetric walk starting at 0 needs on average $N^2$ steps to hit $\pm N$. That's gambler's ruin with $a=N$ on $[0,2N]$, so $a(2N-a)=N^2$. (2) Against an infinitely rich casino ($N\to\infty$) with $p\le\tfrac12$ you are ruined with probability 1. With $p>\tfrac12$ you survive forever with probability $1-q/p$.

Fair game, you start with 10 dollars and stop at 0 or 30 dollars. What are the win probability and expected number of rounds?
  • $1/2$ and $300$
  • $1/3$ and $100$
  • $1/3$ and $200$
  • $1/3$ and $300$
$P=a/N=10/30=1/3$ and $\E[T]=a(N-a)=10\cdot 20=200$.

Random walk

Setup. The simple symmetric random walk is $S_n=X_1+\cdots+X_n$, where each step $X_i=\pm1$ with equal probability, independently.

Mean
$\E[S_n]=n\E[X_i]=0$
Variance
$\Var(S_n)=n$
Typical distance
$\sim\sqrt n$

Each step has $\Var(X_i)=\E[X_i^2]-(\E[X_i])^2=1-0=1$. The steps are independent, so variances add:

$$\Var(S_n)=\sum_{i=1}^n\Var(X_i)=n.$$

So the typical distance from the origin, measured by the standard deviation, grows like $\sqrt n$, not $n$. By the CLT, $S_n/\sqrt n\to\N(0,1)$, and so about 68% of walks end within $\pm\sqrt n$.

Steps cancel each other out. After 10,000 steps you are typically only about 100 steps from home. Walking 4× as long only doubles your typical distance.

Biased walk. If $X_i=+1$ with probability $p$ and $-1$ otherwise,

$$\E[S_n]=n\big(p\cdot1+(1-p)(-1)\big)=n(2p-1),\qquad \Var(S_n)=4np(1-p).$$

The drift grows like $n$ but the noise only like $\sqrt n$, so any bias eventually dominates. That is the reason the unfair gambler is doomed.

A cloud of random walks
Each faint line is one walk. The shaded band is mean ± 1 sd, and the dashed lines are ± 2 sd, which for $p=\tfrac12$ is $\pm\sqrt n$ and $\pm2\sqrt n$. Move $p$ away from $0.5$ to see drift overtake the noise.

Facts worth knowing: $\E|S_n|\approx\sqrt{2n/\pi}\approx0.8\sqrt n$. The 1-D and 2-D symmetric walks return to the origin with probability 1 (they are recurrent), while in 3-D the return probability is only about 34%. Even though returning is certain in 1-D, the expected time to return is infinite.

Coupon collector

Problem. There are $n$ types of coupons. Each cereal box contains one coupon chosen uniformly at random. On average, how many boxes do you buy to collect all $n$ types?

The first few coupons are easy because almost every box gives you something new. The last coupon is painful: each box has only a $1/n$ chance of being the missing one, so you wait $n$ boxes on average just for it. Most of the time is spent at the end.

Solution: split the wait into phases. Phase $k$ (for $k=0,1,\dots,n-1$) is the stretch during which you have exactly $k$ distinct types. Each box is new with probability $\frac{n-k}{n}$, so the phase length is geometric:

$$X_k\sim\Geom\!\Big(\frac{n-k}{n}\Big),\qquad \E[X_k]=\frac{n}{n-k}.$$

By linearity of expectation, the total time $X=\sum_k X_k$ has

$$\E[X]=\sum_{k=0}^{n-1}\frac{n}{n-k}=n\sum_{j=1}^n\frac1j=n\,H_n,$$

where $H_n=1+\tfrac12+\tfrac13+\cdots+\tfrac1n\approx\ln n+0.577$ is the $n$-th harmonic number. The final phase alone takes $n$ boxes in expectation.

Mean
$nH_n\approx n\ln n+0.577n$
Variance
$\sum_k\frac{1-p_k}{p_k^2}\le\frac{\pi^2}{6}n^2$
Examples
$n=6$: 14.7, $n=50$: 225
Collect them all
Open boxes one at a time or press Auto. The phase bar shows how long each phase lasted: phase $k$ is the wait for the $(k+1)$-th new type. The outlined boxes show the expected lengths $n/(n-k)$, and you can see the last few phases dominate. Run 2,000 collections builds a histogram of the total.

The plot above shows $nH_n$ against $n\ln n$ and $n$. The gap $nH_n-n\ln n\approx0.577n$ grows linearly, which is small next to $n\ln n$. That is why the answer is often quoted as "$\Theta(n\log n)$".

Variants you may get: (1) the expected number of distinct types after $m$ boxes is $n\big(1-(1-1/n)^m\big)$, by indicators. (2) To collect only half the types takes about $n\ln2\approx0.69n$ boxes, while the second half takes about $n\ln(n/2)$. (3) The expected wait to see all 6 faces of a die is $6H_6=14.7$ rolls.

Information-theoretic puzzles

The principle: count the information. If you need to tell apart $k$ possibilities and each test has $m$ possible outcomes, then $t$ tests can produce at most $m^t$ distinct outcome sequences. You need $m^t\ge k$, so

$$t\ \ge\ \lceil\log_m k\rceil.$$

This is a lower bound. Whether some strategy actually reaches it depends on the constraints of the problem. To reach it, every test must split the remaining possibilities into $m$ groups that are as equal as possible.

Classic: 9 coins, one is heavier, you have a balance and 2 weighings. A balance has 3 outcomes (left heavy, right heavy, balanced), and $\lceil\log_3 9\rceil=2$, so 2 weighings might be enough. They are:

  1. Split into 3 groups of 3 and weigh group A against group B.
    • Left side heavy → the counterfeit is in A.
    • Right side heavy → the counterfeit is in B.
    • Balanced → the counterfeit is in the left-out group C.
  2. Take the 3 suspects and weigh one against another. Same logic: the heavier one is fake, or if they balance it's the third coin.

Weighing 4 vs 4 feels like it uses "more coins", but it wastes the third outcome: "balanced" then only covers 1 coin, while each tipped outcome leaves 4. Good tests split the possibilities into three equal thirds. With $3^k$ coins you need exactly $k$ weighings.

The balance scale
One coin is secretly heavy. Click a coin to cycle it between left pan → right pan → off, then press Weigh. Coins ruled out by the results so far fade out. The goal is to get down to one candidate in $\lceil\log_3 k\rceil$ weighings. Stuck? Optimal next weighing sets up the ternary split for you.

Famous follow-ups: (1) 12 coins, one is fake, heavier or lighter, 3 weighings. There are $24$ possibilities and $3^3=27\ge24$, so it's possible in principle, and a careful strategy achieves it. (2) 1000 wine bottles, one poisoned, 10 test strips (each strip says yes/no): $2^{10}=1024\ge1000$. Label bottles in binary and strip $j$ tests every bottle whose $j$-th bit is 1. (3) Twenty questions with yes/no answers distinguishes $2^{20}\approx10^6$ objects.

You have 30 coins, one heavier. What is the minimum number of weighings that guarantees finding it?
  • 2
  • 3
  • 4
  • 5
$3^3=27<30\le81=3^4$, so 3 weighings can't distinguish 30 cases. With 4 weighings it works: split $10/10/10$, then $3/3/4$, then $1/1/2$ or $1/1/1$, then $1/1$.

Reservoir sampling

Problem. Items $x_1,x_2,x_3,\dots$ arrive one at a time in a stream. When the stream ends, return one item chosen uniformly at random from everything seen. You don't know the length $n$ ahead of time, and you can only store one item.

Algorithm. Keep the first item: $s=x_1$. For each later item $x_n$ ($n=2,3,4,\dots$), replace $s$ with $x_n$ with probability $1/n$.

The newest item must be the answer with probability exactly $1/n$, so that's the replacement chance. The older items each had a $1/(n-1)$ share, and that shrinks by the factor $(n-1)/n$ that the new item doesn't steal their spot. The two effects cancel exactly, so everyone stays at $1/n$.

Proof by induction

Claim: after processing $n$ items, each of $x_1,\dots,x_n$ is in $s$ with probability $1/n$.

Base case ($n=1$): $s=x_1$ with probability $1=1/1$.

Inductive step: when $x_n$ arrives there are two cases.

  • $s=x_n$ (replace). This happens with probability $1/n$. ✓
  • $s=x_k$ for some $k\lt n$ (keep). This needs (1) $s=x_k$ after step $n-1$, which has probability $\frac1{n-1}$ by induction, and (2) we rejected $x_n$, which has probability $\frac{n-1}n$. These are independent, so $$\frac1{n-1}\cdot\frac{n-1}{n}=\frac1n.\ \checkmark$$

So every $x_k$ is in the reservoir with probability $1/n$ after $n$ steps.

Watch the reservoir
Step through a stream. Each arriving item takes the reservoir with probability $1/n$, and the bars show that at every moment every item seen so far has the same chance of being held. Run 10,000 streams shows a histogram of which index ends up selected, and it comes out flat.

Follow-up: sample $k$ items (Algorithm R). Keep the first $k$ items. For item $n>k$, with probability $k/n$ it replaces a uniformly random slot in the reservoir. The same induction shows each item ends up in the sample with probability $k/n$. Another neat variant: give each item a random key $u_i\sim\Unif(0,1)$ and keep the $k$ smallest keys. This also parallelizes across machines.

Secretary problem

Problem. $n$ candidates are interviewed in random order. After each interview you must immediately hire or reject that candidate, and you can't go back. You want to maximize the probability of hiring the best one. Use the strategy: reject the first $k$ candidates, then hire the next one who is better than all of the first $k$ (if nobody is, you're stuck with the last). What is the optimal $k$?

There's a tension. Look too briefly and your benchmark is weak, so you hire a mediocre early candidate. Look too long and the best has probably already gone by. The sweet spot is to look at about 37% ($1/e$) of candidates, and you then hire the best one about 37% of the time, no matter how large $n$ is.

Solution. Let $P(k)$ be the probability that threshold $k$ hires the best, and let $b$ be the position of the best candidate. The strategy succeeds exactly when:

  1. $b>k$: the best candidate comes after the first $k$, and
  2. the best among positions $1,\dots,b-1$ is in $1,\dots,k$. Otherwise that candidate beats the benchmark and is hired before we reach $b$.
$$\begin{aligned} P(k)&=\sum_{b=k+1}^n P(\text{best at }b)\,P(\text{best of first }b-1\text{ is among first }k)\\ &=\sum_{b=k+1}^n\frac1n\cdot\frac{k}{b-1} =\frac kn\sum_{i=k}^{n-1}\frac1i =\frac kn\big(H_{n-1}-H_{k-1}\big)\\ &\approx\frac kn\ln\frac nk \qquad(H_m\approx\ln m)\\ &=-r\ln r \qquad\text{where } r=k/n. \end{aligned}$$

Maximize: $\frac{d}{dr}(-r\ln r)=-\ln r-1=0$ gives $\ln r=-1$, so $r=1/e$ and $k\approx n/e$. The success probability at the optimum is $-\frac1e\ln\frac1e=\frac1e\approx36.8\%$.

Hiring simulator
The curve is the exact $P(k)$, with a dot at your chosen $k$. In the bar strip each bar is a candidate in interview order (taller = better). The shaded region is the "look" phase, the outlined bar is the true best, and the filled-in bar is who you hired. Simulate 10,000 checks $P(k)$ empirically.

Good things to say in an interview: the cutoff rule is actually optimal among all strategies, not only threshold ones. The answer $1/e$ doesn't depend on $n$. If instead you want to maximize the expected rank of the person hired, the optimal look phase is much shorter, about $\sqrt n$.

Monty Hall

Problem. There are 3 doors: a car behind one and goats behind the other two. You pick a door. Monty, who knows where the car is, opens a different door that has a goat. He then offers to let you switch to the remaining closed door. Should you?

Yes. Switching wins with probability $2/3$. Your first pick is right with probability $1/3$, and nothing Monty does changes that, because he can always open a goat door. So "stay" wins $1/3$ of the time. "Switch" wins exactly when your first pick was wrong, which is $2/3$ of the time: Monty has removed the other goat, so the remaining door must hold the car.

To make it obvious, imagine 100 doors. You pick one, and Monty opens 98 goat doors, leaving yours and door #73. Would you stick with your 1-in-100 guess?

Let's make a deal
Pick a door, Monty opens goat doors, then click your door to stay or another closed door to switch. The tallies keep score. Use Auto-play 1,000 to let the computer play many rounds with each strategy. Try $n$ doors and the "Monty opens only 1 door" variant.

General $n$ doors, by Bayes

Let $A\in\{1,\dots,n\}$ be the car's location and $B$ be the set of doors Monty opens. Without loss of generality we pick door $c$. We want $P(A=j\mid B)$ for each unopened door $j$:

$$P(A=j\mid B)=\frac{P(B\mid A=j)\,P(A=j)}{P(B)}.$$

The prior $P(A=j)=1/n$ is the same for every $j$ and the denominator is shared, so comparing posteriors reduces to comparing the likelihoods $P(B\mid A=j)$: "how likely is it that Monty would open exactly these doors, if the car were behind $j$?"

The original notes use a door index $t$ that is never defined. It is just our chosen door $c$, and it is written as $c$ below. Case 2 in the original also stops at "proportional to" without normalizing; the normalized posteriors are added.

Case 1: Monty opens $n-2$ doors, leaving our door $c$ and one other door $r$.

So the posteriors are proportional to $\frac1{n-1}$ and $1$. Normalizing gives

$$P(A=c\mid B)=\frac1n,\qquad P(A=r\mid B)=\frac{n-1}{n}.$$

Case 2: Monty opens only 1 door, $B=\{k\}$, leaving $n-2$ unchosen doors closed. Let $r$ be any one of them.

The unnormalized weights are $\frac1{n-1}$ for our door and $\frac1{n-2}$ for each of the $n-2$ others. Their sum is $\frac1{n-1}+1=\frac{n}{n-1}$, so

$$P(A=c\mid B)=\frac1n,\qquad P(A=r\mid B)=\frac{n-1}{n(n-2)}\ \text{ for each remaining door } r.$$

Each remaining door is slightly more likely than our door, since $\frac{n-1}{n-2}>1$. So switching to any of them helps, though less dramatically. For $n=3$ the two cases coincide and give $2/3$.

General rule: your door stays at $1/n$. The probability $k/n$ held by the $k$ opened doors gets spread evenly over the $n-k-1$ unopened, unchosen doors, so each ends up with $\frac{n-1}{n(n-k-1)}$.

The answer depends on Monty's behavior, not just on what you see. If Monty opens a door at random and it happens to show a goat, then switching and staying are both $1/2$. The $2/3$ comes from Monty knowing and avoiding the car, which is what makes his choice informative. Always state the host's rule.

10 doors. You pick one, and Monty (who knows) opens 1 goat door. You switch to one of the 8 other closed doors. What's your win probability?
  • $1/10$
  • $9/80$
  • $1/8$
  • $1/9$
Case 2 with $n=10$: $\frac{n-1}{n(n-2)}=\frac{9}{80}=0.1125$. That's a bit better than staying ($1/10$).

Longest run of heads

Problem. Flip a fair coin $n$ times and let $L_n$ be the longest run of consecutive heads. How big is $L_n$ typically?

There is no clean closed form for $\E[L_n]$, but a well-known approximation is

$$\E[L_n]\approx\log_2 n.$$

A specific stretch of $\ell$ flips is all heads with probability $2^{-\ell}$. There are about $n$ places a run could start, so the expected number of runs of length $\ell$ is roughly $n\,2^{-\ell}$ (more carefully $n2^{-\ell-1}$, since a run also has to be preceded by a tail). Runs of length $\ell$ stop being expected once $n2^{-\ell}\approx1$, which is at $\ell\approx\log_2 n$. Doubling $n$ adds only one to the longest run.

A sharper approximation is $\E[L_n]\approx\log_2 n-\tfrac23$, and the standard deviation stays near $1.87$ for every $n$, so the distribution just slides right as $n$ grows. A practical use: people faking "random" coin sequences avoid long runs. In 200 real flips a run of 6 or 7 heads is completely normal.

How long is the longest streak?
The strip is one sequence of $n$ flips (heads in blue) with the longest head-run highlighted. The histogram is the distribution of $L_n$ over thousands of sequences, with $\log_2 n$ marked. Double $n$ and watch the whole histogram shift by about 1.

Throwing balls into bins

Problem. Throw $m$ balls independently and uniformly into $m$ bins. What fraction of bins is empty? Has exactly one ball? Has two or more?

Answer: about 37% empty, 37% exactly one, and the remaining 26% get two or more.

Solution (indicators). Fix a bin. Each ball misses it with probability $1-\frac1m$, so

$$P(\text{empty})=\Big(1-\frac1m\Big)^m\to e^{-1}\approx0.368,$$ $$P(\text{exactly one})=m\cdot\frac1m\Big(1-\frac1m\Big)^{m-1}\to e^{-1}\approx0.368,$$ $$P(\ge 2)\to1-\frac2e\approx0.264.$$

By linearity, the expected fraction of empty bins is the same $(1-1/m)^m$, even though the bins are dependent. The load of one bin is $\Bin(m,1/m)\approx\Pois(1)$, and these three numbers are just $P(0), P(1), P(\ge2)$ for a $\Pois(1)$. See the Poisson limit.

Drop the balls
Balls fall one at a time into $m$ bins. Bins are colored by their final load: empty (gray), one (blue), or two or more (orange). The bar chart compares the observed fractions with $1/e,\ 1/e,\ 1-2/e$.

Maximum load. The fullest bin holds about $\frac{\ln m}{\ln\ln m}$ balls with high probability. This grows very slowly, and the approximation is only accurate for astronomically large $m$. If each ball instead looks at two random bins and goes to the emptier one ("power of two choices"), the max load drops to about $\log_2\ln m$, which is exponentially better and is used in load balancers.

Max load vs ln m / ln ln m
For each $m$ (log scale), this throws $m$ balls into $m$ bins several times and plots the average maximum load. Compare one random choice with the "best of two" rule. Notice the simulated one-choice curve sits well above $\ln m/\ln\ln m$: that formula only gets the leading order right, and the correction terms fade extremely slowly.

Related facts: with $m$ balls into $n$ bins, the expected number of empty bins is $n(1-1/n)^m$, which is the same as the coupon-collector "distinct types" count. It takes about $n\ln n$ balls before no bin is empty, which is the coupon collector again. The first collision happens after about $\sqrt n$ balls, which is the birthday problem again. These three puzzles are really one.

Path counting

Lattice paths ("how many routes from $(0,0)$ to $(m,n)$ moving right/up?" Answer: $\binom{m+n}{m}$) are covered with their own interactive grid in Combinatorics → Path counting.