7
$\begingroup$

In a lottery, 1/10 of the 50 000 000 tickets give a prize.

What is the minimum amount of tickets one should buy to have at least a 50% chance to win?

Would be very glad if you could explain your methodology when resolving this. Please consider this as homework if you will.

$\endgroup$
15
$\begingroup$

I should really ask what your thoughts are so far on this. This problem is very closely related to the "birthday problem". The easiest way to do these problems is to count the possible ways of either winning or losing. Usually one is much easier to do than the other, so the key is to find the right one. Before we get into the actual calculation, let's start with some heuristics.


Heuristics: Let $n$ be the total number of tickets and $m$ be the number of winning tickets. In this case $n = 50\,000\,000$ and $m = 5\,000\,000$. When $n$ is very large then purchasing multiple distinguishable tickets is almost the same as sampling with replacement from the population of tickets.

Let's suppose that, instead of having to purchase $k$ separate tickets, we purchased a ticket, looked to see if it was a winner and then returned it to the lottery. We then repeat this procedure where each such draw is independent from all of the previous ones. Then the probability of winning after purchasing $k$ tickets is just $$ \Pr( \text{we won} \mid \text{purchased $k$ tickets} ) = 1 - \left(\frac{n-m}{n}\right)^k . $$

For our case then, the right-hand side is $1 - (9/10)^k$ and so we set this equal to $1/2$ and solve for $k$ in order to get the number of tickets.

But, we're actually sampling without replacement. Below, we'll go through the development, with the point being that the heuristics above are more than good enough for the present problem and many similar ones.


There are $50\,000\,000$ tickets. Of these $5\,000\,000$ are winning ones and $45\,000\,000$ are losing ones. We seek

$$ \Pr(\text{we win}) \geq 1/2 \>, $$

or, equivalently,

$$ \Pr(\text{we lose}) \leq 1/2 . $$

The probability that we lose is simply the probability that we hold none of the winning tickets. Let $k$ be the number of tickets we purchase. If $k = 1$, then $\Pr(\text{we lose}) = 45\,000\,000 / 50\,000\,000 = 9/10 \geq 1/2$, so that won't do. If we choose two tickets then there are $45\,000\,000 \cdot 44\,999\,999$ ways to choose two losing tickets and there are $50\,000\,000 \cdot 49\,999\,999$ ways to choose any two tickets. So,

$$ \Pr( \text{we lose} ) = \frac{45\,000\,000 \cdot 44\,999\,999}{50\,000\,000 \cdot 49\,999\,999} \approx 0.9^2 = 0.81. $$

Let's generalize now. Let $m$ be the number of winning tickets and $n$ the total number of tickets, as before. Then, if we purchase $k$ tickets,

$$ \Pr(\text{we lose}) = \frac{(n-m) (n-m-1) \cdots (n-m-k+1)}{n (n-1) \cdots (n-k+1)} . $$

It would be tedious, but we can now just start plugging in values for $k$ until we get the probability below $1/2$. We can use a "trick", though, to get close to the answer, especially when $n$ is very large and $m$ is relatively small with respect to $n$.

Note that $\frac{n-m-k}{n-k} \leq \frac{n-m}{n}$ for all $k < m < n$. Hence

$$ \Pr(\text{we lose}) = \frac{(n-m) (n-m-1) \cdots (n-m-k+1)}{n (n-1) \cdots (n-k+1)} \leq \left(1 - \frac{m}{n} \right)^k , $$

and so we need to solve the equation $\left(1 - \frac{m}{n} \right)^k = \frac{1}{2}$ for $k$. But,

$$ k = \frac{\log \frac{1}{2}}{\log (1 - \frac{m}{n})} \>, $$

and so when $m/n = 1/10$, we get $k \approx 6.58$.

So, $k = 7$ tickets ought to do the trick. If you plug it in to the exact equation above, you'll get that

$$ \Pr( \text{we win} \mid \text{k=7} ) \approx 52.2\% $$

$\endgroup$
  • $\begingroup$ Very detailed. I loved it. Thank you and I'll consider it as an answer unless someone comes up with something else. $\endgroup$ – Queops Feb 7 '11 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.