An application to Random Walk - Gambler's Ruin in Coin Tossing

Let's consider a situation when two gamblers bet on whether a coin tossed is head or tail. Assume gambler A has x dollars and gambler B has y dollars. And gambler A always bets on head whereas gambler B always bets on tail. For each round, they bet one dollar. Then, if the probability of tossing a head is p and that of tail is q (= 1-p) and they gamble until one of them is ruined (running out of money), what is the probability that gambler A wins all the money at the end?

Solution

Let s₁, s₂, ....., s_n be a sequence of random variables such that

Let us put S₀=0, S_k = s₁ + s₂ + ..... + s_k, 1<=k<=n. In other words, the sequence, S₀, S₁, ....., S_n as the path of the random fluctuation between the two extremas where either gambler A or gambler B is ruined with starting point at zero. In this problem, S_k can be regarded as the amount won by gambler A from gambler B after k turns. It directly follows that for k<=n (this only means that k is finite) the first time S_k=y is the condition that B is ruined, whereas S_k=-x is the condition that A is ruined.

Let m be an integer between -x and y. It denotes the money gambler A is gained at a particular instant. 

Let the event "A wins within k turns given m dollar is gained at the beginning" = i_mk

Let I_mk = P(i_mk)

I_mk
= P(i_mk)
= P(i_mk and s₁=1) + P(i_mk and s₁=-1)
= P(i_mk | s₁=1)P(s₁=1)+ P(i_mk | s₁=-1)P(s₁=-1)
= pP(i_mk | s₁=1)+ qP(i_mk | s₁=-1)

It would be convenient to determine I_mk if P(i_mk | s₁=1) = P(i_m+1k-1)

To prove this crucial equality, we notice the fact that i_mk is in a one-one correspondence to the path

Hence,
P(i_mk | s₁=1)
= P((m, m+S₁, ....., m+S_k) | s₁=1)
= P((m+1, m+1+s₂, ....., m+1+s₂+...+s_k)) (note: we eliminate the cases where s₁ not equal 1)
= P((m+1, m+1+s₁, ....., m+1+s₁+...+s_k-1)) (note: index shifting)
= P(i_m+1k-1)

As a result for all -x<=m<=y and k<=n,

We observe that as i_mk-1 is a subset of i_mk, it follows that I_mk-1<=I_mk<=1 (and the fact that I is a probability measure). Therefore I is monotonic increasing and bounded above. Hence, its limit exists.

Let I_m be the limit.

We obtain the second order recursive equation,

The characteristic equation for this recursive equation is

The solutions for r is (1±(2p-1))/(2p), ie 1 or q/p

Note that the solution implies that if q does not equal to p, then it will be the case of real distinct root.

Hence, by solving the following system of equations using the boundary conditions,

Solving the system of equation, we have

c₁ = (q/p)^-x/((q/p)^y - (q/p)^-x) and c₂ = 1/((q/p)^y - (q/p)^-x)

By substitution and some algebra, we arrive at the solution for the case q does not equal p

For the case p = q = 1/2, we use partial derivative once. The partial derivative of r^m with respect to m is m×r^m-1. In this case r=1, therefore another independent solution is m(1)^m-1 = m. Hence, now the system of equations become:

Then, c₁ = x/(x + y) and c₂ = 1/(x + y)