Probability interview questions

Coupon Collector's Problem

High-level idea. Decompose the total waiting time into independent geometric stages, then apply linearity of expectation.

Stage decomposition

Let $T$ be the total number of rolls of a fair $N$-sided die needed to observe every face at least once. Define stage $k$ ($k = 1, \ldots, N$) as the period that begins the moment the $(k{-}1)$-th distinct face was first seen and ends when the $k$-th distinct face is first seen. Writing $T_k$ for the number of rolls in stage $k$,

Distribution of each stage

At the start of stage $k$, exactly $k-1$ faces have been observed. Each roll independently reveals a previously unseen face with probability

Hence $T_k \sim \operatorname{Geometric}(p_k)$ (number of trials until first success), so

Closed-form expected value

By linearity of expectation,

Reindexing with $j = N-k+1$ (as $k$ runs $1 \to N$, $j$ runs $N \to 1$):

where $H_N = \displaystyle\sum_{j=1}^{N} \frac{1}{j}$ is the $N$-th harmonic number.

Numerical evaluation for $N = 100$

Using the Euler–Maclaurin asymptotic expansion

with $\gamma = 0.57721566490153\ldots$ (Euler–Mascheroni constant):

Therefore,

Rounded to the nearest integer:

Let $N$ be the number of coin flips until the first heads appears. Since the coin is fair, $N$ follows a geometric distribution with success probability $1/2$: $P(N = n) = (1/2)^n$ for $n = 1, 2, 3, \dots$ (the first $n-1$ flips are tails and the $n$th flip is heads). The payout when $N = n$ is $2^n$ dollars. The expected value of the payout is

Since the expected value is infinite, the game does not have a finite fair value. Per the problem instructions, output $-1$.

High-level idea

Model the process as a Markov chain with two transient states tracking the current "run" of consecutive 1s. Set up first-step equations and solve the $2\times 2$ linear system.

States and equations

Let $p = \tfrac{1}{6}$ be the probability of rolling a 1. Define:

• $S_0$: start, or the last roll was not a 1.
• $S_1$: the last roll was a 1 (one consecutive 1 in progress).

Let $\mu_0,\mu_1$ be the expected number of additional rolls needed to reach absorption (two consecutive 1s) from each state.

From $S_0$ — one roll is used; with probability $\tfrac{1}{6}$ we move to $S_1$, with probability $\tfrac{5}{6}$ we remain in $S_0$:

From $S_1$ — one roll is used; with probability $\tfrac{1}{6}$ we finish (0 more rolls), with probability $\tfrac{5}{6}$ we return to $S_0$:

Solving the system

Rearranging the first equation:

Substituting $\mu_1 = 1 + \tfrac{5}{6}\mu_0$:

Check: $\mu_1 = 1 + \tfrac{5}{6}(42) = 36$, and $6 + 36 = 42$. ✓

Final answer

The expected number of rolls is $\boxed{42}$.

Idea

Work with the complement: a triple fails the triangle inequality if and only if one side is at least as large as the sum of the other two. The three failure events turn out to be mutually exclusive, so the failure probability is simply $3P(A)$ for any one of them.

Setup

Let $X, Y, Z \overset{\text{iid}}{\sim} \text{Uniform}[0,1]$. Define the failure events

Mutual Exclusivity of $A$, $B$, $C$

Suppose $A \cap B$ occurs: $X+Y \le Z$ and $X+Z \le Y$. Adding these inequalities gives $2X + Y + Z \le Y + Z$, hence $X \le 0$. Since $X \ge 0$ a.s., this forces $X = 0$, an event of probability zero. By symmetry, every pairwise intersection has measure zero, so $A$, $B$, $C$ are mutually exclusive a.s. Combined with symmetry of the joint distribution,

Computing $P(A)$

Condition on $Z = z$. The event $\{X + Y \le z\}$ within $[0,1]^2$ traces the right triangle $\{x \ge 0,\, y \ge 0,\, x+y \le z\}$, which has area $z^2/2$. Therefore

Final Answer

Idea

Track the game state as the longest suffix of the flip sequence that is a prefix of either target pattern. This yields a small Markov chain whose first-step equations determine the win probability exactly.

States and Transitions

Target patterns: Player 1 wins on $HTH$; Player 2 wins on $HHT$.

The transient states are $\{\varepsilon,\, H,\, HH,\, HT\}$, where $\varepsilon$ denotes no useful suffix (start, or after a progress-resetting tail).

Remark on $HH \xrightarrow{H} HH$: after any run of heads, the longest suffix that prefixes a target is still $HH$ (the length-2 prefix of $HHT$).

System of Equations

Let $p_s$ denote the probability that Player 1 wins from state $s$.

Equation (3) reflects that $HH$ is a trap: every additional $H$ keeps the game in $HH$, and the inevitable first $T$ completes $HHT$, so Player 1 cannot win from $HH$.

Solution

Substituting $(3)$ into $(2)$:

Combined with $(1)$, we have $p_{\varepsilon} = p_H = \tfrac{1}{2}p_{HT}$. Substituting into $(4)$:

The game begins in state $\varepsilon$, so Player 1 wins with probability $\dfrac{1}{3}$.