Probability Puzzles from Scratch

Solution

Replace the collision rule (“reverse”) with “pass through.” The two models produce identical observations at every moment: the same set of positions are occupied by ants, moving in the same directions. Only the labels on the ants differ, and the problem doesn’t depend on labels.

In the pass-through model, each ant walks independently in its original direction until it falls off the end. An ant at position \(x\) (measured in cm from the left end) falls off at time:

• \(x\) seconds, if facing left (walks to the left end),
• \(100 - x\) seconds, if facing right (walks to the right end).

The maximum time for a single ant is \(\max(x, 100 - x) \leq 100\). The worst case is an ant at one end facing the opposite end: it walks the entire length. So the maximum over all initial configurations is 100 seconds.

Solution

Person 1 can have any birthday. Person 2 must avoid person 1’s birthday: probability \(364/365\). Person 3 must avoid both: probability \(363/365\). Continuing:

$$ \Pr[\text{no match among } n] = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365 - n + 1}{365} = \prod_{k=0}^{n-1}\left(1 - \frac{k}{365}\right). $$

Finding the threshold. We want the smallest \(n\) such that this product drops below \(1/2\). Take logarithms:

$$ \ln\Pr[\text{no match}] = \sum_{k=0}^{n-1} \ln\!\left(1 - \frac{k}{365}\right). $$

For small \(x\), \(\ln(1 - x) \approx -x\). Since \(k/365\) is small for the values we care about:

$$ \ln\Pr[\text{no match}] \approx -\sum_{k=0}^{n-1} \frac{k}{365} = -\frac{n(n-1)}{2 \cdot 365}. $$

Setting this equal to \(\ln(1/2) = -\ln 2\):

$$ \frac{n(n-1)}{2 \cdot 365} \approx \ln 2 \implies n^2 \approx 2 \cdot 365 \cdot \ln 2 \approx 2 \cdot 365 \cdot 0.693 \approx 506. $$ $$ n \approx \sqrt{506} \approx 22.5. $$

So \(n = 23\). Let’s verify: \(\Pr[\text{no match among 23}] = \prod_{k=0}^{22}(1 - k/365)\). Computing this product gives \(\approx 0.4927\), so \(\Pr[\text{match}] \approx 0.5073 > 0.5\). \(\checkmark\)

For \(n = 22\): \(\Pr[\text{match}] \approx 0.476 < 0.5\). So 23 is exact.

Solution (Part 1)

Step 1: Count the relevant events. Two cards are drawn from 52. Total hands: \(\binom{52}{2} = 1326\).

$$ \begin{aligned} \Pr[\text{both Aces}] &= \frac{\binom{4}{2}}{\binom{52}{2}} = \frac{6}{1326}. \\[6pt] \Pr[\text{at least one Ace}] &= 1 - \frac{\binom{48}{2}}{\binom{52}{2}} = 1 - \frac{1128}{1326} = \frac{198}{1326}. \end{aligned} $$

Step 2: Apply the definition of conditional probability.

$$ \Pr[\text{both Aces} \mid \text{at least one Ace}] = \frac{\Pr[\text{both Aces}]}{\Pr[\text{at least one Ace}]} = \frac{6}{198} = \frac{1}{33}. $$

Solution (Part 2)

Step 1: Define the hypotheses.

• \(H_2\): both cards are Aces. \(\Pr[H_2] = 6/1326\).
• \(H_1\): exactly one card is an Ace. \(\Pr[H_1] = \binom{4}{1}\binom{48}{1}/\binom{52}{2} = 192/1326\).

Step 2: Compute likelihoods. A card is chosen at random and it’s an Ace:

• \(\Pr[\text{random card is Ace} \mid H_2] = 1\) (both are Aces, so either card works).
• \(\Pr[\text{random card is Ace} \mid H_1] = 1/2\) (only one of the two cards is an Ace).

Step 3: Bayes’ theorem.

$$ \begin{aligned} \Pr[H_2 \mid \text{see Ace}] &= \frac{\Pr[\text{see Ace} \mid H_2] \cdot \Pr[H_2]}{\Pr[\text{see Ace} \mid H_2] \cdot \Pr[H_2] + \Pr[\text{see Ace} \mid H_1] \cdot \Pr[H_1]} \\[6pt] &= \frac{1 \cdot 6/1326}{1 \cdot 6/1326 + \tfrac{1}{2} \cdot 192/1326} = \frac{6}{6 + 96} = \frac{6}{102} = \frac{1}{17}. \end{aligned} $$

Solution

The sample space. Four equally likely outcomes: BB, BG, GB, GG.

Part 1: “At least one boy.” This rules out GG. The remaining equally likely outcomes are BB, BG, GB. Only one of the three is BB:

$$ \Pr[\text{both boys} \mid \text{at least one boy}] = \frac{1}{3}. $$

Part 2: “A random child is a boy.” Apply Bayes’ theorem. The likelihood of seeing a boy when you pick a random child is:

• From BB: \(\Pr[\text{random child is boy}] = 1\).
• From BG or GB: \(\Pr[\text{random child is boy}] = 1/2\).
• From GG: \(\Pr[\text{random child is boy}] = 0\).

$$ \Pr[\text{BB} \mid \text{random child is boy}] = \frac{1 \cdot 1/4}{1 \cdot 1/4 + \tfrac{1}{2} \cdot 1/4 + \tfrac{1}{2} \cdot 1/4 + 0} = \frac{1/4}{1/2} = \frac{1}{2}. $$

Solution (two methods)

Method 1: Count equally likely cases. Label the six coins: G1a, G1b (Box 1), G2, S2 (Box 2), S3a, S3b (Box 3). Each coin is equally likely to be drawn. You drew a gold coin — that’s one of \(\{G1a, G1b, G2\}\). In two of these three cases (G1a and G1b), the other coin is gold. So:

$$ \Pr[\text{other is gold} \mid \text{drew gold}] = \frac{2}{3}. $$

Method 2: Bayes’ theorem.

$$ \begin{aligned} \Pr[\text{Box 1} \mid \text{gold}] &= \frac{\Pr[\text{gold} \mid \text{Box 1}] \cdot \Pr[\text{Box 1}]}{\sum_i \Pr[\text{gold} \mid \text{Box } i] \cdot \Pr[\text{Box } i]} \\[6pt] &= \frac{1 \cdot 1/3}{1 \cdot 1/3 + 1/2 \cdot 1/3 + 0 \cdot 1/3} = \frac{1/3}{1/2} = \frac{2}{3}. \end{aligned} $$

Solution

Step 1: Priors. \(\Pr[\text{car at } i] = 1/3\) for each door.

Step 2: Likelihoods. Given you picked Door 1, the host opens Door 3:

• \(\Pr[\text{host opens 3} \mid \text{car at 1}] = 1/2\) (host can open 2 or 3).
• \(\Pr[\text{host opens 3} \mid \text{car at 2}] = 1\) (host must open 3 — can’t open 2).
• \(\Pr[\text{host opens 3} \mid \text{car at 3}] = 0\) (host won’t reveal the car).

Step 3: Bayes’ theorem.

$$ \begin{aligned} \Pr[\text{car at 2} \mid \text{host opens 3}] &= \frac{1 \cdot 1/3}{\tfrac{1}{2} \cdot 1/3 + 1 \cdot 1/3 + 0} = \frac{1/3}{1/2} = \frac{2}{3}. \\[6pt] \Pr[\text{car at 1} \mid \text{host opens 3}] &= \frac{1/2 \cdot 1/3}{1/2} = \frac{1}{3}. \end{aligned} $$

Solution

Without the “Tuesday” information, this is the Boy-Girl problem (Puzzle 2b): the answer is \(1/3\). Adding “born on a Tuesday” changes the answer. Here’s why.

Step 1: The sample space. Each child is described by (gender, day of birth): \(2 \times 7 = 14\) equally likely types. Two children give \(14 \times 14 = 196\) outcomes.

Step 2: At least one Tuesday-boy. The complementary count is easier. Outcomes with no Tuesday-boy: each child is one of the \(14 - 1 = 13\) non-Tuesday-boy types, giving \(13^2 = 169\). So:

$$ |\text{at least one Tue-boy}| = 196 - 169 = 27. $$

Step 3: Both boys AND at least one Tuesday-boy. Each child is one of 7 boy-types (Mon-boy, Tue-boy, ..., Sun-boy). Two boys: \(7^2 = 49\). Both boys but no Tue-boy: \(6^2 = 36\). So:

$$ |\text{both boys, at least one Tue-boy}| = 49 - 36 = 13. $$

Step 4: The answer.

$$ \Pr[\text{both boys} \mid \text{at least one Tue-boy}] = \frac{13}{27} \approx 0.481. \quad\square $$

Proof $$ \begin{aligned} \E[X + Y] &= \sum_\omega (X(\omega) + Y(\omega))\,\Pr[\omega] \\ &= \sum_\omega X(\omega)\,\Pr[\omega] + \sum_\omega Y(\omega)\,\Pr[\omega] \\ &= \E[X] + \E[Y]. \end{aligned} $$

That’s it. The proof is one line. It uses nothing but the definition of expectation and the distributive law. The \(X(\omega)\) and \(Y(\omega)\) can be arbitrarily dependent — the algebra doesn’t care. \(\square\)

Solution

Define the indicator random variable:

$$ X_i = \begin{cases} 1 & \text{if card } i \text{ is in position } i, \\ 0 & \text{otherwise.}\end{cases} $$

The total number of fixed points is \(X = X_1 + X_2 + \cdots + X_{52}\).

By linearity of expectation (no independence needed!):

$$ \E[X] = \E[X_1] + \E[X_2] + \cdots + \E[X_{52}]. $$

Now, \(\E[X_i] = \Pr[\text{card } i \text{ is in position } i]\). In a uniformly random permutation of 52 cards, each card is equally likely to be in any of the 52 positions. So:

$$ \E[X_i] = \frac{1}{52}. $$

Therefore:

$$ \E[X] = 52 \cdot \frac{1}{52} = 1. $$

Solution

For any pair \((i, j)\) with \(i < j\), consider only the relative order of cards \(i\) and \(j\) in the shuffled deck. In a uniformly random permutation, card \(i\) is equally likely to appear before or after card \(j\) — there are only two relative orderings and both are equally likely. So:

$$ \Pr[X_{ij} = 1] = \frac{1}{2}. $$

There are \(\binom{n}{2}\) pairs. By linearity of expectation:

$$ \E[X] = \sum_{i < j} \E[X_{ij}] = \binom{n}{2} \cdot \frac{1}{2} = \frac{n(n-1)}{4}. $$

Solution

Let \(X_i = 1\{\text{position } i \text{ is a record}\}\). The card at position \(i\) is a record iff it is the maximum of the first \(i\) cards. In a uniformly random permutation, any of the first \(i\) cards is equally likely to be the maximum, so:

$$ \Pr[X_i = 1] = \frac{1}{i}. $$

By linearity of expectation:

$$ \E[\text{records}] = \sum_{i=1}^{n} \Pr[X_i = 1] = \sum_{i=1}^{n} \frac{1}{i} = H_n. $$

Solution

For each bin \(k\), define \(X_k = 1\{\text{bin } k \text{ is empty}\}\). Each ball lands in bin \(k\) with probability \(1/n\), independently. So:

$$ \Pr[X_k = 1] = \left(1 - \frac{1}{n}\right)^m. $$

By symmetry, this probability is the same for all \(n\) bins. By linearity of expectation:

$$ \E[\text{empty bins}] = n \left(1 - \frac{1}{n}\right)^m. $$

The important special case: when \(m = n\) (as many balls as bins), we use the approximation \((1 - 1/n)^n \to 1/e\) as \(n \to \infty\):

$$ \E[\text{empty bins}] \approx \frac{n}{e} \approx 0.368n. $$

Solution

Step 1: Compute \(\E[X_i X_j]\) for \(i \neq j\).

Since \(X_i\) and \(X_j\) are indicators, \(X_i X_j = 1\) iff both card \(i\) is in position \(i\) and card \(j\) is in position \(j\). In a uniformly random permutation of \(n\) cards:

$$ \Pr[X_i X_j = 1] = \Pr[\text{card } i \text{ in pos } i] \cdot \Pr[\text{card } j \text{ in pos } j \mid \text{card } i \text{ in pos } i]. $$

The first probability is \(1/n\). Given card \(i\) is fixed, card \(j\) must be in position \(j\) among the remaining \(n - 1\) cards in \(n - 1\) positions:

$$ \Pr[X_i X_j = 1] = \frac{1}{n} \cdot \frac{1}{n-1} = \frac{1}{n(n-1)}. $$

Step 2: Sum over all pairs.

There are \(n(n-1)\) ordered pairs \((i, j)\) with \(i \neq j\):

$$ \sum_{i \neq j} \E[X_i X_j] = n(n-1) \cdot \frac{1}{n(n-1)} = 1. $$

Step 3: Compute \(\E[X^2]\) and \(\Var(X)\).

$$ \E[X^2] = \E[X] + \sum_{i \neq j} \E[X_i X_j] = 1 + 1 = 2. $$ $$ \Var(X) = \E[X^2] - (\E[X])^2 = 2 - 1^2 = 1. $$

Proof

\(\Pr[X = k] = (1-p)^{k-1} p\) for \(k = 1, 2, 3, \ldots\). So:

$$ \E[X] = \sum_{k=1}^{\infty} k (1-p)^{k-1} p = p \sum_{k=1}^{\infty} k q^{k-1} \quad \text{where } q = 1-p. $$

The inner sum is a standard calculus fact: \(\sum_{k=1}^\infty k q^{k-1} = \frac{d}{dq}\sum_{k=0}^\infty q^k = \frac{d}{dq}\frac{1}{1-q} = \frac{1}{(1-q)^2} = \frac{1}{p^2}\).

So \(\E[X] = p \cdot 1/p^2 = 1/p\). \(\square\)

Sanity check: if \(p = 1/6\) (rolling a die until you get a 6), \(\E[X] = 6\) rolls. If \(p = 1\) (always succeed), \(\E[X] = 1\). Both match intuition.

Solution

In phase \(k\) (collecting the \(k\)-th new type), you already have \(k-1\) types. Each box is a new type with probability:

$$ p_k = \frac{n - (k-1)}{n} = \frac{n - k + 1}{n}. $$

The number of boxes in phase \(k\) is \(T_k \sim \operatorname{Geometric}(p_k)\), and the phases are independent (the outcome of each box is i.i.d.). The total number of boxes is \(T = T_1 + T_2 + \cdots + T_n\).

By linearity of expectation:

$$ \begin{aligned} \E[T] &= \sum_{k=1}^n \E[T_k] = \sum_{k=1}^n \frac{1}{p_k} = \sum_{k=1}^n \frac{n}{n - k + 1} \\ &= n \sum_{j=1}^n \frac{1}{j} = n \cdot H_n, \end{aligned} $$

where \(H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\) is the \(n\)-th harmonic number.

Proof of the bounds

Upper bound. Since \(1/x \leq 1/k\) for all \(x \in [k, k+1]\):

$$ \frac{1}{k} \geq \int_k^{k+1} \frac{dx}{x}. $$

Sum from \(k = 1\) to \(n\):

$$ H_n = \sum_{k=1}^{n} \frac{1}{k} \geq \int_1^{n+1} \frac{dx}{x} = \ln(n+1). $$

Lower bound. Since \(1/x \geq 1/(k+1)\) for all \(x \in [k, k+1]\):

$$ \frac{1}{k+1} \leq \int_k^{k+1} \frac{dx}{x}. $$

Sum from \(k = 1\) to \(n-1\):

$$ H_n - 1 = \sum_{k=2}^{n} \frac{1}{k} = \sum_{k=1}^{n-1} \frac{1}{k+1} \leq \int_1^{n} \frac{dx}{x} = \ln n. $$

Combining both:

$$ \ln(n+1) \leq H_n \leq 1 + \ln n. $$

This proves \(H_n = \ln n + O(1)\). But we can be much more precise. \(\square\)

Proof that \(\gamma_n\) converges

We show \(\gamma_n\) is decreasing and bounded below, hence convergent by the monotone convergence theorem.

\(\gamma_n\) is decreasing.

$$ \begin{aligned} \gamma_n - \gamma_{n+1} &= \left(H_n - \ln n\right) - \left(H_{n+1} - \ln(n+1)\right) \\ &= \ln(n+1) - \ln n - \frac{1}{n+1} \\ &= \ln\!\left(1 + \frac{1}{n}\right) - \frac{1}{n+1}. \end{aligned} $$

Since \(\ln(1 + 1/n) > 1/(n+1)\) for all \(n \geq 1\) (because \(\ln(1+x) > x/(1+x)\) for \(x > 0\), proved by noting the derivative of \(\ln(1+x) - x/(1+x)\) is \(x/(1+x)^2 > 0\)), we get \(\gamma_n > \gamma_{n+1}\). So \(\gamma_n\) is strictly decreasing.

\(\gamma_n\) is bounded below. We showed \(H_n \geq \ln(n+1)\), so:

$$ \gamma_n = H_n - \ln n \geq \ln(n+1) - \ln n = \ln\!\left(1 + \frac{1}{n}\right) > 0. $$

A decreasing sequence bounded below converges. We call its limit:

$$ \gamma = \lim_{n \to \infty} \left(\sum_{k=1}^{n} \frac{1}{k} - \ln n\right) = 0.5772156649\ldots $$

This is the Euler–Mascheroni constant. \(\square\)

Coupon Collector Asymptotics $$ \E[T] = n \cdot H_n = n\ln n + \gamma n + O(1) \approx n \ln n + 0.5772n. $$

Solution

Step 1: Variance of a Geometric random variable. Let \(X \sim \text{Geometric}(p)\) (number of trials until the first success). We need \(\E[X^2]\). Recall \(\E[X] = 1/p\). We derive \(\E[X^2]\) from scratch using the same conditioning trick that gives \(\E[X]\).

Let \(q = 1 - p\). On the first trial, either we succeed (probability \(p\), and \(X = 1\)) or we fail (probability \(q\), and we start over with \(X = 1 + X'\) where \(X' \sim \text{Geometric}(p)\) is an independent copy). Conditioning:

$$ \E[X^2] = p \cdot 1^2 + q \cdot \E[(1 + X')^2] = p + q\,\E[1 + 2X' + X'^2]. $$

Since \(X'\) has the same distribution as \(X\):

$$ \E[X^2] = p + q\bigl(1 + 2\E[X] + \E[X^2]\bigr) = p + q + 2q\E[X] + q\,\E[X^2]. $$

Using \(p + q = 1\) and \(\E[X] = 1/p\):

$$ \E[X^2] = 1 + \frac{2q}{p} + q\,\E[X^2]. $$

Solving for \(\E[X^2]\):

$$ \begin{aligned} \E[X^2] - q\,\E[X^2] &= 1 + \frac{2q}{p} \\[4pt] p\,\E[X^2] &= 1 + \frac{2q}{p} = \frac{p + 2q}{p} = \frac{2 - p}{p} \\[4pt] \E[X^2] &= \frac{2 - p}{p^2}. \end{aligned} $$

So:

$$ \Var(X) = \E[X^2] - (\E[X])^2 = \frac{2 - p}{p^2} - \frac{1}{p^2} = \frac{1 - p}{p^2}. $$

Step 2: Apply to each phase. In phase \(k\), you have already collected \(k - 1\) types, so the success probability is \(p_k = (n - k + 1)/n\). Substituting \(j = n - k + 1\) (so \(j\) runs from \(n\) down to \(1\)):

$$ \Var(T_k) = \frac{1 - p_k}{p_k^2} = \frac{1 - j/n}{(j/n)^2} = \frac{n^2 - nj}{j^2} = \frac{n^2}{j^2} - \frac{n}{j}. $$

Step 3: Sum the variances. Since the phases are independent:

$$ \begin{aligned} \Var(T) &= \sum_{j=1}^{n} \left(\frac{n^2}{j^2} - \frac{n}{j}\right) \\ &= n^2 \sum_{j=1}^{n} \frac{1}{j^2} \;-\; n \sum_{j=1}^{n} \frac{1}{j} \\ &= n^2 \sum_{j=1}^{n} \frac{1}{j^2} \;-\; n \cdot H_n. \end{aligned} $$

Step 4: Asymptotics. As \(n \to \infty\), \(\sum_{j=1}^{n} 1/j^2 \to \pi^2/6\) (the Basel problem). So:

$$ \Var(T) \;\approx\; \frac{\pi^2}{6}\, n^2 \quad \text{and} \quad \sigma(T) \;\approx\; \frac{\pi}{\sqrt{6}}\, n \;\approx\; 1.28\, n. $$

Proof: Euler’s Infinite Product

Step 1: The Taylor series of \(\sin(x)/x\). From the well-known expansion \(\sin(x) = x - x^3/3! + x^5/5! - \cdots\), divide both sides by \(x\):

$$ \frac{\sin x}{x} = 1 - \frac{x^2}{6} + \frac{x^4}{120} - \cdots $$

The coefficient of \(x^2\) on this side is \(-1/6\). Remember this.

Step 2: The zeros of \(\sin(x)/x\). The function \(\sin(x)\) vanishes at \(x = 0, \pm\pi, \pm 2\pi, \pm 3\pi, \ldots\) After dividing out the root at \(0\), the function \(\sin(x)/x\) has zeros precisely at \(x = \pm n\pi\) for \(n = 1, 2, 3, \ldots\)

Step 3: Factor from the roots. A polynomial with roots \(r_1, r_2, \ldots, r_N\) and value \(1\) at \(x = 0\) factors as \(\prod_{i=1}^{N}(1 - x/r_i)\). Euler’s bold move was to extend this to the infinite product for \(\sin(x)/x\), pairing each root \(+n\pi\) with \(-n\pi\) into a single quadratic factor:

$$ \frac{\sin x}{x} = \prod_{n=1}^{\infty} \left(1 - \frac{x^2}{n^2 \pi^2}\right). $$

(This factorization is justified rigorously by the Weierstrass factorization theorem — see the remark below.)

Step 4: Compare \(x^2\) coefficients. Expand the infinite product. The \(x^2\) term arises by selecting the \(-x^2/(n^2\pi^2)\) factor from exactly one term and \(1\) from all others:

$$ \text{coefficient of } x^2 \text{ in the product} = -\sum_{n=1}^{\infty} \frac{1}{n^2 \pi^2} = -\frac{1}{\pi^2}\sum_{n=1}^{\infty} \frac{1}{n^2}. $$

From Step 1, this coefficient equals \(-1/6\). Equating:

$$ -\frac{1}{\pi^2}\sum_{n=1}^{\infty} \frac{1}{n^2} = -\frac{1}{6} \quad\implies\quad \sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6}. \quad\square $$

Solution

Step 1: Probability a specific type appears. Type \(k\) is missing from all \(m\) draws when every draw lands on one of the other \(n - 1\) types:

$$ \Pr[D_k = 0] = \left(1 - \frac{1}{n}\right)^m. $$

So \(\Pr[D_k = 1] = 1 - (1 - 1/n)^m\). By symmetry, this is the same for every type.

Step 2: Linearity of expectation.

$$ \E[D] = \sum_{k=1}^{n} \Pr[D_k = 1] = n\left(1 - \left(1 - \frac{1}{n}\right)^m\right). $$

Solution

Step 1: Probability of no collision in \(m\) draws. Draw 1 is always new. Draw 2 avoids 1 type with probability \((n-1)/n\). Draw 3 avoids 2 types with probability \((n-2)/n\). Continuing:

$$ \Pr[C > m] = \prod_{k=0}^{m-1} \frac{n - k}{n} = \prod_{k=0}^{m-1}\left(1 - \frac{k}{n}\right). $$

Step 2: Approximate using \(\ln(1-x) \approx -x\).

$$ \begin{aligned} \ln \Pr[C > m] &= \sum_{k=0}^{m-1} \ln\!\left(1 - \frac{k}{n}\right) \\ &\approx -\sum_{k=0}^{m-1} \frac{k}{n} = -\frac{m(m-1)}{2n}. \end{aligned} $$

So \(\Pr[C > m] \approx e^{-m^2/(2n)}\), a Gaussian-style decay.

Step 3: Expected value via survival function.

$$ \begin{aligned} \E[C] &= \sum_{m=0}^{\infty} \Pr[C > m] \approx \int_0^{\infty} e^{-m^2/(2n)}\, dm \\ &= \sqrt{2n} \int_0^{\infty} e^{-u^2}\, du = \sqrt{2n} \cdot \frac{\sqrt{\pi}}{2} = \sqrt{\frac{\pi n}{2}}. \end{aligned} $$

Solution

Step 1: The min-max identity. For any two random variables: \(\max(X, Y) = X + Y - \min(X, Y)\). Taking expectations:

$$ \E[\max(T_A, T_B)] = \E[T_A] + \E[T_B] - \E[\min(T_A, T_B)]. $$

Step 2: Each term. \(T_A \sim \text{Geometric}(p)\), so \(\E[T_A] = 1/p\). Similarly \(\E[T_B] = 1/(1-p)\). The minimum \(\min(T_A, T_B)\) is the time until the first coupon of either type, which happens on every draw with probability \(p + (1-p) = 1\). So \(\min(T_A, T_B) = 1\) always (the first draw is always one of the two types).

Step 3: Combine.

$$ \E[T] = \frac{1}{p} + \frac{1}{1-p} - 1. $$

Solution

Let \(p_k = \Pr[\text{reach } \$n \text{ starting from } \$k]\). By conditioning on the first flip:

$$ p_k = \frac{1}{2}\, p_{k+1} + \frac{1}{2}\, p_{k-1}, \qquad k = 1, 2, \ldots, n-1. $$

Boundary conditions: \(p_0 = 0\) (ruin) and \(p_n = 1\) (win).

Solving the recurrence. Rearrange: \(p_{k+1} - p_k = p_k - p_{k-1}\). This says the successive differences are constant. Let \(d = p_1 - p_0 = p_1\). Then:

$$ p_k - p_{k-1} = d \quad \text{for all } k, $$

so \(p_k = k \cdot d\) (telescoping from \(p_0 = 0\)). From the boundary condition \(p_n = 1\):

$$ n \cdot d = 1 \implies d = \frac{1}{n} \implies p_k = \frac{k}{n}. $$

Solution

Step 1: Recurrence and boundaries.

$$ E_k = 1 + \frac{1}{2}\,E_{k+1} + \frac{1}{2}\,E_{k-1}, \qquad k = 1, \ldots, n-1. $$

Boundaries: \(E_0 = E_n = 0\) (the game ends immediately at either barrier).

Step 2: Rearrange. Multiply through by 2 and collect terms:

$$ E_{k+1} - 2E_k + E_{k-1} = -2. $$

This is a second-order linear recurrence with constant coefficients and a constant forcing term.

Step 3: Homogeneous solution. First, ignore the forcing term and solve the homogeneous version \(E_{k+1} - 2E_k + E_{k-1} = 0\). How do we solve a recurrence like this? The method is exactly analogous to solving differential equations like \(y'' - 2y' + y = 0\) — we guess an exponential.

The characteristic equation method. Guess \(E_k = x^k\) for some constant \(x\). Substituting into \(E_{k+1} - 2E_k + E_{k-1} = 0\):

$$ x^{k+1} - 2x^k + x^{k-1} = 0. $$

Factor out \(x^{k-1}\) (which is never zero):

$$ x^{k-1}(x^2 - 2x + 1) = 0 \quad\implies\quad x^2 - 2x + 1 = 0. $$

This quadratic is the characteristic equation. Its roots tell us which exponentials \(x^k\) solve the recurrence. There are three cases:

• Two distinct roots \(x_1 \neq x_2\): general solution is \(E_k = A \cdot x_1^k + B \cdot x_2^k\).
• One repeated root \(x_1 = x_2 = x_0\): the two independent solutions are \(x_0^k\) and \(k \cdot x_0^k\), so the general solution is \(E_k = (A + Bk) \cdot x_0^k\).

(This is the discrete analogue of \(e^{rx}\) and \(xe^{rx}\) for repeated roots in ODEs.)

Here: \(x^2 - 2x + 1 = (x - 1)^2 = 0\). Double root at \(x = 1\). Since \(1^k = 1\) for all \(k\), the two independent solutions are \(1\) and \(k \cdot 1^k = k\). So the homogeneous solution is:

$$ E_k^{(h)} = A + Bk. $$

(Compare with the biased coin above: that recurrence has characteristic roots \(1\) and \(r = q/p\), two distinct roots, giving general solution \(A \cdot 1^k + B \cdot r^k = A + Br^k\).)

Step 4: Particular solution. The full equation is \(E_{k+1} - 2E_k + E_{k-1} = -2\). The right-hand side is a constant, so we want a particular solution that produces a constant when plugged into the left-hand side. Normally we’d try \(E_k^{(p)} = C\) (a constant), but constants are already in the homogeneous solution. So we “bump up” by one degree and try \(E_k^{(p)} = Ck\) — but linear functions are also in the homogeneous solution (because of the double root). So we bump up again and try \(E_k^{(p)} = Ck^2\). Substituting:

$$ C(k+1)^2 - 2Ck^2 + C(k-1)^2 = C\bigl[(k^2 + 2k + 1) - 2k^2 + (k^2 - 2k + 1)\bigr] = 2C. $$

We need \(2C = -2\), so \(C = -1\). The particular solution is \(-k^2\).

(The rule: if the forcing term’s natural form is already a solution of the homogeneous equation, multiply by \(k\) until it isn’t. This is identical to the “multiply by \(x\)” rule for undetermined coefficients in ODEs.)

Step 5: Apply boundaries. General solution: \(E_k = A + Bk - k^2\).

$$ \begin{aligned} E_0 = 0 &\implies A = 0, \\ E_n = 0 &\implies Bn - n^2 = 0 \implies B = n. \end{aligned} $$

Therefore:

$$ E_k = nk - k^2 = k(n - k). \quad\square $$

Solution

Step 1: State transitions. Draw the automaton:

• \(S_0\): flip H \(\to S_1\), flip T \(\to S_0\)
• \(S_1\): flip H \(\to S_2\), flip T \(\to S_0\) (one head lost — full reset)
• \(S_2\): flip H \(\to\) DONE, flip T \(\to S_0\) (two heads lost — full reset)

Step 2: Write the system. Let \(E_i\) = expected flips from state \(S_i\):

$$ \begin{aligned} E_0 &= 1 + \tfrac{1}{2}\,E_1 + \tfrac{1}{2}\,E_0 &\quad&(1) \\ E_1 &= 1 + \tfrac{1}{2}\,E_2 + \tfrac{1}{2}\,E_0 &\quad&(2) \\ E_2 &= 1 + \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}\,E_0 &\quad&(3) \end{aligned} $$

Step 3: Solve by substitution.

From (1): \(\tfrac{1}{2}E_0 = 1 + \tfrac{1}{2}E_1\), so \(E_0 = 2 + E_1\).  …(i)

From (3): \(E_2 = 1 + \tfrac{1}{2}E_0\).  …(iii)

Substitute (iii) into (2):

$$ E_1 = 1 + \tfrac{1}{2}\!\left(1 + \tfrac{1}{2}E_0\right) + \tfrac{1}{2}E_0 = \tfrac{3}{2} + \tfrac{3}{4}E_0. \quad\ldots\text{(iv)} $$

Substitute (iv) into (i):

$$ E_0 = 2 + \tfrac{3}{2} + \tfrac{3}{4}E_0 = \tfrac{7}{2} + \tfrac{3}{4}E_0. $$

Solving: \(\tfrac{1}{4}E_0 = \tfrac{7}{2}\), so \(\mathbf{E_0 = 14}\).

Step 4: Back-substitute. \(E_2 = 1 + 7 = 8\). \(E_1 = \tfrac{3}{2} + \tfrac{21}{2} = 12\).

Verify equation (2): \(1 + \tfrac{1}{2}(8) + \tfrac{1}{2}(14) = 1 + 4 + 7 = 12\). \(\checkmark\) \(\square\)

Solution

Step 1: The recurrence. Let \(p_k = \Pr[\text{eventually reach } 0 \mid \text{start at } k]\). Then:

$$ p_k = p \cdot p_{k+1} + q \cdot p_{k-1}, \qquad k \geq 1. $$

Boundary: \(p_0 = 1\). No upper boundary — instead, require \(0 \leq p_k \leq 1\) for all \(k\).

Step 2: General solution via the characteristic equation. Rearrange the recurrence: \(p \cdot p_{k+1} - p_k + q \cdot p_{k-1} = 0\). Guess \(p_k = x^k\) and substitute:

$$ p \cdot x^{k+1} - x^k + q \cdot x^{k-1} = 0 \quad\implies\quad x^{k-1}(p \cdot x^2 - x + q) = 0. $$

The characteristic equation is \(p \cdot x^2 - x + q = 0\). Using \(q = 1 - p\):

$$ p \cdot x^2 - x + (1 - p) = 0 \quad\implies\quad (x - 1)(px - q) = 0. $$

Roots: \(x_1 = 1\) and \(x_2 = q/p\). When \(p \neq 1/2\), these are distinct, so the general solution is \(A \cdot 1^k + B \cdot (q/p)^k\):

$$ p_k = A + B \cdot r^k, \qquad r = \frac{q}{p}. $$

From \(p_0 = 1\): \(A + B = 1\), so \(p_k = (1 - B) + B \cdot r^k\).

Step 3: Case \(p \leq 1/2\) (so \(r = q/p \geq 1\)). If \(r > 1\) and \(B \neq 0\), then \(B \cdot r^k \to \pm\infty\) as \(k \to \infty\), making \(p_k\) leave \([0, 1]\). The only bounded solution is \(B = 0\), giving:

$$ p_k = 1 \quad\text{for all } k. \qquad\text{(Certain ruin.)} $$

For \(p = 1/2\) (\(r = 1\)), the characteristic equation has a double root. The general solution is \(p_k = A + Bk\). Boundedness forces \(B = 0\), again giving \(p_k = 1\).

Step 4: Case \(p > 1/2\) (so \(r = q/p < 1\)). Now \(r^k \to 0\) as \(k \to \infty\), so \(B \cdot r^k\) stays bounded for any \(B\). Both \(p_k = 1\) (taking \(B = 0\)) and \(p_k = r^k\) (taking \(B = 1, A = 0\)) are valid bounded solutions satisfying \(p_0 = 1\). Which one is the ruin probability?

The answer comes from the finite problem. With an upper barrier at \(n\), we proved \(p_k = (r^n - r^k)/(r^n - 1)\). As \(n \to \infty\) with \(r < 1\): \(r^n \to 0\), so:

$$ p_k = \frac{0 - r^k}{0 - 1} = r^k = \left(\frac{q}{p}\right)^k < 1. \qquad\text{(Survival is possible.)} $$

The limit selects \(A = 0, B = 1\). The solution \(p_k = 1\) is mathematically valid but physically wrong — it corresponds to the drunkard falling off a cliff that isn’t there (the upper barrier at \(\infty\)).

Step 5: Verify the \(r \geq 1\) case via the finite limit. For \(r \geq 1\), we claimed \(p_k = 1\). Check: from the finite formula \(p_k = (r^n - r^k)/(r^n - 1)\) with \(r > 1\), as \(n \to \infty\): \(r^n \to \infty\), so \(p_k \to r^n / r^n = 1\). For \(r = 1\): \(p_k = (n - k)/(n - 1) \to 1\). Both match. \(\square\)

Solution

Step 1: State transitions for HTH.

• \(S_0\): flip H \(\to S_1\), flip T \(\to S_0\)
• \(S_1\): flip H \(\to S_1\) (self-loop: “HH” has suffix “H”), flip T \(\to S_2\)
• \(S_2\): flip H \(\to\) DONE, flip T \(\to S_0\) (“HTT” has no matching prefix)

Step 2: Write the system.

$$ \begin{aligned} E_0 &= 1 + \tfrac{1}{2}\,E_1 + \tfrac{1}{2}\,E_0 &\quad&(1) \\ E_1 &= 1 + \tfrac{1}{2}\,E_1 + \tfrac{1}{2}\,E_2 &\quad&(2) \\ E_2 &= 1 + \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}\,E_0 &\quad&(3) \end{aligned} $$

Compare with HHH: the only difference is equation (2). In HHH, tails from \(S_1\) resets to \(S_0\), so equation (2) has \(\tfrac{1}{2}E_0\). Here, heads from \(S_1\) stays at \(S_1\), so equation (2) has \(\tfrac{1}{2}E_1\).

Step 3: Solve.

From (1): \(\tfrac{1}{2}E_0 = 1 + \tfrac{1}{2}E_1\), so \(E_0 = 2 + E_1\).  …(i)

From (2): \(\tfrac{1}{2}E_1 = 1 + \tfrac{1}{2}E_2\), so \(E_1 = 2 + E_2\).  …(ii)

From (3): \(E_2 = 1 + \tfrac{1}{2}E_0\).  …(iii)

Substitute (iii) into (ii): \(E_1 = 2 + 1 + \tfrac{1}{2}E_0 = 3 + \tfrac{1}{2}E_0\).

Substitute into (i): \(E_0 = 2 + 3 + \tfrac{1}{2}E_0 = 5 + \tfrac{1}{2}E_0\).

Solving: \(\tfrac{1}{2}E_0 = 5\), so \(\mathbf{E_0 = 10}\).

Step 4: Back-substitute and verify. \(E_2 = 1 + 5 = 6\). \(E_1 = 2 + 6 = 8\).

Check (2): \(1 + \tfrac{1}{2}(8) + \tfrac{1}{2}(6) = 1 + 4 + 3 = 8\). \(\checkmark\) \(\square\)

Discovery 1: \(S_t\) is a martingale — solving for ruin probability

Question: fair coin, start at \(\$k\), barriers at \(0\) and \(n\). Probability of reaching \(n\)?

Step 1: Write the functional equation. Fair coin means \(p = q = 1/2\). We want \(f\) with:

$$ \frac{1}{2} f(x + 1) + \frac{1}{2} f(x - 1) = f(x). $$

Step 2: Try Strategy A. \(f(x) = x\):

$$ \frac{1}{2}(x + 1) + \frac{1}{2}(x - 1) = x. \quad \checkmark $$

It works! So \(M_t = S_t\) (wealth itself) is a martingale.

Step 3: Extract the answer. Since \(\E[M_T] = \E[M_0]\):

$$ \E[S_T] = k. \quad \text{But } S_T \in \{0, n\}, \text{ so } n \cdot \Pr(\text{win}) = k \implies \Pr(\text{win}) = \frac{k}{n}. \quad\square $$

Discovery 2: \(S_t^2 - t\) is a martingale — solving for expected duration

Question: same fair-coin game. What is the expected number of flips until the game ends?

Step 1: What do we need? We need a martingale that involves time \(t\), because we want \(\E[T]\). Try the form:

$$ M_t = g(S_t) - t. $$

If this is a martingale, then at the stopping time \(T\): \(\E[g(S_T) - T] = g(S_0) - 0 = g(k)\). This gives \(\E[T] = \E[g(S_T)] - g(k)\) — and we can compute \(\E[g(S_T)]\) because \(S_T \in \{0, n\}\). So our goal is to find \(g\).

Step 2: Write the functional equation. For \(g(S_t) - t\) to be a martingale:

$$ \E[g(S_{t+1}) - (t+1) \mid S_t = x] = g(x) - t. $$

The \(-t\) cancels, leaving:

$$ \E[g(S_{t+1}) \mid S_t = x] = g(x) + 1. $$

In words: \(g\) must go up by exactly 1, on average, each step. For the fair ±1 walk:

$$ \frac{1}{2}\, g(x + 1) + \frac{1}{2}\, g(x - 1) = g(x) + 1. \tag{$\star$} $$

Step 3: Solve for \(g\). Try a polynomial. The simplest guess is \(g(x) = ax^2 + bx + c\). Plug into (\(\star\)):

$$ \begin{aligned} \text{LHS} &= \frac{1}{2}\bigl[a(x+1)^2 + b(x+1) + c\bigr] + \frac{1}{2}\bigl[a(x-1)^2 + b(x-1) + c\bigr] \\[4pt] &= \frac{1}{2}\bigl[ax^2 + 2ax + a + bx + b + c\bigr] + \frac{1}{2}\bigl[ax^2 - 2ax + a + bx - b + c\bigr] \\[4pt] &= ax^2 + a + bx + c. \end{aligned} $$ $$ \text{RHS} = ax^2 + bx + c + 1. $$

Setting LHS = RHS: \(ax^2 + a + bx + c = ax^2 + bx + c + 1\), which gives \(a = 1\). The parameters \(b\) and \(c\) can be anything — take \(b = c = 0\) for simplicity.

So \(g(x) = x^2\), and

$$ \boxed{M_t = S_t^2 - t \text{ is a martingale.}} $$

Step 4: Extract the answer. Apply \(\E[M_T] = \E[M_0]\):

$$ \E[S_T^2 - T] = S_0^2 - 0 = k^2. $$

Since \(S_T \in \{0, n\}\) and \(\Pr(S_T = n) = k/n\) (from Discovery 1):

$$ \E[S_T^2] = n^2 \cdot \frac{k}{n} + 0^2 \cdot \frac{n - k}{n} = nk. $$

Therefore:

$$ \E[T] = \E[S_T^2] - k^2 = nk - k^2 = k(n - k). \quad\square $$

Discovery 3: \((q/p)^{S_t}\) is a martingale — solving biased ruin

Question: biased coin (\(\Pr(\text{heads}) = p \neq 1/2\)). Start at \(k\), barriers at \(0\) and \(n\). Probability of reaching \(n\)?

Step 1: Why Strategy A fails. Try \(f(x) = x\):

$$ p(x + 1) + q(x - 1) = x + (p - q) \neq x. $$

Wealth is NOT conserved. The coin has a drift of \(p - q\) per flip. We could subtract the drift (\(S_t - (p-q)t\) is a martingale), but that’s useless for ruin: the boundaries are at fixed positions \(0\) and \(n\), but this martingale involves time, which we don’t know at the boundaries.

Step 2: Use Strategy C. We need a function of position alone. Try \(f(x) = r^x\) for some unknown base \(r\).

Plug into the functional equation \(p \cdot f(x+1) + q \cdot f(x-1) = f(x)\):

$$ p \cdot r^{x+1} + q \cdot r^{x-1} = r^x. $$

Step 3: Solve for \(r\). Divide everything by \(r^{x-1}\):

$$ p r^2 + q = r \implies p r^2 - r + q = 0. $$

This is a quadratic in \(r\). Apply the quadratic formula:

$$ r = \frac{1 \pm \sqrt{1 - 4pq}}{2p}. $$

Now use the identity \(1 - 4pq = (p + q)^2 - 4pq = (p - q)^2\), so \(\sqrt{1 - 4pq} = |p - q|\). The two roots are:

$$ r = \frac{1 + (p - q)}{2p} = \frac{2p}{2p} = 1, \qquad r = \frac{1 - (p - q)}{2p} = \frac{2q}{2p} = \frac{q}{p}. $$

Root \(r = 1\) gives \(f(x) = 1^x = 1\) — a constant. True but useless. The interesting root is \(r = q/p\), giving:

$$ \boxed{M_t = \left(\frac{q}{p}\right)^{S_t} \text{ is a martingale.}} $$

Step 4: Verify (one line). Check that \(p \cdot r + q/r = 1\):

$$ p \cdot \frac{q}{p} + q \cdot \frac{p}{q} = q + p = 1. \quad\checkmark $$

Step 5: Extract the answer. Let \(r = q/p\). Apply \(\E[M_T] = \E[M_0]\):

$$ \E[r^{S_T}] = r^{S_0} = r^k. $$

Since \(S_T \in \{0, n\}\), with \(w = \Pr(S_T = n)\):

$$ r^n \cdot w + r^0 \cdot (1 - w) = r^k \implies w = \frac{r^k - 1}{r^n - 1}. $$

This is the biased gambler’s ruin formula — found by solving a quadratic. No recurrence, no characteristic equation for the recurrence. Just one functional equation and Strategy C. \(\quad\square\)

Proof sketch

Step 1: Telescope. Write the stopped value as a sum of increments:

$$ M_T - M_0 = \sum_{t=0}^{\infty} (M_{t+1} - M_t) \cdot \mathbf{1}_{\{T > t\}}. $$

The indicator \(\mathbf{1}_{\{T > t\}}\) equals 1 while the game is running and 0 after you stop. So this sum picks up exactly the increments that happen before stopping.

Step 2: Each term has expectation zero. The key: \(\{T > t\}\) depends only on \(M_0, \ldots, M_t\) (because \(T\) is a stopping time — you can decide whether you’ve stopped by looking at the past). So \(\mathbf{1}_{\{T > t\}}\) is determined by the history up to time \(t\). This lets us use the tower property:

$$ \E\bigl[(M_{t+1} - M_t) \cdot \mathbf{1}_{\{T > t\}}\bigr] = \E\bigl[\underbrace{\E[M_{t+1} - M_t \mid \text{history up to } t]}_{= 0 \text{ (martingale!)}} \cdot\; \mathbf{1}_{\{T > t\}}\bigr] = 0. $$

Step 3: Swap \(\E\) and \(\sum\). Can we pass the expectation inside the infinite sum? Yes, because:

$$ \sum_{t=0}^{\infty} \E\bigl[|M_{t+1} - M_t| \cdot \mathbf{1}_{\{T > t\}}\bigr] \leq C \sum_{t=0}^{\infty} \Pr(T > t) = C \cdot \E[T] < \infty. $$

Bounded increments (\(\leq C\)) and finite expected stopping time (\(\E[T] < \infty\)) guarantee absolute convergence. So \(\E[M_T - M_0] = \sum_t 0 = 0\). \(\quad\square\)

Solution (following the protocol)

Step 1: \(W_t\) = wealth after \(t\) rounds.

Step 2: each round, you pay $1. Heads (prob 1/2): receive $3, net change = +$2. Tails (prob 1/2): receive $0, net change = −$1.

$$ \E[\Delta W] = \frac{1}{2}(+2) + \frac{1}{2}(-1) = +0.50. $$

Step 3: drift = +0.50 > 0. The game is favorable, not fair. \(W_t\) is a sub-martingale (expected to go up). The adjusted process \(W_t - 0.5t\) is a martingale. After \(n\) rounds, expected profit is \(0.5n\).

Follow-up: what entry fee \(c\) makes the game fair? Need \(\E[\Delta W] = (1/2)(3 - c) + (1/2)(0 - c) = 3/2 - c = 0\), so \(c = \$1.50\).

Solution

Step 1: after \(k\) consecutive losses, total bet = \(1 + 2 + \cdots + 2^{k-1} = 2^k - 1\). Next bet: \(2^k\).

Step 2: each individual bet is on a fair coin, so \(\E[\Delta W] = 0\) each round. Wealth \(W_t\) IS a martingale.

Step 3: on the first win (after \(k\) losses), you receive \(2 \cdot 2^k = 2^{k+1}\). Total invested: \(2^{k+1} - 1\). Net profit: $1. Guaranteed!

…or is it?

Step 4 (OST check): the stopping time \(T\) = first win has \(\E[T] = 2 < \infty\) (\(\text{Geometric}(1/2)\)). But the increments are not bounded. At round \(k\), the bet is \(2^k\), which grows without limit. Condition (b) of OST is violated.

What happens: with a finite bankroll \(B\), you can make at most \(m = \lfloor \log_2(B + 1) \rfloor\) bets. If you lose all \(m\) (probability \(1/2^m\)):

$$ \E[\text{payoff}] = \Bigl(1 - \frac{1}{2^m}\Bigr)(+1) + \frac{1}{2^m}\bigl(-(2^m - 1)\bigr) = 0. $$

Expected profit is exactly zero. The strategy doesn’t create value — it redistributes risk: high probability of a small win ($1), tiny probability of a catastrophic loss (all your money). This is the textbook example of why OST conditions matter: drop the bounded-increments condition and conservation breaks.

Solution

Step 2 (expected payout):

$$ \E[\text{payout}] = \sum_{k=1}^{\infty} \frac{1}{2^k} \cdot 2^k = \sum_{k=1}^{\infty} 1 = \infty. $$

Expected value is infinite! You should mortgage your house to play — right?

But if asked “how much would you actually pay?”, most people say $10–$20. The disconnect is real.

Resolution (Bernoulli, 1738): people maximize expected utility, not expected dollars. With logarithmic utility \(u(x) = \ln x\):

$$ \E[\ln(\text{payout})] = \sum_{k=1}^{\infty} \frac{k \ln 2}{2^k} = (\ln 2) \sum_{k=1}^{\infty} \frac{k}{2^k} = (\ln 2) \cdot 2 = 2\ln 2. $$

(The series \(\sum k/2^k = 2\) follows from differentiating the geometric series \(\sum x^k = 1/(1-x)\) to get \(\sum kx^{k-1} = 1/(1-x)^2\), then setting \(x = 1/2\).)

Fair price: \(\ln c = 2\ln 2 \implies c = 4\). Under log utility, pay at most ~$4.

Martingale perspective: the payout process isn’t even integrable (\(\E[|\text{payout}|] = \infty\)), so it violates condition (1) of the martingale definition. It’s not a martingale. OST doesn’t apply. This is consistent: infinite expected value but no finite fair price.

Interview insight: this game tests whether you can recognize when martingale machinery breaks down. The right answer isn’t a number — it’s identifying that the expected value is infinite and pivoting to utility theory.

Solution

Step 1: Define the value. Let \(V\) = expected payoff under optimal play. On any roll, if you see \(x\):

• Keep: you get \(x\).

• Re-roll: you pay $1 and get expected value \(V\) from the fresh start. Net value: \(V - 1\).

Optimal strategy: keep if \(x \geq V\), re-roll if \(x < V\).

Step 2: Self-consistency. \(V\) must satisfy \(V = \E[\max(X, V - 1)]\) where \(X\) is a die roll. We guess a threshold \(t\) (keep if \(X \geq t\), re-roll if \(X < t\)) and check for consistency.

Attempt 1: threshold = 5 (keep on 5 or 6, re-roll on 1–4).

$$ V = \frac{4}{6}(V - 1) + \frac{1}{6}(5) + \frac{1}{6}(6) = \frac{4}{6}V - \frac{4}{6} + \frac{11}{6}. $$ $$ \frac{2}{6}V = \frac{7}{6} \implies V = 3.5. $$

But \(V = 3.5 < 4\), so we should also keep 4 (since \(4 > V\)). Our threshold was too high — we were re-rolling numbers we should have kept. Inconsistent.

Attempt 2: threshold = 4 (keep on 4, 5, or 6, re-roll on 1–3).

$$ V = \frac{3}{6}(V - 1) + \frac{1}{6}(4 + 5 + 6) = \frac{1}{2}V - \frac{1}{2} + \frac{15}{6} = \frac{1}{2}V + 2. $$ $$ \frac{1}{2}V = 2 \implies V = 4. $$

Consistency check: \(V = 4\) = threshold. We keep \(\geq 4\), re-roll \(< 4\). Exactly what we assumed. \(\checkmark\)

Summary: optimal strategy is to keep 4, 5, or 6; re-roll 1, 2, or 3. Expected payoff: $4. Expected number of rolls: \(1/(3/6) = 2\) (geometric with success probability 1/2).

Martingale connection: define \(V_t\) = value of your position at time \(t\). Under optimal play, each re-roll costs $1 while expected value stays at \(V\), so \(\E[V_{t+1} \mid \mathcal{F}_t] \leq V_t\) — a super-martingale. You stop at the first time the reward exceeds the continuation value. This is the principle behind all optimal stopping problems: stop the first time the current reward beats the expected future.

Solution (The Casino Construction)

This is one of the most elegant applications of the optional stopping theorem. The idea: build a casino whose total payout is a martingale, then read off the answer from what the casino owes at the stopping time.

Setup. Before each keystroke, a fresh gambler walks in and bets $1 that the next letter will be “A” (the first letter of the target word). The odds are fair: 26-to-1 payout. If the gambler wins, they parlay their entire \($26\) on the next letter being “B” (again at 26:1 odds). If they win again, they bet everything on “R,” and so on, riding the streak as long as the letters match “ABRACADABRA.”

Why it’s a martingale. Each individual bet is fair (expected payout = stake). So the casino’s total outflow minus total inflow is a martingale. The casino takes in $1 per keystroke (one new gambler arrives). Let \(T\) be the stopping time (the word is completed). The total inflow is \(T\) dollars.

At time \(T\), who’s still alive? When “ABRACADABRA” first appears:

• The gambler who started 11 steps ago rode the entire word. Their stake grew: \($1 \to $26 \to $26^2 \to \cdots \to $26^{11}\). They hold \($26^{11}\).

• “ABRACADABRA” has “ABRA” as both a prefix and a suffix. So the gambler who started 4 steps ago saw “A-B-R-A” and is on a matching streak. They hold \($26^4\).

• The final “A” is also a prefix of length 1. The gambler who started 1 step ago matched “A.” They hold \($26^1\).

All other gamblers have busted out (hit a wrong letter).

Applying OST. The martingale is: (total casino outflow) \(-\) (total inflow) \(= 0\) in expectation. So:

$$ \E[\text{total payout}] = \E[\text{total inflow}] = \E[T]. $$

The total payout at time \(T\) is the sum of all surviving gamblers’ holdings:

$$ \E[T] = 26^{11} + 26^4 + 26^1. $$

That’s approximately \(3.67 \times 10^{15}\) keystrokes — an astronomically large number, dominated by the \(26^{11}\) term.

Solution

Let \(U\) and \(V\) be the two break points, uniform on \([0,1]\). Let \(X = \min(U,V)\) and \(Y = \max(U,V)\). The three piece lengths are:

$$ L_1 = X, \qquad L_2 = Y - X, \qquad L_3 = 1 - Y. $$

Note: \(L_1 + L_2 + L_3 = 1\).

When can three positive lengths form a triangle? The triangle inequality says no single piece can be longer than the sum of the other two. Since the sum of all three is 1, this simplifies to: no piece can be \(\geq 1/2\).

Crucial observation: at most one piece can be \(\geq 1/2\) (since they sum to 1). So the three “bad” events — \(L_1 \geq 1/2\), \(L_2 \geq 1/2\), \(L_3 \geq 1/2\) — are mutually exclusive. This means:

$$ \Pr[\text{no triangle}] = \Pr[L_1 \geq \tfrac{1}{2}] + \Pr[L_2 \geq \tfrac{1}{2}] + \Pr[L_3 \geq \tfrac{1}{2}]. $$

We compute each in the \((U, V)\) unit square.

$$ \Pr[L_1 \geq \tfrac{1}{2}] = \Pr[\min(U,V) \geq \tfrac{1}{2}] = \Pr[U \geq \tfrac{1}{2} \text{ and } V \geq \tfrac{1}{2}] = \left(\tfrac{1}{2}\right)^2 = \tfrac{1}{4}. $$ $$ \Pr[L_3 \geq \tfrac{1}{2}] = \Pr[1 - \max(U,V) \geq \tfrac{1}{2}] = \Pr[\max(U,V) \leq \tfrac{1}{2}] = \left(\tfrac{1}{2}\right)^2 = \tfrac{1}{4}. $$

\(\Pr[L_2 \geq 1/2] = \Pr[|U - V| \geq 1/2]\). In the unit square, this is the area of two triangles:

• \(U - V \geq 1/2\): triangle with vertices \((1/2, 0)\), \((1,0)\), \((1, 1/2)\), area \(= 1/8\).
• \(V - U \geq 1/2\): symmetric triangle, area \(= 1/8\).

Total: \(\Pr[L_2 \geq 1/2] = 1/4\).

So \(\Pr[\text{no triangle}] = 1/4 + 1/4 + 1/4 = 3/4\).

Solution

Real roots exist iff the discriminant is non-negative: \((2b)^2 - 4a \geq 0\), i.e., \(b^2 \geq a\).

In the unit square \((b, a) \in [0,1]^2\), this is the region below the parabola \(a = b^2\):

$$ \Pr[\text{real roots}] = \int_0^1 b^2 \, db = \frac{b^3}{3}\bigg|_0^1 = \frac{1}{3}. \quad\square $$

The technique: convert the algebraic condition to a geometric region, compute its area. When the boundary is a curve (parabola, circle), integrate; when it’s lines, use triangle/parallelogram formulas.

Solution

Let \(X, Y\) be their arrival times, uniform on \([0, 1]\) (in hours). They meet iff \(|X - Y| \leq 1/4\).

In the unit square, the favorable region is the strip between the lines \(Y = X - 1/4\) and \(Y = X + 1/4\). The unfavorable region consists of two corner triangles, each with legs \(3/4\):

$$ \Pr[\text{don't meet}] = 2 \cdot \frac{1}{2}\left(\frac{3}{4}\right)^2 = \frac{9}{16}. $$ $$ \Pr[\text{meet}] = 1 - \frac{9}{16} = \frac{7}{16}. \quad\square $$

General formula: with waiting time \(w\) (as a fraction of the window): \(\Pr[\text{meet}] = 1 - (1 - w)^2\).

Solution

The pieces form an \(n\)-gon iff no single piece exceeds \(1/2\) (no piece \(\geq\) sum of the rest). Let \(A_i\) = event that piece \(i > 1/2\).

Key observation: these events are disjoint — two pieces can’t both exceed half the total. And by symmetry, \(\Pr(A_i)\) is the same for all \(i\).

\(\Pr(A_1) = \Pr(\text{all } n - 1 \text{ cut points fall in the same half}) = (1/2)^{n-1}\).

Since the events are disjoint:

$$ \Pr[\text{some piece} > 1/2] = n \cdot \left(\frac{1}{2}\right)^{n-1} = \frac{n}{2^{n-1}}. $$ $$ \boxed{\Pr[\text{forms } n\text{-gon}] = 1 - \frac{n}{2^{n-1}}.} $$

Check \(n = 3\): \(1 - 3/4 = 1/4\). \(\checkmark\) (matches the broken stick triangle answer)

Check \(n = 4\): \(1 - 4/8 = 1/2\). Check \(n = 10\): \(1 - 10/512 \approx 0.98\).

The trick: when bad events are symmetric and disjoint, you skip inclusion-exclusion entirely and just multiply the count by one event’s probability.

Proof

The \(n\) uniform points divide \([0, 1]\) into \(n + 1\) gaps (spacings): the space before the smallest point, between consecutive points, and after the largest. By symmetry, the \(n + 1\) spacings are exchangeable — any permutation of them is equally likely. Since they sum to 1:

$$ \E[\text{each spacing}] = \frac{1}{n + 1}. $$

The \(k\)-th order statistic is the sum of the first \(k\) spacings:

$$ X_{(k)} = \text{(spacing 1)} + \text{(spacing 2)} + \cdots + \text{(spacing } k\text{)}. $$

By linearity: \(\E[X_{(k)}] = k \cdot \frac{1}{n+1} = \frac{k}{n+1}\). \(\quad\square\)

Solution

\(X_{(n)} - X_{(n-1)}\) is one of the \(n + 1\) spacings. By exchangeability, each spacing has the same expected value:

$$ \E[X_{(n)} - X_{(n-1)}] = \frac{1}{n + 1}. \quad\square $$

The surprise: the expected gap between the two largest points equals the expected gap between the two smallest, or between any other consecutive pair. The specific identity of “which gap” is irrelevant — exchangeability makes them all equal.

Solution

The \(n\) points cut the circle into \(n\) arcs. Each arc has expected length \(1/n\). So the arc containing \(P\) has expected length \(1/n\), right?

Wrong. The arc containing \(P\) is not a uniformly chosen arc. Longer arcs are more likely to contain \(P\) — this is size-biased sampling.

Here is the correct calculation. Think of the circle as \([0, 1)\) with endpoints identified, and place \(P\) at 0. The arc containing \(P\) is the gap between the largest point (going counterclockwise) and the smallest point (going clockwise) — equivalently, the gap containing 0 when \(n\) points are dropped on \([0, 1)\).

This gap is the sum of the first and last spacing on the line \([0, 1]\) when we “unwrap” the circle. But there is a cleaner argument: by symmetry, the \(n\) random points and the fixed point \(P\) form \(n + 1\) points, creating \(n + 1\) arcs on the circle, each with expected length \(1/(n+1)\). The arc containing \(P\) spans from the point just before \(P\) to the point just after, covering two of these \(n + 1\) spacings.

$$ \E[\text{arc containing } P] = \frac{2}{n + 1}. \quad\square $$

Check \(n = 1\): one point splits the circle into one arc of length 1. The arc containing \(P\) has length 1. Formula: \(2/2 = 1\). \(\checkmark\)

Solution

Let \(f(n)\) = number of length-\(n\) binary strings with no “HH.” A valid string either:

• ends in T: the first \(n - 1\) characters form any valid string of length \(n - 1\), or

• ends in TH: the first \(n - 2\) characters form any valid string of length \(n - 2\).

(It can’t end in HH — that’s forbidden.)

This gives the recurrence:

$$ f(n) = f(n - 1) + f(n - 2). $$

This is Fibonacci! With initial conditions \(f(1) = 2\) (H or T) and \(f(2) = 3\) (HT, TH, TT):

$$ f(n) = F_{n+2} \quad \text{(the } (n+2)\text{-th Fibonacci number)}. $$

The probability is:

$$ \Pr[\text{no HH in } n \text{ flips}] = \frac{F_{n+2}}{2^n}. $$

Growth rate: \(F_{n+2} \sim \varphi^{n+2}/\sqrt{5}\) where \(\varphi = (1 + \sqrt{5})/2 \approx 1.618\), so the probability decays like \((\varphi/2)^n \approx (0.809)^n\).

For \(n = 10\): \(F_{12} = 144\), so \(\Pr = 144/1024 \approx 14.1\%\). \(\quad\square\)

Solution

Condition on \(N\) (the tower property):

$$ \E[S] = \E[\E[S \mid N]] = \E[N \cdot \E[X]] = \E[N] \cdot \E[X]. $$

This is Wald’s identity: the expected sum of a random number of random variables equals the expected count times the expected individual value.

Example: a casino game lasts \(N \sim \text{Geometric}(1/4)\) rounds (expected 4 rounds). Each round you win \(X_i\) with \(\E[X_i] = 2\). Expected total winnings: \(\E[S] = 4 \cdot 2 = 8\). \(\quad\square\)

Solution

Condition on \(p\). Given \(p\), the number of flips is Geometric\((p)\) with mean \(1/p\). By the tower property:

$$ \E[\text{flips}] = \E\!\left[\E[\text{flips} \mid p]\right] = \E\!\left[\frac{1}{p}\right] = \int_0^1 \frac{1}{p} \, dp = \ln p \Big|_0^1. $$

This integral diverges. The expected number of flips is infinite.

Why: for any fixed \(p > 0\), you’d finish in finite expected time (\(1/p\) flips). But values of \(p\) near 0 — almost-all-tails coins — contribute \(\E[\text{flips} \mid p] \approx 1/p \to \infty\). Even though these coins are “rare” (small \(p\)), their contribution to the expectation is not integrable. The fat tail wins.

This is a “trust the math over intuition” answer. In interviews, it tests whether you can set up the tower property cleanly and accept a divergent answer when the math says so. \(\quad\square\)

Solution

The key decomposition: write \(Y\) as the part explained by \(X\) plus independent noise:

$$ Y = \rho X + \sqrt{1 - \rho^2} \, Z, \qquad Z \sim N(0,1), \quad Z \perp X. $$

Check: \(\E[Y] = 0\), \(\Var(Y) = \rho^2 + (1 - \rho^2) = 1\), \(\text{Corr}(X, Y) = \rho\). \(\checkmark\)

Now condition on \(X = x\). Since \(Z\) is independent of \(X\):

$$ \E[Y \mid X = x] = \rho x + \sqrt{1 - \rho^2} \cdot \E[Z] = \rho x + 0 = \rho x. $$ $$ \boxed{\E[Y \mid X = x] = \rho x.} $$

The conditional expectation of \(Y\) given \(X\) is the regression line through the origin with slope \(\rho\). This is the probabilistic foundation of linear regression: the best linear prediction of \(Y\) from \(X\) is exactly \(\rho X\).

Conditional variance: \(\Var(Y \mid X = x) = (1 - \rho^2) \cdot \Var(Z) = 1 - \rho^2\). This is the “unexplained” variance — the fraction of \(Y\)’s variability not captured by \(X\). When \(\rho = \pm 1\), the conditional variance is 0 (perfect prediction). When \(\rho = 0\), it equals 1 (knowing \(X\) tells you nothing about \(Y\)). \(\quad\square\)

Proof

Let \(n = a + b\). A counting sequence is a permutation of \(a\) copies of \(+1\) and \(b\) copies of \(-1\). There are \(\binom{n}{a}\) such sequences, each equally likely.

Step 1: The first vote must be for A (otherwise B is ahead immediately). This happens with probability \(a/n\).

Step 2: Given the first vote is for A, we have a path starting at height 1 with \(a-1\) remaining \(+1\) steps and \(b\) remaining \(-1\) steps, ending at height \(a - b\). We need this path to stay strictly above 0. Let’s count these “good” paths using the reflection principle.

Total paths from height 1 to height \(a - b\) in \(n - 1\) steps: \(\binom{n-1}{a-1}\).

“Bad” paths: those that touch height 0 at some point. Reflect the portion of the path before the first touch of 0 around the horizontal axis. This creates a bijection between bad paths (from height 1 to height \(a-b\), touching 0) and all paths from height \(-1\) to height \(a-b\) in \(n-1\) steps.

A path from \(-1\) to \(a - b\) in \(n - 1\) steps needs total displacement \(a - b + 1\), so it has \(a\) up-steps and \(b - 1\) down-steps. Number of such paths: \(\binom{n-1}{a}\).

Step 3: Good paths from height 1 = total minus bad:

$$ \binom{n-1}{a-1} - \binom{n-1}{a}. $$

Using \(\binom{n-1}{a} = \binom{n-1}{a-1} \cdot \frac{n - a}{a} = \binom{n-1}{a-1} \cdot \frac{b}{a}\):

$$ \binom{n-1}{a-1} - \binom{n-1}{a} = \binom{n-1}{a-1}\left(1 - \frac{b}{a}\right) = \binom{n-1}{a-1} \cdot \frac{a - b}{a}. $$

Step 4: The probability that A is always ahead, given the first vote is A:

$$ \frac{\binom{n-1}{a-1} \cdot \frac{a-b}{a}}{\binom{n-1}{a-1}} = \frac{a - b}{a}. $$

Step 5: Combining with the probability the first vote is A:

$$ \Pr[\text{A always ahead}] = \frac{a}{n} \cdot \frac{a - b}{a} = \frac{a - b}{n} = \frac{a - b}{a + b}. \quad \square $$

Solution

The strategy: fix a threshold \(r\) (we will optimize it later). Reject the first \(r\) candidates. Then accept the first subsequent candidate who is the best seen so far (i.e., better than all \(r\) candidates in the learning phase). If no such candidate appears, accept the last one.

Computing \(\Pr[\text{win}]\). The best candidate is in position \(k\) (for some \(k = 1, \ldots, n\), each equally likely). We select the best candidate if and only if:

1. The best is not in the learning phase: \(k > r\).
2. We don’t stop before reaching position \(k\): the best of the first \(k - 1\) candidates must be among the first \(r\) (otherwise someone in positions \(r+1\) through \(k-1\) would have been selected first).

\(\Pr[\text{best of first } k-1 \text{ is in first } r] = r/(k-1)\) (each of the \(k-1\) candidates is equally likely to be the best among them).

$$ \begin{aligned} \Pr[\text{win} \mid \text{strategy } r] &= \sum_{k=r+1}^{n} \Pr[\text{best at position } k] \cdot \Pr[\text{don't stop early} \mid k] \\ &= \sum_{k=r+1}^{n} \frac{1}{n} \cdot \frac{r}{k-1}. \end{aligned} $$ $$ = \frac{r}{n} \sum_{k=r+1}^{n} \frac{1}{k-1} = \frac{r}{n} \sum_{j=r}^{n-1} \frac{1}{j}. $$

Optimizing \(r\) for large \(n\). For large \(n\), the sum is approximately an integral:

$$ \frac{r}{n} \sum_{j=r}^{n-1} \frac{1}{j} \approx \frac{r}{n} \int_r^n \frac{dx}{x} = \frac{r}{n} \ln\frac{n}{r}. $$

Let \(t = r/n\) (the fraction of candidates in the learning phase). Then:

$$ \Pr[\text{win}] \approx -t \ln t. $$

Maximize: \(\frac{d}{dt}[-t\ln t] = -\ln t - 1 = 0\), giving \(t^* = 1/e\). The optimal success probability is:

$$ \Pr[\text{win}] = \frac{1}{e} \cdot \ln(e) = \frac{1}{e} \approx 0.368. $$

Solution: Backward Induction

Solve from the last decision and work backward — this is the universal method for finite-horizon stopping problems.

Round 3 (forced): you must keep whatever you roll. \(\E[\text{payout}] = 3.5\).

Round 2: you see a face \(x\). Keep if \(x > 3.5\) (better than the expected value of being forced in round 3), re-roll if \(x \leq 3.5\). So keep on 4, 5, 6; re-roll on 1, 2, 3.

$$ \E[\text{round 2}] = \frac{1}{2} \cdot \frac{4 + 5 + 6}{3} + \frac{1}{2} \cdot 3.5 = \frac{1}{2}(5) + \frac{1}{2}(3.5) = 4.25. $$

Round 1: keep if \(x > 4.25\), i.e., keep on 5 or 6; re-roll on 1, 2, 3, 4.

$$ \E[\text{round 1}] = \frac{2}{6} \cdot \frac{5 + 6}{2} + \frac{4}{6} \cdot 4.25 = \frac{1}{3}(5.5) + \frac{2}{3}(4.25) = \frac{14}{3} \approx 4.667. $$

Optimal policy: round 1 keep 5–6, round 2 keep 4–6, round 3 forced. Expected payout: \(14/3\).

The principle: at each round, the threshold = expected value of continuing. The thresholds decrease as you approach the deadline (you become less picky as time runs out). This is backward induction — the same logic behind the secretary problem, taken to its most explicit form.

Proof

To form a cycle of length \(\ell\):

1. Choose \(\ell\) elements from \(n\): \(\binom{n}{\ell}\) ways.
2. Arrange them in a cycle: \((\ell - 1)!\) ways (fix one element, arrange the remaining \(\ell - 1\) in a line).
3. The remaining \(n - \ell\) elements can form any permutation: \((n - \ell)!\) ways.

Number of permutations with a cycle of length \(\ell\) containing specific elements is \((\ell-1)! \cdot (n-\ell)!\). Total permutations with any such cycle:

$$ \begin{aligned} \binom{n}{\ell} \cdot (\ell-1)! \cdot (n-\ell)! &= \frac{n!}{\ell!(n-\ell)!} \cdot (\ell-1)! \cdot (n-\ell)! \\ &= \frac{n!}{\ell}. \end{aligned} $$

Dividing by the total \(n!\) permutations:

$$ \Pr[\text{cycle of length } \ell] = \frac{n!/\ell}{n!} = \frac{1}{\ell}. \quad \square $$

Solution

The strategy: prisoner \(k\) starts at drawer \(k\) and follows the chain. They succeed iff their cycle has length \(\leq 50\).

All prisoners succeed iff every cycle has length \(\leq 50\), i.e., the longest cycle has length \(\leq 50\).

Key observation: a random permutation of \(\{1, \ldots, 100\}\) can have at most one cycle of length \(> 50\) (because such a cycle uses more than half the elements, leaving no room for another long cycle). So:

$$ \Pr[\text{longest cycle} > 50] = \Pr\!\left[\bigcup_{\ell=51}^{100} \{\text{cycle of length } \ell \text{ exists}\}\right]. $$

Since these events are mutually exclusive (at most one long cycle):

$$ = \sum_{\ell=51}^{100} \Pr[\text{cycle of length } \ell] = \sum_{\ell=51}^{100} \frac{1}{\ell} = \frac{1}{51} + \frac{1}{52} + \cdots + \frac{1}{100}. $$

This is a partial sum of the harmonic series. Using the integral approximation:

$$ \sum_{\ell=51}^{100} \frac{1}{\ell} \approx \int_{50}^{100} \frac{dx}{x} = \ln\frac{100}{50} = \ln 2 \approx 0.6931. $$

So:

$$ \Pr[\text{all succeed}] = 1 - \sum_{\ell=51}^{100} \frac{1}{\ell} \approx 1 - \ln 2 \approx 0.3069. $$