How many balls in the urn?
Probability ; Difficulty: medium
How many balls in the urn?
This week’s Riddler Classic is a statistical parameter estimation exercise. The Classic reproduced:
This week’s Classic may seem nonsensical at first. But surely there’s more to it …
You have an urn with an equal number of red balls and white balls, but you have no information about what that number might be. You draw 19 balls at random, without replacement, and you get eight red balls and 11 white balls. What is your best guess for the original number of balls (red and white) in the urn?
*spoiler alert* solution and answer follow below
Building intuition
I’m not sure why Zach writes that this may seem nonsensical. This is a problem of the kind that is frequently encountered in statistical endeavors: estimating parameters of a distribution from a sample. For example, I remember reading about total actual crime estimation based on reported crime when most crime goes unreported.
One of the most popular estimation methodologies is Maximum Likelihood Estimation. Conceptually, applied to this problem, all it says is that for all the possible values of \(n\) – the number of balls of each type, the value of \(n\) that results in the highest probability of observing the given result, is our best guess of \(n\).
So let’s calculate the probability of getting 8 red and 11 white balls, if the urn has \(n\) balls of each, red and white.
Probability of the observed values as a function of n:
Consider arranging \(2n\) balls equally split between red and white in a row. We can pick \(n\) slots from the \(2n\) for the red ones in \( \displaystyle \ {2n \choose n} \) equally likely ways with the white ones taking the other slots. The number of ways in which the first 19 balls have 8 red and 11 white is just the number of ways of choosing 8 slots out of 19 for the red and then choosing \(n-8\) slots out of the remaining \(2n – 19\) slots.
This is: \( \displaystyle \ {19 \choose 8} \cdot \ {2n – 19 \choose n-8} \)
So the required probability of getting 8 red and 11 white with 19 balls given there are \(n\) of each color is :
\[
P(\textit{8 red and 11 white }| \textit{ n of each color}) = \frac{\displaystyle \ {19 \choose 8} \cdot \ {2n – 19 \choose n-8}
}{\displaystyle \ {2n \choose n}}
\]
Now the maximum likelihood estimate of \(n\) is just the value of \(n\) for which the above probability is the largest.
This is easily determined by calculating the probability for different values of \(n\) as shown in the chart below.
It is seen that \(n = 17\) maximizes the value. So the Max Likelihood Estimate is 34 balls—17 each of red and white.
It can be shown fairly easily that that as \(n\) increases, the above probability function converges to:
\( \displaystyle \frac{19!}{8! \ 11! \ 2^{19}} \approx 0.14416 \)
Does not work for all sample combinations of 19 balls!
It’s natural to believe that this method could be applied to other mix of results for the 19 balls. Interestingly, it turns out this is not the case. For (red, white) values of 19 balls outside of (8,11), (9,10), (10,9) and (11,8), the probability as a function of \(n\) is a uniformly increasing but converging function of \( n\).
For example, if the 19 balls resulted in 7 red and 12 white balls, the probability of this occurrence as a function of \(n\) is given by:
\[
P(\textit{7 red and 12 white }| \textit{ n of each color}) = \frac{\displaystyle \ {19 \choose 7} \cdot \ {2n – 19 \choose n-7}
}{\displaystyle \ {2n \choose n}}
\]
This uniformly increases from \(n = 12\) and converges to \( \displaystyle \frac{19!}{7! \ 12! \ 2^{19}} \approx 0.09611 \)
This implies that larger the value of \(n\), larger the likelihood of this sample.
Why does this happen?
Intuitively, the gap between the color counts is more likely to be small when there are fewer balls in the urn. For example, if the urn had 11 balls of each color, the maximum difference between the color counts when drawing 19 balls can only be 3.
Conversely, the gap between the color counts is likely to be higher when the number of balls increases.
As a result, for any sample size, there occurs a count difference beyond which the most likely number of balls in the urn tends to infinity!
So what do we guess in these instances?
So what should we guess if the samples of 19 revealed 7 red and 12 white balls? Practicality suggests that the urn cannot be infinitely large and so we would guess as high a number of balls as we believe the urn can actually hold (say 100).
This is based on an à priori belief that is refined upon observation. This interestingly leads to another type of estimator: The Bayes Estimator which we discuss next.
Bayes Estimation
The Bayesian approach to probability and statistics treats unknowns not as having a having a fixed value but as having a probability distribution (the prior) driven by expectation/intuition. Further data then helps us refine this expected probability distribution (the posterior).
How would we apply this to our current problem, say when the sample is 7 red and 12 white?
To begin, we need to pick what our expectations are of the distribution of \(n\) – the number of balls of each color prior to the sampling. The choices are infinite, but I highlight two where we assume that the urn can hold a maximum of 100 (50 of each color):
- There is an equal likelihood of the urn containing anywhere between 1 and \(N = 50\) balls of each color. i.e. uniform distribution
- The probability of the urn containing \(n\) balls is distributed binomially with \(N = 50\), \(n\) tries and probability 0.5
Let \(S\) be the observed sample of 7 red and 12 white balls. Applying basic Bayes theorem:
\begin{align*}
P(n| S) &= \frac{P(S|n) \ P(n)}{P(S)} \\
\textit{Now } \qquad P(S|n) &= \frac{\ {19 \choose 7} \cdot \ {2n – 19 \choose n-7}}{\ {2n \choose n}} \\
\textit{Also }\qquad P(S) &= \sum_{i=1}^{N}P(S | n = i)P(n = i) \\
\textit{And } \qquad P(n = i) &= \frac{1}{N} &&\textit{ (in the uniform prior case 1)} \\
\textit{And } \qquad P(n = i) &= {N \choose i}p^i (1-p)^{N-i} &&\textit{ (in the binomial prior case 2)}
\end{align*}
We can thus calculate the posterior in each of our two cases. The prior and the posterior are shown below for the two cases.
Case 1: the uniform prior gives us a posterior that is 0 for values below \(n=11\) (as it should) and then increasing but converging with max probability at \(n = 50 \) as expected. We’d guess 50 balls of each color.
Case 2: The binomial prior gives a posterior that is largely unchanged because the red and and white counts are still quite similar. In this case we’d guess the max value (also ~ the expected value) = 25 balls of each color.
Conclusion:
- The maximum likelihood estimate for the original question is 17 balls of each color.
- With a uniform prior, the Bayes estimate for the original question with 8 red and 11 white is the same 17 as the maximum likelihood estimate
- With a binomial prior, we would pick what turns out to be just the expected value of the prior = 25.