Player A has £1, Player B £99. They flip a coin. The loser pays the other £1. What is the expected number of games they play before one is bankrupt?
I have struggled at this for hours now with little other than a lot of scribbles to show for it. Please could someone help me out.
On
I answer by simulation only
Little python skript:
d = {} # d[x] probability of player one to own x pound
for x in range(101):
d[x] = 0.0
flips = 100000 #100000 flips seem to be enough
d[1] = 1.0
exp = 0 # Expected flips until ruin, as soon as d[0]+d[100] converges to 1
for count in range(1,flips+1):
d_old = d
d = {}
for x in range(2, 99):
d[x] = (d_old[x-1] + d_old[x+1])/2
d[1] = d_old[2]/2
d[0] = d_old[1]/2 + d_old[0]
d[99] = d_old[98]/2
d[100] = d_old[99]/2 +d_old[100]
exp += (d_old[1]+d_old[99])*count/2
print d[0]+d[100] # probability game ended with ruin after "flips" flips
print d
print count # should be the number of flips now
print exp
results in
1.0 {0: 0.9899999999999723, 1: 1.449161956482358e-26, 2: 0.0, 3: 4.3417666892639597e-26, 4: 0.0, 5: 7.217236452487559e-26, 6: 0.0, 7: 1.0064223080674886e-25, 8: 0.0, 9: 1.2871490818268956e-25, 10: 0.0, 11: 1.5627960662028116e-25, 12: 0.0, 13: 1.8322754084790334e-25, 14: 0.0, 15: 2.094523596804998e-25, 16: 0.0, 17: 2.3485056573911828e-25, 18: 0.0, 19: 2.593219239077821e-25, 20: 0.0, 21: 2.8276985691569964e-25, 22: 0.0, 23: 3.051018264836302e-25, 24: 0.0, 25: 3.262296985301957e-25, 26: 0.0, 27: 3.460700909968348e-25, 28: 0.0, 29: 3.6454470291869485e-25, 30: 0.0, 31: 3.815806234427676e-25, 32: 0.0, 33: 3.971106195737163e-25, 34: 0.0, 35: 4.1107340151179235e-25, 36: 0.0, 37: 4.234138645356746e-25, 38: 0.0, 39: 4.3408330647562905e-25, 40: 0.0, 41: 4.4303961991872295e-25, 42: 0.0, 43: 4.502474583875468e-25, 44: 0.0, 45: 4.556783758366126e-25, 46: 0.0, 47: 4.593109389158988e-25, 48: 0.0, 49: 4.611308115584916e-25, 50: 0.0, 51: 4.611308115584916e-25, 52: 0.0, 53: 4.593109389158988e-25, 54: 0.0, 55: 4.556783758366126e-25, 56: 0.0, 57: 4.502474583875468e-25, 58: 0.0, 59: 4.4303961991872295e-25, 60: 0.0, 61: 4.3408330647562905e-25, 62: 0.0, 63: 4.234138645356746e-25, 64: 0.0, 65: 4.1107340151179235e-25, 66: 0.0, 67: 3.971106195737163e-25, 68: 0.0, 69: 3.815806234427676e-25, 70: 0.0, 71: 3.6454470291869485e-25, 72: 0.0, 73: 3.460700909968348e-25, 74: 0.0, 75: 3.262296985301957e-25, 76: 0.0, 77: 3.051018264836302e-25, 78: 0.0, 79: 2.8276985691569964e-25, 80: 0.0, 81: 2.593219239077821e-25, 82: 0.0, 83: 2.3485056573911828e-25, 84: 0.0, 85: 2.094523596804998e-25, 86: 0.0, 87: 1.8322754084790334e-25, 88: 0.0, 89: 1.5627960662028116e-25, 90: 0.0, 91: 1.2871490818268956e-25, 92: 0.0, 93: 1.0064223080674886e-25, 94: 0.0, 95: 7.217236452487559e-26, 96: 0.0, 97: 4.3417666892639597e-26, 98: 0.0, 99: 1.449161956482358e-26, 100: 0.009999999999999303} 100000 99.0
Whoever answers with 99 and a correct mathematical explanation should get the pot, this answer is just for validation.
Let $E_n$ be the expected number of flips before either player goes bankrupt if player A has $n$ pounds.
For $n = 0$ and $n = 100$, we have $E_{0} = E_{100} = 0$ since one of the players is already bankrupt.
If $0 < n < 100$, then there is a $\frac{1}{2}$ chance of the coin flip resulting in player A having $n-1$ pounds and a $\frac{1}{2}$ chance of the coin flip resulting in player A having $n+1$ pounds. This gives us the recurrence relation $E_n = \frac{1}{2}E_{n-1}+\frac{1}{2}E_{n+1}+1$, i.e. $E_{n+1}-2E_{n}+E_{n-1} = -2$.
Now, we have a linear recurrence relation and two boundary conditions. You can use the methods described on Wikipedia to solve this. Then, your answer is simply $E_1$, which ends up being a lot bigger than I expected.