On December 13, 2009, Marilyn was asked, by Stephanie Beaupre of Sharon, Mass., about a raffle where you have tickets that represent chances on any one of ten individual prizes. Each prize has a basket, into which you can put as many tickets as you want. Stephanie asked for the strategy that gives you the best chance of winning with 100 tickets: should you put them all in one basket, or spread them out?
Marilyn gave a three separate answers, based on what information you have access to before the winning tickets are drawn.
(1) If you can estimate the relative number of tickets in each basket, you should wait to be the last person to put your tickets in. Then, put all 100 in the basket that appears to have the fewest.
(2) If you can't estimate the number of tickets in the baskets, you should put them all in the basket with the least valuable prize.
(3) If you can't estimate the numbers and all prizes are of equal value, it doesn't matter what strategy you use.
Marilyn apparently gave these three answers to make up for necessary information that was missing in the question. Unfortunately, she left out one other bit: Are we trying to maximize the chance of winning anything, so that winning two prizes is just as good as winning one? Or is it to be considered twice as good, so that we really want to maximize the expected value? The answer doesn't change the strategy you use, but it does change how one goes about proving it. I'll assume that you just want to win something. The probability we want to maximize is thus:
P(WIN) = 1 - P(Don't Win Prize #1)*P(Don't Win Prize #2)*...*P(Don't Win Prize #10)
(1) It is likely that the rules of the raffle would prevent you from accomplishing Marilyn's first strategy. Every other participant should be able to arrive at the same conclusion, and so try to be the last person for that same basket. That could lead to a riot. But assuming you can, it is only correct as long as your 100 tickets do not make that basket have more tickets than another. In such a case, you will do better by dividing your tickets so that the two lowest, as estimated before you place your 100 tickets, have the same number afterwards.
Proof: Assume you estimate that the two least popular baskets have M and N tickets, respectively. Further assume that N>0, M>0, and |N-M|<100. You add X tickets to the first, where 0<=X<=100; and (100-X) to the second. You will have no chance of winning any of the other prizes, so those terms can be left out of the equation since they all multiply by 1. Your chances of winning are thus:
P(X) = 1 - P(Don't Win Prize with M) * P(Don't Win Prize with N)
P(X) = 1 - (M/(M+X)) * (N/(N+100-X))
P(X) = 1 - M * N (M+X)^-1 * (N+100-X)^-1
Taking the derivative w.r.t. X, and setting to zero, we get:
P'(X) = 0 = M*N*( (M+X)^-1 * (N+100-X)^-2 - (M+X)^-2 * (N+100-X)^-1 )
Multiply both sides by M^-1 * M^-1 * (M+X)^2 * (N+100-X)^2, which is well defined and non-zero.
0 = (M+X) - (N+100-X)
2X = N-M+100
X = 50 + (N-M)/2
100-X = 50 + (M-N)/2
Final # tickets in first basket = M+X = 50 + (N+M)/2
Final # tickets in second basket = N+(100-X) = 50 + (N+M)/2
In fact, this is a general result: When choosing how to distribute tickets between two baskets, it is best to end up with them having the same number as your best estimate of the numbers.
(2) Marilyn's second answer is probably the most complicated to prove, but the easiest to understand why it is wrong. If it were the right answer, nobody would ever put a ticket into any basket except the one with the least valuable prize, which would make it the hardest to win. Exactly how to place your tickets is a complicated problem in Game Theory, and the solution to it won John Nash (the subject of the movie A Beautiful Mind) a Nobel Prize. Suffice it to say that you need to balance the value of the prize against the tendency to come to Marilyn's conclusion. That balance is called a Nash Equilibrium.
(3) If you don't have any idea how many tickets are in the baskets, you have to treat each equally. That doesn't mean that you must assume that each has the same number, but that the probability P that Basket #1 has M tickets while Basket #2 has N, is the same as the probability that Basket #1 has N tickets while Basket #2 has M. It turns out that with only that assumption, and regardless of what P, M, and N are, that you get the best chance of winning at least one of those two prizes if you put the same number in each basket. The proof is along the same lines as the proof used in Answer #1 above (or you can just use that answer, and estimate each basket equally), but more complicated. From that it can be shown that you need to put the same number of tickets in each basket to maximize the overall probability. (Or be within 1, if you can't divide them equally). Because if any two baskets have an unequal number of your tickets, you can increase your probability by equalizing them.