The Mathematical Garden

An Analysis of the Problem

Let q_i(i = 0, 1, ... , N) be the probability that the gambler has a fortune of i and he will eventually win the money he needs.

We first note that

q₀ = 0 and q_N = 1

and

q_i = (1 - p) q_i-1 + (p) q_i+1     for i = 1, 2, ..., N -1.

We observe that

(1 - p)(q_i - q_i-1) = p(q_i+1 - q_i)     for i = 1, 2, ..., N -1.

Let

w_i = q_i - q_i-1

then we have

wi+1 =

1 - p ¾¾ p

wi     for i = 1, 2, ..., N -1.

Inductively

wi+1 = (

1 - p ¾¾ p

)i w1 = (

1 - p ¾¾ p

)i (q1 - q0) = (

1 - p ¾¾ p

)i q1

Therefore

qi+1 = qi + (

1 - p ¾¾ p

)i q1     for i = 1, 2, ..., N -1.

Hence

q2 = (1 +

1 - p ¾¾ p

) q1

q3 = q2 + (

1 - p ¾¾ p

)2 q1 = (1 +

1 - p ¾¾ p

+ (

1 - p ¾¾ p

) 2 ) q1

Inductively we have

qi	=	(1 + 1 - p ¾¾ p + ( 1 - p ¾¾ p ) 2 + ... + ( 1 - p ¾¾ p ) i-1 ) q1
	=	ì í î p ¾¾ 2p - 1 ( 1 - ( 1 - p ¾¾ p ) i ) q1   if p¹ 0.5 Nq1   if p = 0.5.

To solve for q₁ we use the fact that

1 = qN =	ì í î	p ¾¾ 2p - 1 ( 1 - ( 1 - p ¾¾ p ) i ) q1   if p¹ 0.5
		Nq1   if p = 0.5.

Hence

q1 =	ì í î	2p - 1 ¾¾¾¾ p (1 - XN)     where X = ( 1 - p ¾¾ p )   if p¹ 0.5
		1 / N   if p = 0.5.

Finally

qi =	ì í î	(1 - Xi) ¾¾¾¾ (1 - XN)     where X = ( 1 - p ¾¾ p )    for i = 0, 1, ..., N   if p¹ 0.5
		i / N    for i = 0, 1, ..., N   if p = 0.5.