A Long Game

Simulation and Analysis of a Random Walk

by Jeff Brown and Thad Dankel

Origin of the Problem

When my daughter Rebecca was six years old, she received a calendar from the Kids Club associated with a fast food chain.  Each month in the calendar had an activity, and September's activity was the following game.

Each player puts a marker on the first day of the month and the  players take turns flipping a coin.  If your coin lands on heads, then you move your marker ahead one day.  If your coin lands on tails, then you move your marker back one day, unless you are on the first day of the month, in which case you stay there. The first player to get beyond the last day of the month (ie get to square 31) is the winner.

When Rebecca read me the rules and asked if I wanted to play, my first thought was that this game might take all night!  We decided to play a different game.

I later simulated this game and arrived at estimates of the expected length of the game for different calendar lengths.  In the case where there is only one player, the expected number of moves needed to reach square 31 is 930.

Thad Dankel and I proved that these estimates are correct, and Thad has completed the analysis of the general case where there are k players.
 

Try the game!

The button below will start a java applet in which you can try the game yourself.  This version has 20 squares, and your position is indicated by the red square.  Clicking the "Flip Coin" button simulates a coin toss and moves your red marker.  Clicking the "Finish the Game" button completes the game and updates the number of moves required.  

Expected Duration of N Person Game through Simulation

What we want to know is, how long can we expect this game to last? First of all, notice that if we have more than one player, then we expect the game to require fewer turns, where a turn consists of each player flipping a coin. This is because the length of the game is determined by the luckiest player.

If we play the game many times, record the number of turns required each time, and take the average, then we have approximated the Expected Duration of the game. That is just what the applet below does. Enter the number of players, the number of squares in the game, the number of trials (number of times to go through the game), and then the "Run Simulation" button will play the game the required number of times and compute the average number of turns required to finish.