Two players A and B start a game with i and Ni chips respect

Two players, A and B, start a game with i and N-i chips, respectively. The game consists in repeatedly flipping a fair coin with A receiving 1 chip from B if heads turns up and B receiving 1 from A otherwise. The game ends as soon as one of the two players runs out of chips. If this game is played many times, what is the average duration (length) E(N,i) of a game? Compute an explicit formula for E(N,i) and provide a detailed derivation. The average length of the game will depend on the total number of chips and on the how many chips each player has, hence the indicated dependence on (N,i).

Solution

Answer:-

Use:

E(f) = E(f|h)P(h) + E(f|t)P(t)

E(f): Expected number of flips

E(f|h): Expected number of flips given that the first is a head
P(h): probability of a head
E(f|t): Expected number of flips given that the first is a tail
P(t): probability of a tail

If E(f) = e(i) a function of player As capital i then E(f|h) = 1 + e(i+1) since the 1 is for the first head and e(i+1) is the expected length when A starts with capital i+1 (because of the head).
Similarly we have E(f|t) = 1 + e(i-1). Giving a recurrence:

e(i) = P(h)(1 + e(i+1)) + P(t)(1 + e(i-1))

Or:

P(h)e(i+1) - e(i) + P(t)e(i-1) = -1

This recurrence can be solved for general P(h) but we have P(h)=P(t)=1/2 so:

e(i+1) - 2e(i) + e(i-1) = -2 (*)

which is of the form: \" recurrent terms in i = function of i \" and hence can be expressed as the sum of a particular solution p(i) and general solution g(i):

e(i) = p(i) + g(i)

the general solution comes from solving the characteristic equation for the left hand side of (*):

x^(i+1) - 2x^i + x^(i-1) = 0
x^2 - 2x + 1 = 0
x = 1 (multiplicity m=2)

so our general solution is:

g(i) = c0i^(m-1)(1)^i = c0i

The fact that the general root is 1 means the particular solution is of the form p(i) = a0i^m + a1i^(m+1) + .. + adi^(m+d) where d=0 is the degree of our \"function of i\" in (*). Hence our particular solution is:

p(i) = a0i^2

substitute this as e(i) into (*) to get:

a0(i+1)^2 - 2a0i^2 + a0(i-1)^2 = -2
a0(i^2 + 2i + 1 - 2i^2 + i^2 - 2i + 1) = -2
2a0 = -2
a0 = -1

thus:

e(i) = -i^2 + c0i

with the boundary conditions e(0)=e(N)=0, since in these cases the game is already over:

-N^2 + c0N = 0
c0 = N

e(i) = -i^2 + Ni
e(i) = i(N-i) <----

where my e(i) is your E(i,N).