Best of N
August 2009 (index)
We repeatedly toss a coin. If it's heads then you score a point. If it's tails then I score a point. The game continues for up to N tosses, but you can decide to stop the game early at any point when the scores aren't tied. The winner is the player who has the most points when the game ends. What's your chance of winning?
The strategy is pretty simple. You should stop the game if and only if you're ahead at that point. Stopping when you're behind loses you the game; and continuing when you're ahead can't improve your chances of winning.
There are a couple of different ways of working out your chance of winning. By calculating the probability mathematically, or by simulating it.
Calculation
Write D(x,n) for the probability that after n tosses you're still playing and behind by x. And write W(n) for the probability that you took the lead on the nth turn (and won by stopping at that point).
We know we start level so D(0,0)=1 and we can calculate for each n W(n)=D(0,n-1)*0.5 since the chance of winning is the the chance of being level before then getting a head.
Also for x>=0 D(x,n)=D(x-1,n-1)*0.5 + D(x+1,n-1)*0.5 since the chance of a deficit x comes from either being one worse before and getting a head, or being one better before and getting a tail.
Then to get the overall chance of winning we add up W(n) for n up to the number of games.
Simulation
As a check on the maths we can also do a "Monte Carlo" simulation. This means we use a random number generator to mimic the coin tosses. We just play a lot of (virtual) games according to the rules of the game and keep count of who wins.
Results
If N=1 and we can only play one game then you have a 50% chance of winning. With N=3 your chances increase: you win if the first game is a head (and you stop immediately) or if the sequence is Tail,Head,Head. Of the eight possibilities for the game (HHH, HHT, HTH, HTT, THH, THT, TTH, TTT) you win five.
Game-length Simulated Calculated
1 50.0% 50.0%
3 62.9% 62.5%
5 68.9% 68.8%
7 72.7% 72.7%
9 74.7% 75.4%
19 82.7% 82.4%
29 85.7% 85.6%
39 87.6% 87.5%
49 88.7% 88.8%
99 92.0% 92.0%
999 97.4% 97.5%
As the game-length N gets longer and longer your chance of winning gets closer and closer to 100%. Being able to choose how long the game is while it's in progress is a big advantage.
Other odds
We can also look at what happens if the random event (the coin toss) isn't 50:50. Suppose that instead of a coin toss you draw one card from a shuffled full deck of cards (replacing the card after each draw) and you score a point if you draw a ten, Jack, Queen, King, or Ace. So you have a 5/13(=38.5%) chance of winning a point each turn and an 8/13(=61.5%) chance of losing.
With these odds for each turn your overall chances are:
Game-length Simulated Calculated
1 37.5% 38.5%
3 47.7% 47.6%
5 52.5% 51.9%
7 54.5% 54.4%
9 56.0% 56.1%
19 59.9% 59.9%
29 60.8% 61.2%
39 61.5% 61.7%
49 61.4% 62.0%
99 62.3% 62.4%
999 62.0% 62.5%
Although the odds are against you over one turn, being able to choose between best-of-1, best-of-3 and best-of-5 while the game is progress is enough to give you a better than 50% chance of winning overall.
As the game-length increases your overall chance of winning increases. But unlike the coin-toss where it increases without limit, this time it never gets above 5/8 (62.5%).
Writing p for the probability of winning a single round, with p>=0.5, your chance of winning overall gets as close as you like to certainty, if you play long enough.
But with p<0.5, no matter how long the game is, youe chance of winning has a limit of p/(1-p). So with p=1/3 you have a 50% chance of winning an infinitely long game. With p<1/3 the game is never long enough to make it to your advantage.
ibbly.com contact