Page 98 - A First Course In Stochastic Models

90 DISCRETE-TIME MARKOV CHAINS

roulette the wheel has 37 compartments numbered 0, 1, . . . , 36, where the odd
numbers are black and the even numbers except for the zero are red. An interesting
question that naturally arises is: what is the probability that during the next m spins
of the wheel there will be some sequence of r consecutive spins that all result either
in r black numbers or in r red numbers for a given value of r?
This question can be answered by Markov chain theory. The idea is to define a
Markov chain with r + 1 states including an absorbing state. The process is said to
be in state 0 when the last spin of the wheel resulted in a zero, while the process is
said to be in state i with 1 ≤ i < r when the same colour (red or black) appeared
in the last i spins but this colour did not appear in the spin preceding the last i
spins. The process is said to be in state r when the last r spins of the wheel have
resulted in the same colour. The state r is taken as an absorbing state; imagine that
the wheel sticks to the colour of the success run once a success run of length r
has occurred. A success run of length r is said to occur when state r is reached.
Denote by X n the state of the process after the nth spin of the wheel, with X 0 = 0
by convention. The stochastic process {X n } is a discrete-time Markov chain. Its
one-step transition probabilities are given by
1 36
p 00 = , p 01 = ,
37 37
18 1
p i,i+1 = p i1 = , p i0 = for i = 1, . . . , r − 1
37 37
p rr = 1.
The other p ij are zero. Since state r is absorbing, it is not possible that the process
has visited state r before time t when the process is in some state i = r at time t.
Hence

P {more than m spins are needed to get a success run of length r}

= P {X k = r for k = 1, . . . , m | X 0 = 0}
= P {X m = r | X 0 = 0} = 1 − P {X m = r | X 0 = 0}
(m)
= 1 − p .
0r
The desired probability that a success run of length r will occur during the first m
(m)
spins of the wheel is thus p . How can we calculate this probability for r = 26
0r
when N is of order 8 million (a rough estimate for the number of spins of the
roulette wheel in Monte Carlo between the date of the founding of the casino and
the date of 18 August 1913)? It is not advised to multiply the 27 × 27 matrix
P = (p ij ) 8 million times by itself. A more clever computation is based on
4
4
8
2
4
2
2
P = P × P, P = P × P , P = P × P , etc.
k
Taking k = 23, we have 2 is about 8 million. Hence it suffices to do 23 matrix
(m) 23
multiplications to get p for m = 2 . This gives the probability 0.061. Another
0,26