Have you ever been to an event where there is a multiple raffle? The premise is simple: There are a plurality of prizes and you enter a raffle by placing your ticket into that drawing (typically a gold-fish bowl) of your choice. At the end of the evening, each drawing is performed independently. The winning ticket from each drawing gets that prize.
If there is only one prize you care about, clearly, your best strategy is to place your ticket into that drawing.
If you are agnostic as to the prize you win, your strategy should be to place your ticket into the bowl that has the lowest number of entries (Maybe waiting until just before drawing begins, and slipping your ticket into the least popular bowl?!)
But, what if you have multiple tickets? How would your strategy change? What if the bowls are occluded and you can’t see how many entries were in each drawing (or there were sufficiently many that you could not estimate?)
Is it better to put all your eggs (tickets) into one basket (drawing), or distribute them over all the drawings?
Again, let’s make the assumption that you are agnostic as to the prize you win (because, if you only cared about one, and only one, of the prizes you would still put all your tickets into that drawing).
The question comes down to the tradeoff: Does having more ‘skin in the game’ (multiple chances in one drawing), outweigh having multiple attempts at winning prize. Let’s take a look.
As we have no other information to go on, let’s assume that the existing entries have been uniformly distributed through the drawings. So, before you determine what to do, the N tickets have been spread through the d bowls so that each bowl holds N/d tickets.
If you place all t of your tickets into one drawing, the probability of you winning is:
This is a simple calcuation. Before you added your tickets, there were N/d tickets in the bowl. You've just added t more, so now the total number of tickets in the bowl is t+(N/d). Out of these, t tickets will cause you to win the prize.
Let's put some real numbers in there. Let's imagine there are 1,000 other tickets out there (N=1,000), and that there are five raffles (d=5), and that you have five tickets (t=5).
If you place all your tickets in the same bowl, your chance of winning is 5/(5+(1000/5)) = 5/205 ≈ 2.439%
If you had ten tickets, your odds increase to 10/(10+(1000/5)) = 10/210 ≈ 4.762%, not quite double.
Now let's see what happens if we distribute our tickets through all the drawings.
To calculate the probability of at least one win, we need to find the probability of losing every single drawing and subtract this from 1 (certainty). We need to do this because, with a ‘spread the love’ strategy it’s possible to win more than one of the prizes.
If you have t tickets then distributing these evenly you will be putting t/d additional tickets in each bin which, before you placed in your tickets, held N/d tickets.
You lose a drawing if your ticket is not selected, and this happens N/d times out of (N/d + t/d) times. There are the total of d drawings, so we multiply these probabilities together (logical AND), and this is the dth power:
Let's run the same values from the example above: N=1,000; d=5; t=5
If we place one ticket in each of the five bowls, the odds of winning at least one prize is:
1-(1000/(5+1000))5 = 1-(1000/1005)5 ≈ 2.463%
This is a slightly higher chance than putting all the tickets in one drawing at 2.439% (plus there is also the chance of winning more than one prize!)
In the ten ticket example, if you place two tickets in each of the drawings: N=1,000; d=5; t=10
1-(1000/(10+1000))5 = 1-(1000/1010)5 ≈ 4.853% (cf. 4.762%)
The math is clear – Spread out your tickets*
With a 'spread the love' strategy, not only are your chances of winning anything better, you also stand a chance of winning more than one prize.
*Assuming that the other tickets are fairly evenly distributed.Image: Alyson Hurt
Here is the data in graph format. Below are two curves showing the percentage chance of winning based on the two strategies. For both, the number of other tickets is kept constant at 1,000 and the number of parallel raffles is also kept at five. You can see that the orange line (spreading the love) is always higher than the blue line (putting all tickets in one drawing). Also, remember that by spreading your tickets out there is a chance that you may win more than one prize!
There is a related, and more complex, problem in probability theory and this is given the name of the Multi-armed bandit problem. I’m hoping this will be a topic of a future blog post.
In the multi-armed bandit problem, you are standing in front of a row of slot machines. Each of these machines has a different payout probability. You are given a finite number of coins to bet, and your goal is to maximize the return from your investment.
|Image: Connie Ma||
Herein lies the problem: Clearly you want to consistently play the machine with the best payout odds, but how do you know which that machine is?
You might get lucky, and on your first attempt, get a machine with pretty good payout odds, but how can you be sure it’s the best machine? Maybe every other machine pays out more than the machine you are currently playing? The way to find out is to try some of the others, but if you do that too much you’re wasting money playing poor machines. Also, since this is random, maybe you were just lucky on your first machine and it’s really the worst paying machine, and your early wins convinced you to keep playing? Maybe when you tested one of the other machines to see how lose/tight it was, you were just unlucky and the best paying machine did not pay you when you sampled it.
Clearly some strategy similar to the Sultan’s Wife problem is in order (also sometimes called the dating problem, or the secretary puzzle …) in which you spend some time sampling each of the offerings to build in idea of the range of the machines, and then focus your efforts on the higher paying machines. If the sampling period is too short then you don’t get a good estimate of the expected output of the machines, but if you make the sampling period too long, then you don’t have adequate time to capitalize on what you’ve learned as you’ve wasted too many bets finding the better machines.
Where the multi-armed bandit differs from the secretary style puzzles is that it is dynamic; as you go along the odds are continuing to change. With every bet you are learning more about the system. You might start off thinking that one machine is the better machine, but after a while, your results might cause you to churn from this as you play it and your average winnings start to fall.
The multi-armed bandit has great applications in rapid product development where multivariate tests need to be run (such as web pages, feature sets, or pricing models). With a live service you want to maximize some parameter (revenue, engagement, trust …) at the same time as operating it. Many great papers have been written about this problem.