A while back I posted a puzzle based on a suggestion by Fabian in which Smartodds employees are – hypothetically – given the opportunity to increase their bonus by a factor of 10. See the original post for the rules of the game.
As I wrote at the time, the solution is not at all obvious – I don’t think I could have found it myself – but it includes some important ideas from Statistics. It goes as follows…
Each individual employee has a probability equal to 1/2 of finding their number. This is because they can open 50 of the 100 boxes, leaving another 50 unopened. It’s then obvious by symmetry that they must have a 50-50 chance of finding their number, since all numbers are randomly distributed among the boxes.
But recall, the players’ bonus is multiplied by 10 only if all players find their own number.
To begin with, let’s assume that the employees play the game without any strategy at all. In that case they are playing the game independently, and the standard rules of probability mean that we must multiply the individual probabilities to get the overall win probability. So, the probability that the first 2 players both win is 1/2 * 1/2. The probability that the first 3 players all win is 1/2 * 1/2 * 1/2. And the probability that all 100 players win is 1/2 multiplied by itself 100 times, which is roughly
0.000000000000000000000000000000789.
In other words, practically zero. So, the chances of the bonuses being multiplied by 10 is vanishingly small; it’s therefore almost certain that everyone will lose their bonus if they choose to play the game. As Ian wrote to me, it would be ‘one of the worst bets of all time’. No arguments there.
But the amazing thing is that with a planned strategy the probability that all players find their number, and therefore win the bet, can be increased to around 31%. The strategy which yields this probability goes like this…
Recall that the boxes themselves are numbered. Each player starts by opening the box corresponding to their own number. So, Player 1 opens box 1. If it contains their number they’ve won and they stop. Otherwise, whichever number they find in that box is chosen as the number of the box they will next look in. And they carry on this way, till either they find their number and stop; or they open 50 boxes without having fond their number. In the first case, that individual player has won, and it is the next player’s turn to enter the room (and play according to the same strategy); in the second case, they – and by the rules of the game the whole set of players – has lost.
So, Player 1 first opens box 1. If that box contains, say, the number 22, they next open box 22. If that contains the number 87, they next open box number 87. And so on, until they find their number or they reach the limit of 50 boxes. Similarly, Player 2 starts with box 2, which might contain the number 90; they next open box number 90; if that contains number 49 they then open box number 49, etc etc. Remarkably with this strategy the players will all find their own numbers – within the limit of 50 boxes each – with a probability of around 31%.
I find this amazing for 2 reasons:
- That fairly basic probability techniques can be used to show the strategy leads to calculate the win probability of around 31%;
- That the strategy results in such a massive increase in the win probability from virtually 0 to almost 1/3.
Unfortunately, though the calculations are all elementary, the argument is a touch too elaborate for me to reasonably include here. The Wikipedia entry for the puzzle – albeit with the cosmetic change of Smartodds employees being replaced by prisoners- does give the solution though, and it’s extremely elegant. If you feel like stretching your maths and probability skills just a little, it’s well worth a read.
In any case it’s instructive to look at a simpler case included in the Wikipedia article. Things are simplified there to just 8 employee/prisoners who have to find their number by opening at most 4 boxes (i.e. 50% of 8 boxes as opposed to 50% of 100 boxes in the original problem).
In this case suppose the numbers have been randomised into the boxes according to the following table…
| Box number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Card number | 7 | 4 | 6 | 8 | 1 | 3 | 5 | 2 |
Now suppose the players play according to the strategy described above except that they keep playing until they find their number, without stopping at the 4th box, even though they will have lost if they open more than 4 boxes. With the numbers randomised as above you can easily check that the sequence of boxes each player opens is as follows:
Player 1: (1, 7, 5)
player 2: (2, 4, 8)
Player 3: (3, 6)
Player 4: (4, 8, 2)
Player 5: (5, 1, 7)
Player 6: (6, 3)
Player 7: (7, 5, 1)
Player 8: (8, 2, 4)
With these numbers, since each player opens at most 3 boxes, everyone wins and the employers/prisoners get their increased bonus.
However, had the cards been randomised slightly differently among the boxes, as per the following table…
| Box number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Card number | 7 | 4 | 6 | 8 | 2 | 3 | 5 | 1 |
… then Player 1 (for example) would have followed the sequence (1, 7, 5, 2, 4, 8) and would therefore have lost, having opened more than 4 boxes.
Now observe:
- Several players follow the same sequence, albeit in a different order. For example, with the first randomisation, Players 1, 5 and 7 are each following the sequence (1, 7, 5) in some order;
- The complete set of different sequences – ignoring changes of order – are in the first case (1, 7, 5), (2, 4, 8) and (3, 6). They are bound not to overlap and are also bound to contain the complete set of numbers 1-8 between them.
- The fact that none of the sequences is longer than 4 with this randomisation means that the game has been won by all players. With the second randomisation, the fact that at least one of the sequences – (1, 7, 5, 2, 4, 8) – is longer than 4 means that the game has been lost.
- It follows that the probability the game is won is equal to the probability that the longest sequence has length at most 4.
- This argument applies more generally, so that with 100 players the game is won if the longest sequence of boxes opened has length at most 50.
Remarkably, it turns out to be not too difficult to calculate this probability that the longest sequence has length at most 50% of the number of players. And with 100 players it turns out be approximately 31%. And as if that’s not remarkable enough, the same proof shows that with an unlimited number of players the above strategy leads to a win probability of around 30.7%. In other words, in replacing 100 players with 1 million players, the win probability only drops from around 31% to 30.7%.
All quite incredible. But even without studying the detailed proof you can maybe get an idea from the 8-player example of why the strategy works. By playing this way, even though each individual player wins with probability 1/2, they no longer win or lose independently of one another. If Player 1 wins, every other player in their sequence of searches – Players 5 and 7 in the first example above – also wins. So, the suggested strategy induces dependence in the win/lose events of the individual players, and this leads to a change in win probability from something close to 0 to something close to 1/3.
Something similar actually came up earlier in the blog in the context of accumulator bets. I mentioned that betting on Mark Kermode’s Oscar predictions might be a good accumulator bet since the success of his predictions might not be independent events, and this had the potential to generate value against bookmakers who assume independence when setting prices for accumulators.
Finally, to answer the question: should the employees accept the challenge? If their original bonus is, say, ￡1000, then that becomes ￡10000 if they win, but ￡0 if they lose. So, with probability 31% they gain ￡9000, but with probability 69% they lose ￡1000. It follows that their expected gain if they play is
31\% \times \pounds 9000 - 69\% \times \pounds 1000 = \pounds 2100,
which is a comfortably positive expected profit for an outlay of ￡1000. So, they should definitely play, as long as they follow the strategy described above.
Two quick footnotes:
- It’s more difficult to prove, but it turns out that the strategy described above is optimal – there’s no other strategy that would lead to a bigger win probability than 31%;
- All of the above assumes that everyone follows the described strategy correctly. It would just take a couple of player to not follow the rules for all of the value of the bet to be lost. So, if the employees thought there might be a couple of, let’s say, ‘slow-learners’ in the company, it might be safer for them not to play and just take the ￡1000 and run.
