Average coinflips to reach the 6 (Custom game)

Question

a friend of mine asked me about a certain game mechanic in a videogame and how many tries it would take for him (on average) to reach his goal. In abstract form, it can be explained as follows:

• You start with the number 4
• The lowest you can go is 0
• Once you reach 6, you win
• You flip coins (50/50 distribution) one after another. If you get heads, you add 1 to your number, if it's tails, you subtract 1

-> How many tries will it take to reach 6?

My main problem is, that you have an unlimited number of tries and that there is actually an upper and lower bound on your "score".

Can someone help me out?

Answer 1

Hint: Starting at position $4$, you have, in one flip, a fifty-fifty chance of going to position $3$ or position $5$. So $E_4=1+\frac12 E_3+\frac12 E_5$ (where $E_k$ is the expected number of flips to get from position $k$ to the end of the game (position $6$)). You can develop a bunch of equations like this and solve the resulting system using the fact that $E_6=0$. Note: You have to be a bit careful with the equation for $E_0$ since you have a fifty-fifty chance of staying at $0$ or moving to $1$.

Answer 2

This is a problem very suited to be solved with a Monte Carlo simulation. Below is a simple code I used (Python), with $100,000$ simulations:

import random
import pandas as pd
import seaborn as sns
def game():
    '''
    Defines the game.
    '''
    number = 4 # Starts at 4
    count = 0 # Counts the number of plays
    while not number == 6: # If the player is not at place 6 yet...
        number += 2*random.randint(0,1)-1 # Adds 1 or -1 with probability 1/2
        number = max(number, 0) # Guarantees we are not below 0
        count +=1 # Updates the counter
    return count # Returns the counter when the player arrives at 6
simulations = pd.Series([game() for i in range(100000)])
print(simulations.describe())

with output

count    100000.000000
mean         22.020540
std          30.137399
min           2.000000
25%           2.000000
50%           8.000000
75%          30.000000
max         383.000000
dtype: float64

Here's a histogram of the distribution:

Thus, the average number of tries is around 22. But notice that the median is around 8. Since the number of tries is unbounded by above, these outliers are bringing the mean up.

Answer 3

Let's take the method as described by @paw88789 and see if it matches the approximation as given by @econbernardo:

OK, so we get:

$E(0) = 1+ E(1)/2 + E(0)/2$

So: $E(0)/2=1+E(1)/2$

$E(1) = 1 + E(2)/2+E(0)/2 = 1 + E(2)/2+1+E(1)/2=2+E(2)/2+E(1)/2$

So: $E(1)/2=2 +E(2)/2$

Likewise (I'll save you the details), we get:

$E(2)/2=3 +E(3)/2$

$E(3)/2=4 +E(4)/2$

$E(4)/2=5 +E(5)/2$

$E(5)/2=6 +E(6)/2$

And since E(6)=0$, we thus get:

$E(5)/2=6 +0 = 6$, meaning that $E(5) = 12$

$E(4)/2=5 + 6= 11$, meaning that $E(4) = 22$

So yes, we got a match with @econbernardo empirical result!

and just to be complete:

$E(3)/2=4 +E(4)/2=4 + 11= 15$, meaning that $E(3) = 30$

$E(2)/2=3 +E(3)/2=3 + 15= 18$, meaning that $E(2) = 36$

$E(1)/2=2 +E(2)/2=2 + 18= 20$, meaning that $E(1) = 40$

$E(0)/2=1+E(1)/2= 1+20=21$, meaning that $E(0) = 42$