#probability#induction

Non-Markovian Paper Toss Challenge: 298 Wins

· Updated January 5, 2024
You toss paper 300 times into a bin. You miss the first but nail the second one. Subsequently, your chance of hitting the bin equals your cumulative win rate. What is the probability of hitting the bin exactly 298 times out of 300 throws?

Setting Up the Model

Let’s define:

  • YiY_i — indicator random variable: 1 if the ii-th toss is a hit, 0 otherwise
  • Xn=∑i=1nYiX_n = \sum_{i=1}^{n} Y_i — total hits after nn tosses
  • The transition rule: P(Yn=1∣Y1,…,Yn−1)=Xn−1n−1P(Y_n = 1 \mid Y_1, \ldots, Y_{n-1}) = \frac{X_{n-1}}{n-1}

Initial conditions: Y1=0Y_1 = 0 (miss), Y2=1Y_2 = 1 (hit), so X2=1X_2 = 1.

Pattern Recognition

Working through small cases makes the structure visible:

nnFeasible values of XnX_nProbability of each
2{1}\{1\}1
3{1,2}\{1, 2\}12\frac{1}{2} each
4{1,2,3}\{1, 2, 3\}13\frac{1}{3} each

The pattern suggests: for any nn, all n−1n-1 feasible values of XnX_n are equally likely with probability 1n−1\frac{1}{n-1}.

Proof by Induction

Claim: P(Xn=k)=1n−1P(X_n = k) = \frac{1}{n-1} for k∈{1,2,…,n−1}k \in \{1, 2, \ldots, n-1\}.

Base case (n=3n = 3): P(X3=1)=P(X3=2)=12P(X_3 = 1) = P(X_3 = 2) = \frac{1}{2}. ✓

Inductive step: Assume P(Xn−1=j)=1n−2P(X_{n-1} = j) = \frac{1}{n-2} for all feasible jj. We show P(Xn=k)=1n−1P(X_n = k) = \frac{1}{n-1}.

Case k=1k = 1: The only path is Xn−1=1X_{n-1} = 1 and the nn-th toss misses.

P(Xn=1)=P(Xn−1=1)⋅n−2n−1=1n−2⋅n−2n−1=1n−1P(X_n = 1) = P(X_{n-1} = 1) \cdot \frac{n-2}{n-1} = \frac{1}{n-2} \cdot \frac{n-2}{n-1} = \frac{1}{n-1}

Case k>1k > 1: Two paths lead here — hit on toss nn from Xn−1=k−1X_{n-1} = k-1, or miss on toss nn from Xn−1=kX_{n-1} = k.

P(Xn=k)=P(Xn−1=k−1)⋅k−1n−1+P(Xn−1=k)⋅n−1−kn−1P(X_n = k) = P(X_{n-1} = k-1) \cdot \frac{k-1}{n-1} + P(X_{n-1} = k) \cdot \frac{n-1-k}{n-1}

Substituting the inductive hypothesis P(Xn−1=j)=1n−2P(X_{n-1} = j) = \frac{1}{n-2}:

=1n−2⋅k−1n−1+1n−2⋅n−1−kn−1=1n−2⋅(k−1)+(n−1−k)n−1=1n−2⋅n−2n−1=1n−1= \frac{1}{n-2} \cdot \frac{k-1}{n-1} + \frac{1}{n-2} \cdot \frac{n-1-k}{n-1} = \frac{1}{n-2} \cdot \frac{(k-1) + (n-1-k)}{n-1} = \frac{1}{n-2} \cdot \frac{n-2}{n-1} = \frac{1}{n-1}

□\square

Answer

For n=300n = 300, all values X300∈{1,2,…,299}X_{300} \in \{1, 2, \ldots, 299\} are equally likely. Therefore:

P(X300=298)=1299≈0.33%\boxed{P(X_{300} = 298) = \frac{1}{299} \approx 0.33\%}

Video Walkthrough

There’s also a natural extension: what if the miss rate decreases with each miss? The structure of the proof changes but a uniformity result still holds — worked out in the video above.