# A lottery will be held. From 1000 numbers, one will be randomly chosen as the winner.

A lottery will be held. From 1000 numbers, one will be randomly chosen as the winner. A lottery ticket is a random number between 1 and 1000 with replacement.

How many tickets do you need to buy for the probability of winning to be at least 50%?

I am having trouble starting this problem and was told to find the probability of no winning tickets out of n tickets.

If there wasn't replacement then the probability would just increase by a thousandth with every new ticket, but I am unsure of how the possibility of buying two tickets that are the same affects the increase in probability from having multiple tickets

• You may want to check birthday paradox. – Chayan Ghosh Feb 12 at 3:47
• Hello and welcome to math.stackexchange. Here is a way to think about it. You buy a lottery ticket (with a random number printed on it) every day. The prob. of not winning on the first day is obviously 0.999. The prob. of not winning on days 1 and 2 is $0.999 \cdot 0.999$ since these two events are assumed to be independent (that's what "with replacement" means). The prob. of not winning on days 1 - 7 is $0.999^7 \approx 0.99302$, so the probability of winning on one of these days is now 0.00298 or 0.298%. The prob. of not winning $n$ days in a row is $1 - 0.999^n$. Make that prob. $>0.5$. – Hans Engler Feb 12 at 3:58
• Thanks for the suggestion and I will check it out, but I think that the question is asking how many tickets do you have to buy for 1 drawing, not a drawing every day. So you would already have all the tickets and you aren't buying a new one every day, you are justing buying them all at once and there is only one drawing, right? – hmtkd Feb 12 at 4:05

You need $$500$$ distinct numbers to have a $$50\%$$ chance of winning. This is the coupon collector's problem except that you do not need to collect all the coupons. We can compute the expected number to get $$500$$ distinct numbers. The first coupon is guaranteed to get a new number. To get a second new number takes on average $$\frac {1000}{999}$$. Once you have two, the third takes $$\frac {1000}{998}$$ and so on. We can compute the expected number to get $$500$$ distinct numbers as as \begin {align} 1+\frac {1000}{999}+\frac {1000}{998}+\ldots \frac {1000}{501}&=1000(H_{1000}-H_{500})\\ &\approx 1000(\log(1000)-\log (500))\\&=1000\log (2)\\ &\approx 693 \end {align} This gives the expected number of days to get $$500$$ different tickets. It is close to, but not guaranteed to be the same as, the number of days to get your chance of $$500$$ distinct tickets over $$50\%$$. I don't have a good way to calculate the second of these. I suspect the $$693$$ is an overestimate of the number of days to have a $$50\%$$ chance to have $$500$$ different because there will be a long tail.
• I don't think "the expected number of days to get 500 distinct numbers" is the same as "the fixed number such that if you wait that many days your chance of winning is $\frac12$". Or at least if it is the same it is not obvious that it is the same. – Henning Makholm Feb 12 at 4:26
• Consider for example, a game where you get the tickets by a different random process than coupon collection: You get the 500 lowest-numbered tickets either all on day 1 or all on day 99, with probability $\frac 12$ each, and the 500 remaining tickets on day 100 in any case. Then the expected number of days until you have 500 tickets is 50, but if you decide in advance to play just one day of the game your chance of winning is already 50%. – Henning Makholm Feb 12 at 4:26
• It's quite darn close, actually. The approach in Hans Engler's comment (which I find convincing) leads to the answer being $$\frac{-\log 2}{\log(1-\frac{1}{1000})}$$ which is approximated neatly by your $1000\log 2$. – Henning Makholm Feb 12 at 4:36