Binomial ducks
Last weekend, Regensburg hosted a somewhat unusual event: a “duck race.” The organizers threw 6,000 rubber ducks into a shallow canal with virtually still water. The ducks were slowly drifting towards the finish line. How did they make the ducks move in still water? They used high-pressure water streams from hoses to push the water around the ducks towards the finish line. You will be excused for thinking that this is a dumb idea. It does not make for a particularly exciting race. On the other hand, there were people involved who were in the water, so doing that in a shallow canal with still water is safer than doing that in a river with a current. On the plus side, this was the biggest amount of ducks I have ever seen.
People could buy lottery tickets, one for each duck, and the first 100 ducks that finished yielded prizes. As an economist, that got me thinking about what are the chances of winning in this lottery. We bought three tickets. To my shame, I could not immediately come up with a good answer. It is easy to compute the probability of winning if there is a single winner, which is just $1/n$, or, if you bought $m$ tickets, $m/n$. But what happens if the first 100 tickets win? What usually helps here is developing intuition through the simplest examples.
Suppose there are just three tickets: A, B, C. Let’s say you bought ticket A. Two randomly chosen tickets yield prizes. What is the probability of winning a prize? Since two tickets are picked at random, we need to consider all possible pairs of tickets (or combinations). These are AB, AC, BC. There are three possible outcomes, two of which lead to a prize. Hence, the probability of winning is 2⁄3.
Now let’s suppose there are four tickets: A, B, C, D. Again, assume that you bought ticket A. Now there are six possible combinations of two tickets: AB, AC, AD, BC, BD, CD. Three of them lead to a prize, hence the probability of winning is 3⁄6=1⁄2.
It is easy to see the pattern. If there are $n$ tickets in total and $k$ randomly chosen tickets win, the total number of possibilities, which is the number of combinations of $k$ elements from the set of $n$ elements, is simply $\binom{n}{k}$. In the first example, it was $3 = \binom{3}{2}$. In the second example, it was $6 = \binom{4}{2}$. But what is the number of winning combinations? It seems that it is easier to find the number of non-winning combinations. This is just the total number of combinations of $k$ elements that do not include our ticket: $\binom{n-1}{k}$. In the first example, this was $1 = \binom{3-1}{2}$. In the second example, this was $3 = \binom{4-1}{2}$. Then the number of winning combinations is the difference between the total number of combinations and the number of non-winning combinations.
Now we can compute the probability of winning:
$$
\begin{align}
p &= \frac{\binom{n}{k} - \binom{n - 1}{k}}{\binom{n}{k}}
&= 1 - \frac{\binom{n-1}{k}}{\binom{n}{k}}
&= 1 - \frac{\frac{(n-1)!}{k!(n-1-k)!}}{\frac{n!}{k!(n-k)!}}
&= 1- \frac{(n-1)!(n-k)!}{n!(n-k-1)!}
&= 1 - \frac{n-k}{n}
&= \frac{k}{n},
\end{align}
$$
which turns out to be super simple: it’s just the number of the randomly chosen winning tickets over the total number of tickets. What is interesting is that buying one ticket and having $k$ winning tickets gives you the same probability of winning as if a single ticket won, but you bought $k$ tickets.
Perhaps one could derive this formula easier, but thinking about the total number of combinations and the number of non-winning combinations makes sense to me. Applying the formula to the duck race, we get a probability of winning $p = 100⁄6000 \approx 0.017$, about 2%.
What if you bought more than one ticket, though? What is the probability of having at least one ticket win? It cannot be simply the sum of probabilities of a single ticket winning. In the duck race, if you buy 100 tickets, your probability of winning cannot be $100\times 0.017 = 1.7$.
Let’s start slow. Suppose there are four tickets: A, B, C, D. But now assume that you bought tickets A and B. There are still six possible combinations of two tickets: AB, AC, AD, BC, BD, CD. But now five of them lead to a prize, hence the probability of winning is 5⁄6. Clearly, what changes here is the number of non-winning combinations. If you buy $m$ tickets, then this number is $\binom{n-m}{k}$, which in this example is $1 = \binom{4-2}{2}$. So in general, the probability of winning is
$$
\begin{align}
p &= 1 - \frac{\binom{n-m}{k}}{\binom{n}{k}}
&= 1 - \frac{\frac{(n-m)!}{k!(n-m-k)!}}{\frac{n!}{k!(n-k)!}}
&= 1 - \frac{(n-m)!(n-k)!}{n!(n-k-m)!}
&= 1 - \frac{(n-k)(n-k-1)\cdots(n-k-m+1)}{n(n-1)\cdots(n-m+1)},
\end{align}
$$
which, unfortunately, does not seem to simplify further. In our case, we bought three tickets, which implies a probability of winning of
$$
p = 1 - \frac{\binom{6000-3}{100}}{\binom{6000}{100}} \approx 0.049
$$
or about 5%, which is not bad. We did not win anything, though.