Polya Urn Free Kicks
Cristiano Ronaldo is practicing free kicks. He takes 100 shots total. He scores his first free kick and misses his second. For $n \geq 3$, the probability that he scores the $n$th free kick equals the fraction of the first $n-1$ kicks that he scored. For example, if he has scored 17 of his first 30, the probability he scores the 31st is $17/30$.
Find the probability that Ronaldo scores exactly 40 of the 100 free kicks.
Hints
- The specific number 40 is a red herring. Try computing $p(k,n)$ for small values of $n$ and see if you notice a pattern across different values of $k$.
- Set up a recurrence by conditioning on the $n$th kick. If kick $n$ is a goal, there were $k-1$ goals in the first $n-1$ kicks; if a miss, there were $k$ goals in the first $n-1$.
- For $n = 4$, you should find $p(1,4) = p(2,4) = p(3,4) = 1/3$. The conjecture $p(k,n) = 1/(n-1)$ can be verified by substitution into the recurrence.
Worked Solution
How to Think About It: This is a Polya urn model. After the first two kicks (one goal, one miss), we have 1 "success ball" and 1 "failure ball" in the urn. Each subsequent kick draws a ball, and the result goes back in with reinforcement. The beautiful thing about the Polya urn is that it has a hidden symmetry: every sequence of $k$ goals and $n-k$ misses (in any order) is equally likely. This means the final count $k$ is uniformly distributed over all feasible values.
Quick Estimate: Since the first kick is always a goal and the second is always a miss, we need the number of goals in kicks 3 through 100 (that is, 98 additional kicks) to be exactly 39. If the distribution turns out to be uniform over the feasible values $k = 1, \ldots, n-1$ for $n$ total kicks, then $P(k = 40) = 1/99$. Let us verify this.
Approach: Derive a recurrence relation for $p(k,n) = P(\text{exactly } k \text{ goals in } n \text{ kicks})$, compute small cases, conjecture the pattern, and verify by induction.
Formal Solution:
Let $p(k,n)$ be the probability of exactly $k$ goals in $n$ kicks, where $1 \leq k \leq n-1$ (since the first kick is a goal and the second is a miss).
Conditioning on the $n$th kick:
- If Ronaldo scores kick $n$: he must have had $k-1$ goals in the first $n-1$ kicks, and the probability of scoring is $(k-1)/(n-1)$. Contribution: $\frac{k-1}{n-1} \cdot p(k-1, n-1)$.
- If Ronaldo misses kick $n$: he must have had $k$ goals in the first $n-1$ kicks, and the probability of missing is $1 - k/(n-1) = (n-1-k)/(n-1)$. Contribution: $\frac{n-1-k}{n-1} \cdot p(k, n-1)$.
This gives the recurrence:
$$p(k,n) = \frac{k-1}{n-1}\, p(k-1, n-1) + \frac{n-1-k}{n-1}\, p(k, n-1)$$
Base cases: $p(1,1) = 1$ (first kick is a goal), $p(1,2) = 1$ (after two kicks, exactly 1 goal with certainty).
Small cases:
- $n = 3$: $p(1,3) = \frac{0}{2} \cdot p(0,2) + \frac{1}{2} \cdot p(1,2) = \frac{1}{2}$ and $p(2,3) = \frac{1}{2} \cdot p(1,2) + \frac{0}{2} \cdot p(2,2) = \frac{1}{2}$.
- $n = 4$: Computing all three values gives $p(1,4) = p(2,4) = p(3,4) = \frac{1}{3}$.
Conjecture: $p(k,n) = \frac{1}{n-1}$ for all $1 \leq k \leq n-1$.
Verification by substitution: Plug $p(k,n) = 1/(n-1)$ and $p(\cdot, n-1) = 1/(n-2)$ into the recurrence:
$$\frac{k-1}{n-1} \cdot \frac{1}{n-2} + \frac{n-1-k}{n-1} \cdot \frac{1}{n-2} = \frac{(k-1) + (n-1-k)}{(n-1)(n-2)} = \frac{n-2}{(n-1)(n-2)} = \frac{1}{n-1}$$
The conjecture is verified.
Answer:
$$P(\text{exactly 40 goals in 100 kicks}) = \frac{1}{100 - 1} = \frac{1}{99}$$
Intuition
This is a Polya urn process, one of the most elegant models in probability. The key property is exchangeability: the probability of any particular sequence of goals and misses depends only on the total counts, not on the order. This implies that the number of goals $k$ after $n$ kicks is uniformly distributed over $\{1, 2, \ldots, n-1\}$, regardless of what $k$ is. The answer $1/(n-1)$ is completely independent of $k$ -- whether you ask for 2 goals or 98 goals out of 100, the probability is the same.
Polya urns show up in Bayesian nonparametrics (the Chinese restaurant process), in models of preferential attachment (rich-get-richer dynamics), and in adaptive clinical trial design. The deep reason the uniform distribution appears is that the Polya urn with 1 success and 1 failure ball is equivalent to drawing a random bias $p \sim \text{Uniform}(0,1)$ and then flipping a coin with that bias. The Beta(1,1) prior is uniform, and the resulting marginal distribution over counts is uniform. This is a beautiful instance of de Finetti's theorem in action.