Reflection principle: count bad paths by mirroring them
Count bad paths by mirroring them across a barrier. Maps gambler's ruin and ballot problems to clean combinatorial counts.
Intro
When a problem asks for the probability or count of paths that avoid some barrier — “A always leads,” “walker never goes negative,” “tally stays non-negative” — count the bad paths instead and subtract. The reflection trick gives you a clean bijection: reflect each bad path across the barrier at its first hit, and you land in a family of paths that’s directly countable with one binomial coefficient. Powers the ballot problem, Catalan numbers, and most random-walk first-passage questions — all classic interview territory.
✓ Intro · expand
More examples
A handful of harder problems on the same theme. Click any prompt to reveal the solution sketch.
Ticket-queue change problem. A theatre kiosk has no float at start of day. $2n$ customers line up to buy one $\$5$ ticket each; $n$ of them carry only $\$5$ bills and the other $n$ carry only $\$10$ bills. As long as the kiosk has change when a $\$10$-bill customer arrives, everyone is served in order. What is the probability that the entire queue is served without any customer being asked to move position?
$\dfrac{1}{n+1}$ (the $n$-th Catalan number divided by $\binom{2n}{n}$). Map $\$5$ holders to $+1$ steps and $\$10$ holders to $-1$ steps; the queue succeeds iff the corresponding lattice path from 0 stays non-negative. By the reflection principle, the count of bad paths matches paths that ever hit $-1$, and the good count is the $n$-th Catalan number $C_n = \tfrac{1}{n+1}\binom{2n}{n}$.
Coin-streak expectation. You have a fair coin. What is the expected number of tosses needed to see $n$ heads in a row?
$E[T_n] = 2^{n+1} - 2$. Set up the first-step recurrence: from state $k$ (current streak length), heads moves you to $k + 1$ and tails resets to 0. Solving gives $E[T_n] = 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 2$.
+ More examples · expand