Minimum tickets required for specified probability of winning lottery

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.

Answer

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=50000000 and m=5000000. 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

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\%

Attribution
Source : Link , Question Author : Queops , Answer Author : cardinal

Leave a Comment