One Hundred
1
Solved
2
Exercises
3
for the subject:
Stochastic Processes I
4
Takis Konstantopoulos
5
1.
In the Dark Ages, Harvard, Dartmouth, and Yale admitted only male students. As-
sume that, at that time, 80 percent of the sons of Harvard men went to Harvard and
the rest went to Yale, 40 percent of the sons of Yale men went to Yale, and the rest
split evenly between Harvard and Dartmouth; and of the sons of Dartmouth men, 70
percent went to Dartmouth, 20 percent to Harvard, and 10 percent to Yale. (i) Find
the probability that the grandson of a man from Harvard went to Harvard. (ii) Modify
the above by assuming that the son of a Harvard man always went to Harvard. Again,
find the probability that the grandson of a man from Harvard went to Harvard.
Solution. We first form a Markov chain with state space S = {H, D, Y } and the
following transition probability matrix :
P =
.8 0 .2
.2 .7 .1
.3 .3 .4
.
Note that the columns and rows are ordered: first H, then D, then Y . Recall: the ij
th
entry of the matrix P
n
gives the probability that the Markov chain s tarting in state
i will be in state j after n steps. Thus, the probability that th e grandson of a m an
from Harvard went to Harvard is the upper-left element of the matrix
P
2
=
.7 .06 .24
.33 .52 .15
.42 .33 .25
.
It is equal to .7 = .8
2
+ .2 × .3 and , of course, one does not n eed to calculate all
elements of P
2
to answer this question.
If all sons of men from Harvard went to Harvard, this would give the following matrix
for th e new Markov chain with the same set of states:
P =
1 0 0
.2 .7 .1
.3 .3 .4
.
The upper-left element of P
2
is 1, which is not surprising, because the offspring of
Harvard men enter this very institution only.
2.
Consider an experiment of mating rabbits. We watch the evolution of a particular
1
More or less
2
Most of them
3
Some of these exercises are taken verbatim from Grinstead and Snell; some from other standard sources;
some are original; and some are mere repetitions of things explained in my lecture notes.
4
The subject covers the basic theory of Markov chains in discrete time and simple random walks on the
integers
5
Thanks to Andrei Bejan for writing solutions for many of them
1
gene that appears in two types, G or g. A rabbit has a pair of genes, either GG (dom-
inant), Gg (hybrid–the order is irrelevant, so gG is the same as Gg) or gg (recessive).
In mating two rabbits, the offspring inherits a gene from each of its parents with equal
probability. Thus, if we mate a dominant (GG) with a hybrid (Gg), the offspring is
dominant with probability 1/2 or hybrid with probability 1/2.
Start with a rabbit of given character (GG, Gg, or gg) and mate it with a hybr id. The
offspring produced is again mated with a hybrid, and the process is repeated through
a number of generations, always mating with a hybrid.
(i) Write down the transition probabilities of the Markov chain thus defined.
(ii) Assume that we start with a hybrid rabb it. Let µ
n
be the probability dis-
tribution of the character of the r abbit of the n-th generation. In other words,
µ
n
(GG), µ
n
(Gg), µ
n
(gg) are the probabilities that the n-th generation rabbit is GG,
Gg, or gg, respectively. Compute µ
1
, µ
2
, µ
3
. Can you do the same for µ
n
for general
n?
Solution. (i) The set of states is S = {GG, Gg, gg} with the following transition
probabilities:
GG Gg gg
GG .5 .5 0
Gg .25 .5 .25
gg 0 .5 .5
We can rewrite the transition matrix in the following form:
P = 2
−1
1 1 0
1
2
1
1
2
0 1 1
.
(ii) Th e elements from the second row of the matrix P
n
will give us the probabilities
for a hybrid to give dominant, hybrid or recessive species in (n − 1)
th
generation in
this experiment, respectively (reading this row from left to right). We first fi nd
P
2
= 2
−2
1.5 2 0
1 2 1
0.5 2 1.5
,
P
3
= 2
−3
2.5 4 1.5
2 4 2
1.5 4 2.5
,
P
4
= 2
−4
4.5 8 3.5
4 8 4
3.5 8 4.5
,
so that
µ
i
(GG) = .25, µ
i
(Gg) = .5, µ
i
(gg) = .25, i = 1, 2, 3.
Actually the p robabilities are the same f or any i ∈ N. If you obtained this result before
1858 when Gregor Mendel s tarted to breed garden peas in his monastery garden and
analysed the offspring of these matings, you would probably be very famous because it
definitely looks like a law! This is what Mendel found when he crossed mono-hybrids.
2
In a more general setting, this law is known as Hardy-Weinberg law.
As an exercise, show that
P
n
= 2
−n
3
2
+ (2
n−2
− 1) 2
n−1
1
2
+ (2
n−2
− 1)
2
n−2
2
n−1
2
n−2
1
2
+ (2
n−2
− 1) 2
n−1
3
2
+ (2
n−2
− 1)
.
Try!
3.
A certain calculating machine uses only the digits 0 and 1. It is supposed to transm it
one of these digits through several stages. However, at every stage, there is a prob-
ability p that the digit that enters this stage w ill be changed when it leaves and a
probability q = 1 −p that it won’t. Form a Markov chain to represent the process of
transmission by taking as states the digits 0 and 1. What is the matrix of transition
probabilities?
Now draw a tree and assign probabilities assuming that the process begins in state
0 and moves through two stages of transmission. What is the probability that the
machine, after two stages, produces the d igit 0 (i.e., the correct digit)?
Solution. Taking as states the digits 0 and 1 we identify the following Markov chain
(by specifying states and transition probabilities):
0 1
0 q p
1 p q
where p + q = 1. Thus, the trans ition matrix is as follows:
P =
q p
p q
=
1 −p p
p 1 − p
=
q 1 − q
1 − q q
.
It is clear that the probability that that the machine will produce 0 if it starts with 0
is p
2
+ q
2
.
4.
Assume that a man’s profession can be classified as professional, skilled labourer,
or unskilled labourer. Assume that, of the sons of professional men, 80 percent are
professional, 10 percent are skilled labourers, and 10 percent are unskilled labourers.
In the case of sons of skilled labourers, 60 percent are skilled labourers, 20 percent are
professional, and 20 percent are unskilled. Finally, in the case of unskilled labourers,
50 percent of the sons are unskilled labourers, and 25 percent each are in the other
two categories. Assume that every man has at least one son, and form a Markov chain
by following the profession of a randomly chosen son of a given family through several
generations. Set up the matrix of transition probabilities. Find the probability that a
randomly chosen grandson of an unskilled labourer is a professional m an.
Solution. The Markov chain in this exercise has the following set states
S = {Professional, Skilled, Unskilled}
3
with the following transition probabilities:
Professional Skilled Unskilled
Professional .8 .1 .1
Skilled .2 .6 .2
Unskilled .25 .25 .5
so that the transition matrix for this chain is
P =
.8 .1 .1
.2 .6 .2
.25 .25 .5
with
P
2
=
0.6850 0.1650 0.1500
0.3300 0.4300 0.2400
0.3750 0.3000 0.3250
,
and thus the probability that a randomly chosen grandson of an un s k illed labourer is
a professional man is 0.375.
5.
I have 4 umbrellas, some at home, some in the office. I keep moving between home
and office. I take an umbrella with me only if it rains. If it does not rain I leave the
umbrella behind (at home or in the office). It may happen that all umbrellas are in
one place, I am at the other, it starts raining and must leave, so I get wet.
1. If the probab ility of rain is p, what is the probability that I get wet?
2. Curr ent estimates show that p = 0.6 in Edinburgh. How many umbrellas should I
have so that, if I follow the strategy above, the probability I get wet is less than 0.1?
Solution. To solve the problem, consider a Markov chain taking values in the set
S = {i : i = 0, 1, 2, 3, 4}, where i represents the number of umbrellas in the place
where I am currently at (home or office). If i = 1 and it rains then I take the
umbrella, move to the other place, where there are already 3 umbrellas, and, including
the one I bring, I have next 4 umbrellas. Thus,
p
1,4
= p,
because p is th e probability of rain. If i = 1 but d oes n ot r ain then I do not take the
umbrella, I go to the other place and find 3 u mbrellas. Thus,
p
1,3
= 1 − p ≡ q.
Continuing in the same mann er, I form a Markov chain with the following diagram:
2
1
3
4
0
q
p
q
p
p
q
p
q
1
4
But this does not look very nice. So let’s redraw it:
30
4 2
1
1
p
q
p
p q
q
p
Let us find the stationary distribution. By equating fluxes, we have:
π(2) = π(3) = π(1) = π(4)
π(0) = π(4)q.
Also,
4
X
i=0
π(i) = 1.
Expressing all pr ob abilities in terms of π(4) and inserting in this last equation, we find
π(4)q + 4π(4) = 1,
or
π(4) =
1
q + 4
= π(1) = π(2) = π(3), π(0) =
q
q + 4
.
I get wet every time I happen to be in state 0 and it rains. Th e ch ance I am in state
0 is π(0). The chance it rains is p. Hence
P (W ET ) = π(0) · p =
qp
q + 4
.
With p = 0.6, i.e. q = 0.4, we have
P (W ET ) ≈ 0.0545,
less than 6%. That’s nice.
If I want the chance to be less th an 1% then, clearly, I need more umbrellas. So,
suppose I need N umbrellas. S et up the Markov chain as above. It is clear that
π(N) = π(N − 1) = ··· = π(1),
π(0) = π(N)q.
Inserting in
P
N
i=0
π(i) we find
π(N) =
1
q + N
= π(N − 1) = ··· = π(1), π(0) =
q
q + N
,
and so
P (W ET ) =
pq
q + N
.
We want P (W ET ) = 1/100, or q + N > 100pq, or
N > 100pq −q = 100 × 0.4 × 0.6 − 0.4 = 23.6.
So to reduce the chance of getting wet from 6% to less than 1% I need 24 umbrellas
instead of 4. Th at’s too much. I’d rather get wet.
5
6.
Suppose that ξ
0
, ξ
1
, ξ
2
, . . . are independent random variables with common probability
function f(k) = P (ξ
0
= k) where k belongs, say, to the integers. Let S = {1, . . . , N}.
Let X
0
be another random variable, independent of the sequence (ξ
n
), taking values in
S and let f : S ×Z → S be a certain function. Define new random variables X
1
, X
2
, . . .
by
X
n+1
= f(X
n
, ξ
n
), n = 0, 1, 2 . . .
(i) Show that the X
n
form a Markov chain.
(ii) Find its transition probabilities.
Solution. (i) Fix a time n ≥ 1. Suppose that you know that X
n
= x. The goal is
to sh ow that PAST=(X
0
, . . . , X
n−1
) is independent of FUTURE=(X
n+1
, X
n+2
, . . .).
The variables in the PAST are functions of
X
0
, ξ
1
, . . . , ξ
n−2
.
The variables in the FUTURE are functions of
x, ξ
n
, ξ
n+1
, . . .
But X
0
, ξ
1
, . . . , ξ
n−2
are independent of ξ
n
, ξ
n+1
, . . .. Therefore, the PAST and the
FUTURE are independent.
(ii)
P (X
n+1
= y|X
n
= x) = P (f (X
n
, ξ
n
) = y|X
n
= x)
= P (f(x, ξ
n
) = y|X
n
= x)
= P (f(x, ξ
n
) = y)
= P (f(x, ξ
0
) = y) = P (ξ
0
∈ A
x,y
),
where
A
x,y
:= {ξ : f(x, ξ) = y}.
7.
Discuss the topological properties of the graphs of the following Markov chains:
(a) P =
0.5 0.5
0.5 0.5
(b) P =
0.5 0.5
1 0
(c) P =
1/3 0 2/3
0 1 0
0 1/5 4/5
(d) P =
0 1
1 0
(e) P =
1/2 1/2 0
0 1/2 1/2
1/3 1/3 1/3
Solution. Draw the transition diagram for each case.
(a) Irreducible? YES because there is a path from every state to any other state.
Aperiodic? YES because the times n for which p
(n)
1,1
> 0 are 1, 2, 3, 4, 5, . . . and their
gcd is 1.
(b) Irreducible? YES because there is a path from every state to any other state.
Aperiodic? YES because the times n for which p
(n)
1,1
> 0 are 1, 2, 3, 4, 5, . . . and their
gcd is 1.
(c) Irreducible? NO because starting from state 2 it remains at 2 forever. However, it
6
can be checked that all states have period 1, simply because p
i,i
> 0 f or all i = 1, 2, 3.
(d) Irreducible? YES because there is a path from every state to any other state.
Aperiodic? NO because the times n for which p
(n)
1,1
> 0 are 2, 4, 6, . . . and their gcd is
2.
(e) Ir reducible? YES because there is a path from every state to any other state.
Aperiodic? YES because the times n for which p
(n)
1,1
> 0 are 1, 2, 3, 4, 5, . . . and their
gcd is 1.
8.
Consider the knight’s tour on a chess board: A knight selects one of the next positions
at random independ ently of the past.
(i) Why is this process a Markov chain?
(ii) What is the state space?
(iii) Is it irreducible? Is it aperiodic?
(iv) Find the stationary distribution. Give an interpretation of it: what does it mean,
physically?
(v) Which are the most likely states in steady-state? Which are the least likely ones?
Solution. (i) Part of the problem is to set it up correctly in mathematical terms.
When we say that the “knight selects one of the next positions at random indepen-
dently of the past” we mean that the next position X
n+1
is a function of the current
position X
n
and a random choice ξ
n
of a neighbou r. Hence the problem is in the same
form as the one above. Hence (X
n
) is a Markov chain.
(ii) The state space is the set of the squares of the chess board. There are 8 × 8 = 64
squares. We can label them by a pair of integers. Hence the state space is
S = {(i
1
, i
2
) : 1 ≤ i
1
≤ 8, 1 ≤ i
2
≤ 8} = {1, 2, 3, 4, 5, 6, 7, 8} ×{1, 2, 3, 4, 5, 6, 7, 8}.
(iii) The best way to see if it is irreducible is to take a knight and move it on a chess
board. You will, indeed, realise that you can fi nd a path that takes the knight from
any square to any other square. Hence every state communicates with every other
state, i.e. it is irreducible.
To see what the period is, fin d the perio d for a s pecific state, e.g. from (1, 1). You
can see that, if you start the knight from (1, 1) you can return it to (1, 1) only in
even number of steps. Hence the period is 2. So the answer is that the chain is not
aperiodic.
(iv) You have no chance in solving a set of 64 equations with 64 unknowns, unless you
make an educated guess. First, there is a lot of sym metry. So squares (states) that
are symmetric with respect to the centre of the chess board must have the pr ob ability
under the stationary d istrib ution. So, for example, states (1, 1), (8, 1), (1, 8), (8, 8)
have the same probability. And so on. Second, you sh ould realise that (1, 1) must be
less likely than a square closer to the centre, e.g. (4, 4). The reason is that (1, 1) has
fewer next states (exactly 2) th an (4, 4) (which has 8 next states). So let us make the
guess that if x = (i
1
, i
2
), then π(x) is proportional to the number N (x) of the possible
next states of the squ are x:
π(x) = CN(x).
But we must SHOW that this choice is correct. Let us say that y us a NEIGHBOUR
of x if y is a possible next s tate of x (if it is possible to move the kn ight from x to y
7
in on e step). So we must show that such a π satisfies the b alance equations:
π(x) =
X
y ∈S
π(y)p
y ,x
.
Equivalently, by cancelling C from both sides, we wonder whether
N(x) =
X
y ∈S
N(y)p
y ,x
holds true. But the sum on the right is zero unless x is a NEIGHBOUR of y:
N(x) =
X
y ∈S: x neighbour of y
N(y)p
y ,x
But the rule of m otion is to choose on of the neighbours with equal probability:
p
y ,x
=
(
1
N(y)
, if x is a neighbour of y
0, otherwise.
Which means that the previous equation becomes
N(x) =
X
y ∈S: x neighbour of y
N(y)
1
N(y)
=
X
y ∈S: x neighbour of y
1
=
X
y ∈S: y neighbour of x
1,
where in the last equ ality we used the obvious fact that x is a neighbour of y if and
only if y is a neighbour of x (sym metry of the relation) and so the last sum equals,
indeed, N (x). So our guess is correct!
Therefore, all we have to do is count the neighbours of each square x. Here we go:
2
2
2
2 3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
44
4
4
4
4
4
4
4
4
4
4
6
6
6
6
66
6
6
6
6
6
6
6
6
6
6
8
8
8
8
8
8
8
8 8 8
8
8
8
8
8
8
We have
2 × 4 + 3 × 8 + 4 × 20 + 6 × 16 + 8 × 16 = 336.
So C = 1/336, and
π(1, 1) = 2/336, π(1, 2) = 3/336, π(1, 3) = 4/336, . . . , π(4, 4) = 8/336, . . . ,
8
etc.
Meaning of π. If we start with
P (X
0
= x) = π(x), x ∈ S,
then, for all times n ≥ 1,
P (X
n
= x) = π(x), x ∈ S.
(v) The corner ones are the least likely: 2/336. The 16 middle ones are the most likely:
8/336.
9.
Consider a Markov chain with two states 1, 2. Suppose that p
1,2
= a, p
2,1
= b. For
which values of a and b do we obtain an absorbing Markov chain?
Solution. O ne of them (or both) should be zero. Because, if they are both positive,
the chain will keep moving between 1 and 2 forever.
10.
Smith is in jail and has 3 dollars; he can get out on bail if he has 8 dollars. A guard
agrees to make a series of bets with him. If Smith bets A dollars, he wins A dollars
with probability 0.4 and loses A dollars with probability 0.6. Find the p robability that
he wins 8 dollars before losing all of his money if (a) he bets 1 d ollar each time (timid
strategy). (b) he bets, each time, as much as possible but not more than necessary to
bring his fortune up to 8 dollars (bold strategy). (c) Which strategy gives Smith the
better chance of getting out of jail?
Solution. (a) The Markov chain (X
n
, n = 0, 1, . . .) representing the evolution of
Smith’s money has diagram
0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.6 0.6 0.6 0.6 0.6 0.6 0.6
0
1
2
3
4 5
6
7
8
1
1
Let ϕ(i) be the probability that the chain reaches state 8 before reaching state 0,
starting from state i. In other words, if S
j
is the first n ≥ 0 such that X
n
= j,
ϕ(i) = P
i
(S
8
< S
0
) = P (S
8
< S
0
|X
0
= i).
Using first-step analysis (viz. the Markov property at time n = 1), we have
ϕ(i) = 0.4ϕ(i + 1) + 0.6ϕ(i − 1), i = 1, 2, 3, 4, 5, 6, 7
ϕ(0) = 0
ϕ(8) = 1.
We solve this system of linear equations and find
ϕ = (ϕ(1), ϕ(2), ϕ(3), ϕ(4), ϕ(5), ϕ(6), ϕ(7))
= (0.0203, 0.0508, 0.0964, 0.1649, 0.2677, 0.4219, 0.6531, 1).
9
E.g., the pr obab ility that the chain reaches state 8 before reaching state 0, starting
from state 3 is the th ird component of this vector and is equal to 0.0964. Note that
ϕ(i) is increasing in i, which was expected.
(b) Now the chain is
0
1
2
3
4 5
6
7
8
1
1
0.4
0.4
0.4
0.6
0.6
0.6
and the equations are:
ϕ(3) = 0.4ϕ(6)
ϕ(6) = 0.4ϕ(8) + 0.6ϕ(4)
ϕ(4) = 0.4ϕ(8)
ϕ(0) = 0
ϕ(8) = 1.
We solve and find
ϕ(3) = 0.256, ϕ(4) = 0.4, ϕ(6) = 0.64.
(c) By comparing the third components of the vector ϕ we find that th e bold strategy
gives Smith a better chance to get out jail.
11.
A Markov chain with state space {1, 2, 3} has transition probability matrix
P =
1/3 1/3 1/3
0 1/2 1/2
0 0 1
Show that state 3 is absorbing and, starting from state 1, find the expected time until
absorption occurs.
Solution. Let ψ(i) be the expected time to reach state 3 starting from state i, where
i ∈ {1, 2, 3}. We have
ψ(3) = 0
ψ(2) = 1 +
1
2
ψ(2) +
1
2
ψ(3)
ψ(1) = 1 +
1
3
ψ(1) +
1
3
ψ(2) +
1
2
ψ(3).
We solve and find
ψ(3) = 0, ψ(2) = 2, ψ(1) = 5/2.
12.
A fair coin is tossed repeatedly and independently. Find th e expected number of tosses
till the pattern HTH appears.
10
Solution. Call HTH our target. Consider a chain that starts from a state called
nothing ∅ and is eventually absorbed at HTH. If we first toss H then we move to state
H because this is the first letter of our target. If we toss a T then we move back to ∅
having expended 1 unit of time. Being in state H we either move to a new state HT if
we bring T and we are 1 step closer to the target or, if we b ring H, we move back to
H: we have expended 1 unit of time, but the new H can be the beginning of a target.
When in state HT we either move to HTH and we are done or, if T occurs th en we
move to ∅. The trans ition diagram is
H HT HTH
1/2 1/2
1/2
1/2
1/2
1/2
1
Rename the states ∅, H, HT, HTH as 0, 1, 2, 3, respectively. Let ψ(i) be the expected
number of steps to reach HTH starting from i. We have
ψ(2) = 1 +
1
2
ψ(0)
ψ(1) = 1 +
1
2
ψ(1) +
1
2
ψ(2)
ψ(0) = 1 +
1
2
ψ(0) +
1
2
ψ(1).
We solve and find ψ(0) = 10.
13.
Consider a Markov chain with states S = {0, . . . , N} and transition probabilities
p
i,i+1
= p, p
i,i−1
= q, for 1 ≤ i ≤ N − 1, where p + q = 1, 0 < p < 1; assume p
0,1
= 1,
p
N,N−1
= 1.
1. Draw the graph (= transition diagram).
2. Is the Markov chain irreducible?
3. Is it aperiodic?
4. What is the period of the chain?
5. Find the stationary distribution.
Solution. 1. The transition diagram is:
p
p
p
q
q
q
N
N−12
1
0
i
i−1
p
q
q
p
2. Yes, it is possible to go from any state to any other state.
3. Yes, because p
0,0
> 0.
4. One.
5. We write balance equations by equating fluxes:
π(i)q = π(i − 1)p,
11
as long as 1 ≤ i ≤ N. Hence
π(i) =
p
q
π(i − 1) =
p
q
2
π(i − 2) = ··· =
p
q
i
π(0), 0 ≤ i ≤ N.
Since
π(0) + π(1) + . . . + π(N −1) + π(N ) = 1,
we find
π(0)
"
1 +
p
q
+
p
q
2
+ ··· +
p
q
N
#
= 1,
which gives
π(0) =
"
1 +
p
q
+
p
q
2
+ ··· +
p
q
N
#
−1
=
(p/q)
N
− 1
(p/q) −1
,
as long as p 6= q. Hence, if p 6= q,
π(i) =
(p/q)
N
− 1
(p/q) − 1
p
q
i
, 0 ≤ i ≤ N.
If p = q = 1/2, then
π(0) =
"
1 +
p
q
+
p
q
2
+ ··· +
p
q
N
#
−1
1
N + 1
,
and so
π(i) =
1
N + 1
, f or all i.
Thus, in this case, π(i) is the uniform distribution on the set of states.
14.
A. Assume that an experiment has m equally p robable outcomes. Show that the
expected number of independent trials before the first occurrence of k consecutive
occurrences of one of these outcomes is
m
k
− 1
m − 1
.
Hint: Form an absorbing Markov chain with states 1, 2, . . . , k with state i representing
the length of the current run. The expected time until a run of k is 1 more than the
expected time until absorption for the chain started in state 1.
B. It has been found that, in the decimal expansion of π = 3.14159 . . ., starting with
the 24,658,601st digit, there is a run of nine 7’s. What would your result say about
the expected number of digits necessary to find such a run if the digits are pr oduced
randomly?
Solution. A. Let the outcomes be a, b, c, . . . (m of th em in total). Suppose that a is
the desirable outcome. We set up a chain as follows. Its states are
∅, (a), (aa), (aaa), . . . , (aa ···a)
|
{z }
m times
12
Or, more simply, 0, 1, 2, . . . , m. State k means that you are currently at the end of
a run of k a’s. If you see an extra a (with probability 1/m) you go to state k + 1.
Otherwise, you go to ∅. Let ψ(k) be the expected number of steps till state m is
reached, starting from state k:
ψ(k) := E
k
S
m
.
We want to fi nd ψ(0). We have
ψ(k) = 1 + (1 − 1/m)ψ(0) + (1/m)ψ(k + 1).
Solving these, we find
ψ(0) = 1 + m + m
2
+ ··· + m
k−1
=
m
k
− 1
m − 1
.
B. So to get 10 consecutive sixes by rolling a die, you need more than 12 million rolls
on the average (12, 093, 235 rolls to be exact).
C. They are not random. If they were, we expect to have to pick (10
9
− 1)/9 digits
before we see nine consecutive sevens. That’s about 100 million digits. The actual
position (24 million digits) is one fourth of the expected one.
15.
A rat runs through the maze shown below . At each step it leaves the room it is in by
choosing at ran dom one of the doors out of the room.
1
2 3
4
5 6
(a) Give the transition matrix P for this Markov chain. (b) Show that it is irreducible
but not aperiodic. (c) Find the stationary distribution (d) Now suppose that a piece
of mature cheddar is placed on a deadly trap in Room 5. The mouse starts in Room 1.
Find the expected number of steps before reaching Room 5 for the first time, starting
in R oom 1. (e) Find the exp ected time to return to room 1.
Solution
(a) The transition matrix P f or this Markov chain is as follows:
P =
0 0 1 0 0 0
0 0 1 0 0 0
1/4 1/4 0 1/4 1/4 0
0 0 1/2 0 0 1/2
0 0 1/2 0 0 1/2
0 0 0 1/2 1/2 0
.
13
(b) The chain is irreducible, because it is possible to go f rom any state to any other
state. However, it is not aperiodic, because for any n even p
(n)
6,1
will be zero and for
any n odd p
(n)
6,5
will also be zero (why?). This means that there is no power of P that
would have all its entries strictly positive.
(c) The stationary distribution is
π = (
1
12
,
1
12
,
4
12
,
2
12
,
2
12
,
2
12
).
You should carry out the calculations and check that this is correct.
(d) We find from π that the mean recur rence time (i.e. the expected time to return)
for th e room 1 is 1/π(1)=12.
(e) Let
ψ(i) = E(number of steps to reach state 5 | X
0
= i).
We have
ψ(5) = 0
ψ(6) = 1 + (1/2)ψ(5) + (1/2)ψ(4)
ψ(4) = 1 + (1/2)ψ(6) + (1/2)ψ(3)
ψ(3) = 1 + (1/4)ψ(1) + (1/4)ψ(2) + (1/4)ψ(4) + (1/4)ψ(5)
ψ(1) = 1 + ψ(3)
ψ(2) = 1 + ψ(3).
We solve and find ψ(1) = 7.
16.
Show that if P is the transition matrix of an irreducible chain with finitely many states,
then Q := (1/2)(I + P) is the transition matrix of an irreducible and aperiodic chain.
(Note that I stands for the identity matrix, i.e. th e matrix which has 1 everywhere on
its diagonal and 0 everywhere else.)
Show that P and (1/2)(I + P) have the same stationary distributions.
Discuss, physically, how the two chains are related.
Solution. Let p
ij
be the entries of P. Then the entries q
ij
of Q are
q
ij
=
1
2
p
ij
, if i 6= j,
q
ii
=
1
2
(1 + p
ii
).
The graph of the new chain has more arrows th an the original one. Hence it is also
irreducible. But the new chain also has self-loops for each i because q
ii
> 0 for all i.
Hence it is ap eriodic.
Let π be a stationary distribution for P. Then
πP = π.
We must show that
πQ = π.
14
But
πQ =
1
2
(πI + πP) =
1
2
(π + π) = π.
The physical meaning of the new chain is that it represents a slowing down of the orig-
inal one. Indeed, all outgoing probabilities have been halved, while the probability of
staying at the same state has been increased. The chain performs the same transitions
as the original on e but stays longer at each state.
17.
Two players, A and B, play the game of matching pennies: at each time n, each player
has a penny and must secretly turn the penny to heads or tails. The players then
reveal their choices simultaneously. If the pen nies match (both heads or both tails),
Player A wins the penny. If the pennies do not match (one heads and one tails), Player
B wins the penny. Suppose the players have between them a total of 5 pennies. I f
at any time one player has all of the pen nies, to keep the game going, he gives one
back to the other player and the game will continue. (a) Show that this game can be
formulated as a Markov chain. (b) Is the chain regular (irredu cible + aperiodic?) (c)
If Player A starts with 3 pennies an d Player B with 2, what is the probability that A
will lose his pennies first?
Solution (a) The problem is easy: The pr obab ility that two pennies match is 1/2.
The probability they do not match is 1/2. Let x be the number of pennies that A has.
Then with probability 1/2 he will next have x + 1 pennies or with probability 1/2 he
will next have x −1 pennies. The exception is when x = 0, in wh ich case, he gets, for
free, a penny from B and he next has 1 penny. Also, if x = 5 he gives a penny to B
and he next has 4 pennies. Thus:
0
1
2
3
4 5
1/2
1/2
1/2 1/2
1/21/2
1/2
1
11/2
(b) The chain is clearly irreducible. But the period is 2. Hence it is not regular.
(c) To do this, modify the chain and make it stop once one of the players loses his
pennies. After all, we are NOT interested in the behaviour of the chain after this time.
The modification is an absorbing chain:
0
1
2
3
4 5
1/2
1/2
1/2 1/2
1/21/2
1/2
1/2
1
1
We then want to compute the absorbing probability ϕ
01
(3) where
ϕ
01
(i) = P
i
(hit 0 before 1).
15
Write ϕ(i) = ϕ
01
(i), for brevity, and apply first-step analysis:
ϕ(0) = 1
ϕ(1) =
1
2
ϕ(0) +
1
2
ϕ(1)
ϕ(2) =
1
2
ϕ(1) +
1
2
ϕ(2)
ϕ(3) =
1
2
ϕ(2) +
1
2
ϕ(3)
ϕ(4) =
1
2
ϕ(3) +
1
2
ϕ(4)
ϕ(5) = 0.
Six equations with six unknowns. Solve and find: ϕ(3) = 2/5.
Alternatively, observe, from Thales’ theorem,
6
that ϕ must be a straight line:
ϕ(x) = ax + b.
From ϕ(0) = 1, ϕ(5) = 0, we find a = −1/5, b = 1, i.e.
ϕ(i) ≡ 1 − (i/5),
which agrees with the above.
18.
A process moves on the integers 1, 2, 3, 4, and 5. It starts at 1 and, on each successive
step, moves to an integer greater than its present position, moving with equal proba-
bility to each of the remaining larger integers. State five is an absorbing state. Find
the expected number of steps to reach state five.
Solution. A Markov chain is defined an d its transition probability matrix is as follows:
P =
0
1
4
1
4
1
4
1
4
0 0
1
3
1
3
1
3
0 0 0
1
2
1
2
0 0 0 0 1
0 0 0 0 1
.
We apply first step analysis for the function
ψ(i) := E
i
S
5
, 1 ≤ i ≤ 5,
6
Thales’ theorem says (proved around the
year 600 BCE) says that if the lines L, L
′
are parallel then
DE
BC
=
AE
AC
=
AD
AB
.
16
where S
5
= inf{n ≥ 0 : X
n
= 5}. One of the equations is ψ(5) = 0 (obviously).
Another is
ψ(1) = 1 +
1
4
ψ(2) +
1
4
ψ(3) +
1
4
ψ(3) +
1
4
ψ(5).
It’s up to you to wr ite the remaining equations and solve to find
ψ(1) = 1 +
1
2
+
1
3
+
1
4
≈ 2.0833.
19.
Generalise the previous exercise, by replacing 5 by a general positive integer n. Find
the expected number of steps to reach state n, when starting from state 1. Test your
conjecture for several different values of n. Can you conjecture an estimate for the
expected number of steps to reach state n, for large n?
Solution. The answer here is
E
1
S
n
=
n−1
X
k=1
1
k
.
We here recognise the harmonic series:
n
X
k=1
1
k
≈ log n,
for large n, in the sense that the difference of the two sides converges to a constant.
So,
E
1
S
n
≈ log n,
when n is large.
20.
A gamb ler plays a game in which on each play he wins one dollar with probability p
and loses one dollar with probability q = 1 − p. The Gambler’s Ruin Problem is
the problem of finding
ϕ(x) :=the probability of winning an amount b
before losing everything, starting with state x
=P
x
(S
b
< S
0
).
1. Show that th is problem may be considered to be an absorb ing Markov chain with
states 0, 1, 2, . . . , b, with 0 and b absorbing states.
2. Write down the equations satisfied by ϕ(x).
3. If p = q = 1/2, show that
ϕ(x) = x/b.
4. If p 6= q, show that
ϕ(x) =
(q/p)
x
− 1
(q/p)
b
− 1
.
Solution. 1. If the current fortune is x the next fortune will be either x + 1 or x −1,
with probability p or 1, r espectively, as long as x is not b or x is not 0. We assume
independ en ce between games, so the next fortune will not depend on the previous
17
ones; whence the Markov property. If the fortune reaches 0 then the gambler must
stop playing. S o 0 is absorbing. If it reaches b then the gambler has reached the target
hence the play stops again. So both 0 and T are absorbing states. The transition
diagram is:
T
T−2
T−1
x+1
x−1
x
2
1
0
p p
p
p p
q q
q
q
q
1
1
2. The equations are:
ϕ(0) = 0
ϕ(b) = 1
ϕ(x) = pϕ(x + 1) + qϕ(x − 1), x = 1, 2, . . . , b − 1.
3. If p = q = 1/2, we have
ϕ(x) =
ϕ(x + 1) + ϕ(x − 1)
2
, x = 1, 2, . . . , b − 1.
This means that the point (x, ϕ(x)) in the plane is in the middle of the segment with
endpoints (x − 1, ϕ(x − 1)), (x + 1, ϕ(x + 1)). Hence the graph of the function ϕ(x)
must be on a s tr aight line (Thales’ theorem):
x
w
x+1
w
x−1
w
x
x−1
x+1
In other words,
ϕ(x) = Ax + B.
We determine the constants A, B from ϕ(0) = 0, ϕ(b) = 1. Thus , ϕ(x) = x/b.
4. If p 6= q, then this nice linear property does not h old. However, if we substitute the
given function to the equations, we see that they are satisfied.
21.
Consider the Markov chain with transition matrix
P =
1/2 1/3 1/6
3/4 0 1/4
0 1 0
18
(a) Show that this is irreducible and aperiodic.
(b) The process is started in state 1; find the probability that it is in state 3 after two
steps.
(c) Find the m atrix which is the limit of P
n
as n → ∞.
Solution
1/2
1/3
1/6
3/4
1/4 1
1
2
3
(a) Draw the transition diagram and observe that there is a path from every state to
any other state. Hence it is irreducible. Now consider a state, say state i = 1 and the
times n at which p
(n)
1,1
> 0. These times are 1, 2, 3, 4, 5, . . . and their gcd is 1. Hence it
is aperiodic. So the chain is regular.
(b)
P
1
(X
2
= 3) = p
(2)
1,3
=
3
X
i=1
p
1,i
p
i,3
= p
1,1
p
1,3
+ p
1,2
p
2,3
+ p
1,3
p
3,3
=
1
2
·
1
6
+
1
3
·
1
4
+
1
6
· 0 =
1
12
+
1
12
=
1
6
.
(c) The limit exists because the chain is regular. It is given by
lim
n→∞
P
n
=
π(1) π(2) π(3)
π(1) π(2) π(3)
π(1) π(2) π(3)
where π = (π(1), π(2), π(3)) is the stationary distribution which is found by solving
the balance equations
πP = π,
together with
π(1) + π(2) + π(3) = 1.
The balance equations are equivalent to
π(1)
1
6
+ π(1)
1
3
= π(2)
3
4
π(3) = π(2)
1
4
+ π(1)
1
6
.
Solving the last 3 equations with 3 unknowns we find
π(1) =
3
6
, π(2) =
2
6
, π(3) =
1
6
.
Hence
lim
n→∞
P
n
=
3/6 2/6 1/6
3/6 2/6 1/6
3/6 2/6 1/6
.
19
22.
Show that a Markov chain with transition matrix
P =
1 0 0
1/4 1/2 1/4
0 0 1
has more than one stationary distributions. Find the matrix that P
n
converges to, as
n → ∞, and verify that it is not a matrix all of whose rows are the same.
You should work out this exerc ise by direct methods, without appealing to the general
limiting theory of Markov chains–see lecture notes.
Solution. The transition diagram is:
1/2
2
1
3
1
1
1/4
1/4
Write the balance equations πP = π :
π(1) π(2) π(3)
1 0 0
1/4 1/2 1/4
0 0 1
=
π(1) π(2) π(3)
or
π(1) · 1 + π(2) · (1/4) + π(3) · 0 = π(1) (1)
π(1) · 0 + π(2) · (1/2) + π(3) · 0 = π(2) (2)
π(1) · 0 + π(2) · (1/4) + π(3) · 1 = π(3), (3)
together with the normalisation condition
P
π(i) = 1, i.e.
π(1) + π(2) + π(3) = 1. (4)
and solve for π(1), π(2), π(3). Equation (1) gives
π(2) = 0.
Equation (2) gives
π(2) = π(2),
i.e. it is useless. Equation (3) gives
π(3) = π(3),
again, obviously true. Equation (4) gives
π(1) + π(3) = 1.
Therefore, equations (1)–(4) are EQUIVALENT TO:
π(2) = 0, π(1) + π(3) = 1.
20
Hence we can set π(1) to ANY value we like between 0 and 1, s ay, π(1) ≡ p, and then
let π(3) = 1−p. Thus there is not just one stationary distribution but infinitely many.
For each value of p ∈ [0, 1], any π of the form
π =
p 0 1 − p
is a stationary distribution.
To find the limit of P
n
as n → ∞, we compute the entries of the matrix P
n
. Notice
that the (i, j)-entry of P
n
equals
p
(n)
i,j
= P
i
(X
n
= j).
If i = 1 we have
P
1
(X
n
= 1) = 1, P
1
(X
n
= 2) = 0, P
1
(X
n
= 3) = 0,
because state 1 is absorbing. Similarly, state 3 is absorbing:
P
3
(X
n
= 1) = 0, P
3
(X
n
= 2) = 0, P
3
(X
n
= 3) = 1.
We thus know the first and third rows of P
n
:
P
n
=
1 0 0
p
(n)
2,1
p
(n)
2,2
p
(n)
2,3
0 0 1
.
We now compute the missing entries of the second row by simple observations, based
on the fact that the chain, started in state 2, will remain at 2 for some time and then
will leave it and either go to 1 or 3:
P
2
(X
n
= 2) = P
2
(chain has stayed in state 2 for n consecutive steps) = (1/2)
n
.
P
2
(X
n
= 1) =
n
X
m=1
P
2
(X
m−1
= 2, X
m
= 1)
=
n
X
m=1
(1/2)
m−1
· (1/4)
=
1 − (1/2)
n
1 − (1/2)
·
1
4
=
1 − 0.5
n
2
.
P
2
(X
n
= 3) = 1 − P
2
(X
n
= 2) − P
2
(X
n
= 1) =
1 − 0.5
n
2
.
Therefore,
P
n
=
1 0 0
1−0.5
n
2
(0.5)
n
1−0.5
n
2
0 0 1
.
Since 0.5
n
→ 0 as n → ∞, we have
P
n
→
1 0 0
1/2 0 1/2
0 0 1
, as n → ∞.
21
23.
Toss a fair die repeatedly. Let S
n
denote the total of the outcomes thr ough the nth
toss. Show that there is a limiting value for the proportion of the first n values of S
n
that are divisible by 7, and compute the value for this limit.
Hint: The desired limit is a stationary distribution for an appropriate Markov chain
with 7 states.
Solution. An integer k ≥ 1 is divisible by 7 if it leaves remainder 0 when divided by
7. When we divide an integer k ≥ 1 by 7, the possible remainders are
0, 1, 2, 3, 4, 5, 6.
Let X
1
, X
2
, . . . be the outcomes of a fair die tossing. These are i.i.d. random variables
uniformly distributed in {1, 2, 3, 4, 5, 6}. We are asked to consider the sum
S
n
= X
1
+ ··· + X
n
.
Clearly, S
n
is an integer. We are interested in the remainder of S
n
when divided by
7. Call this R
n
. So:
R
n
:= the remainder of the division of S
n
by 7.
Note that the random variables R
1
, R
2
, R
3
, . . . form a Markov chain becaus e if we
know the value of R
n
, all we have to do to find the next value R
n+1
is to add X
n
to R
n
, divide by 7, and take the remainder of this division, as in elementary-school
arithmetic:
R
n+1
= the remainder of the division of R
n
+ X
n
by 7.
We need to find the transition probabilities
p
i,j
:=P (R
n+1
= j|R
n
= i)
=P ( the remainder of the division of i + X
n
by 7 equals j)
for this Markov chain, for all i, j ∈ {0, 1, 2, 3, 4, 5, 6}. But X
n
takes values in {1, 2, 3, 4, 5, 6}
with equal probabilities 1/6. If to an i we add an x chosen from {1, 2, 3, 4, 5, 6} and
then divide by 7 we are going to obtain any j in {0, 1, 2, 3, 4, 5, 6}. Therefore,
p
i,j
= 1/6, for all i and all j ∈ {0, 1, 2, 3, 4, 5, 6}.
We are asked to consider the proportion of the first n values of S
n
that are divisible
by 7, namely the quantity
1
n
n
X
k=1
1(R
k
= 0).
This quantity has a limit from the Strong Law of Large Numbers for Markov chains
and the limit is the s tationary distribution at state 0:
P
lim
n→∞
1
n
n
X
k=1
1(R
k
= 0) = π(0)
!
= 1
22
Therefore we need to compute π for the Markov chain (R
n
). This is very easy. From
symmetry, all states i must have the same π(i). Therefore
π(i) = 1/7, i = 0, 1, 2, 3, 4, 5, 6.
Hence
P
lim
n→∞
1
n
n
X
k=1
1(R
k
= 0) = 1/7
!
= 1.
In other words, if you toss a fair die 10, 000 times then approximately 1667 times n
you had a sum S
n
that was divisible by 7, and this is true with probability very close
to 1.
24.
(i) Consider a Markov chain on the vertices of a triangle: the chain moves from one
vertex to another with probability 1/2. Find the prob ability th at, in n steps, the chain
returns to the vertex it started from.
(ii) Suppose that we alter the probabilities as follows:
p
12
= p
23
= p
31
= 2/3, p
21
= p
32
= p
13
= 1/3.
Answer the same question as above.
Solution. (i) T he transition matrix is
P =
1
2
0 1 1
1 0 1
1 1 0
The characteristic polynomial is
det(xI −P) = x
3
−
1
2
x
2
−
1
2
x
whose roots are
x
1
:= 0, x
2
:= 1, x
3
:= −
1
2
.
Therefore,
p
(n)
11
= C
1
x
n
1
+ C
2
x
n
2
+ C
3
x
n
3
= C
2
x
n
2
+ C
3
x
n
3
,
where C
2
, C
3
are constants. Since, clearly, p
(0)
11
= 1, p
(1)
11
= p
11
= 0, we have
C
2
+ C
3
= 1
C
2
x
2
+ C
3
x
3
= 0.
Solving, we find C
2
= 1/3, C
3
= 2/3. So
p
(n)
11
=
1
3
+
2
3
(−1/2)
n
.
(ii) We now have
P =
1
3
0 1 2
2 0 1
1 2 0
23
The characteristic polynomial is
det(xI −P) = x
3
−
2
3
x −
1
3
=
1
3
(3x
3
− 2x − 1) :=
1
3
f(x).
Checking the divisors of the constant (1 or 2), we are lucky because we see that 1 is
a zero:
f(1) = 3 − 2 −1 = 0.
So we divide f (x) with x − 1. Since
3x
2
(x − 1) = 3x
3
− 3x
2
,
we have
f(x) − 3x
2
(x − 1) = 3x
2
− 2x − 1.
Since
3x(x − 1) = 3x
2
− 3x,
we have
3x
2
− 2x − 1 − 3x(x − 1) = x − 1.
Therefore,
f(x) = 3x
2
(x − 1) + 3x
2
− 2x − 1
= 3x
2
(x − 1) + 3x(x − 1) + (x − 1)
= (3x
2
+ 3x + 1)(x − 1).
So the other roots of f(x) = 0 are the roots of 3x
2
+ 3x + 1 = 0. The discriminant of
this quadratic is
3
2
− 4 · 3 · 1 = −3 < 0,
so the r oots are complex:
x
1
=
−1
2
+
√
−3
6
, x
2
=
−1
2
−
√
−3
6
.
Letting x
3
= 1 (the first root we found), we now have
p
(n)
11
= C
1
x
n
1
+ C
2
x
n
2
+ C
3
.
We need to determine the constants C
1
, C
2
, C
3
. But we have
1 = p
(0)
11
= C
1
+ C
2
+ C
3
0 = p
(1)
11
= C
1
x
1
+ C
2
x
2
+ C
3
x
3
2
9
= p
(2)
11
= C
1
x
2
1
+ C
2
x
2
2
+ C
3
x
2
3
Solving for the constants, we find
p
(n)
11
=
1
3
+
2
3
(−1/
√
3)
n
cos(nπ/6).
24
25.
A certain experiment is believed to be described by a two-state Markov chain with
the transition matrix P, where
P =
0.5 0.5
p 1 − p
,
and the parameter p is not known. When the experiment is performed many times,
the chain ends in state one approximately 20 percent of the time and in state two
approximately 80 percent of the time. Comp ute a sensible estimate for the unk nown
parameter p an d exp lain how you found it.
Solution. If X
k
is the position of the chain at time k, we are being told that when we
perform the exp eriment (i.e. watch the chain), s ay, n times we see that approximately
20% of the time the chain is in state 1:
1
n
n
X
n=1
1(X
k
= 1) ≈ 0.2 (5)
We know, from the Strong Law (=Theorem) of Large Numbers that
P
lim
n→∞
1
n
N
X
k=1
1(X
k
= 1) = π(1)
!
= 1, (6)
where π = (π(1), π(2)) is the s tationary distribution. Combining the obs ervation (5)
with the Law of Large Numbers (6) we obtain
π(1) ≈ 0.2.
We can easily compute π because
π(1)
1
2
= π(2)p,
and, of course,
π(1) + π(2) = 1,
whence
π(1) =
2p
1 + 2p
.
Solving
2p
1+2p
= 0.2 we find p = 1/8.
26.
Here is a trick to try on your friends. Shuffle a deck of cards and deal out one at a
time. Count the face cards each as ten. Ask your friend to at one of the first ten cards;
if this card is a s ix, she is to look at the card turns up six cards later; if this card is a
three, she is to look at the card turns up three cards later, and so forth. Eventually
she will reach a where she is to look at a card that tu rns up x cards later but there are
x cards left. You then tell her the last card that she looked at even though you did
not know her starting point. You tell her you do this by watching her, and she cannot
disguise the times that she looks at the cards. In fact just do the same procedure and,
25
even though you do not start at the point as she does, you will most likely end at the
same point. Why?
Solution. Let X
n
denote the value of the n-th card of the experiment when you start
from the x-th card from the top. Let Y
n
denote the value of the n-th card of another
experiment when you start from the y-th card from the top. You use exactly the same
deck with the cards in the same order in both experiments. If, for some n and some
m we have
X
n
= Y
m
,
then X
n+1
= Y
m+1
, X
n+2
= Y
m+2
, etc. The point is that the event
{∃m, n such that X
n
= Y
m
}
has a large probability. In fact, it has p robability close to 1.
27.
You h ave N books on your shelf, labelled 1, 2, . . . , N. You pick a book j with prob-
ability 1/N. Then you place it on the left of all others on the shelf. You r epeat the
process, independently. Construct a Markov chain which takes values in the set of all
N! permutations of the books.
(i) Discuss the state space of the Markov chain. Think how many elements it has and
how are its elements represented.
(ii) Show that the chain is regular (irreducible and aperiodic) and find its stationary
distribution.
Hint: You can guess the stationary distribution before computing it.
Solution. (i) T he state space is
S = {all function σ : {1, 2, . . . , N} → {1, 2, . . . , N} which are one-to-one and onto}.
These σ are called permutations and there are N ! of them:
|S| = N!
Each σ can be represented by a the list of each values:
σ = (σ(1), σ(2), . . . , σ(N))
i.e. σ(i) is its values at i.
(ii) Let us find the transition probabilities. If σ is the current state and we pick the
j-th book and place it in front, then the next state is the same if j = 1 or
(σ(j), σ(1), σ(2), . . . , σ(j − 1), σ(j + 1), . . .),
if j 6= 1. There are N possible next states and each occurs with probability 1/N . If
we denote the next state obtained when picking the j-th book by σ
(j)
then we have
p
σ,σ
(j)
= 1/N, j = 1, . . . , N.
(For example, σ
(1)
= σ.) And, of course, p
σ,τ
= 0 if τ is not of the form σ
(j)
for some j.
The chain is aperiodic because p
σ,σ
= 1/N for all σ. It is irreducible because, clearly,
26
it can move from any state (i.e. any arr an gement of books) to any other. Hence it is
regular.
It does not require a lot of thought to see that there is complete symmetry! Therefore
all states must have the same stationary distribution, i.e.
π(σ) =
1
N!
, for all σ ∈ S.
You can easily verify that
π(σ) =
X
τ
π(τ)p
τ,σ
, for all σ ∈ S,
i.e. the balance equations are satisfied and so our educated guess was correct.
28.
In unprofitable times corporations sometimes suspend dividend payments. Suppose
that after a dividend has been paid the next one will be paid with probability 0.9,
while after a dividend is s uspended the next one will be suspended with p robability
0.6. In the long run what is the fraction of dividends that will be paid?
Solution. We here have a Markov chain with two states:
State 1: “dividend paid”
State 2: “dividend suspended”
We are given the following transition probabilities:
p
1,1
= 0.9, p
2,2
= 0.6
Hence
p
1,2
= 0.1, p
2,1
= 0.4
Let π be the stationary distribution. In the long run the fraction of dividends that
will be paid equals π(1). But
π(1) × 0.1 = π(2) × 0.4
and
π(1) + π(2) = 1,
whence
π(1) = 4/5.
So, in the long run, 80% of the d ividen ds will be paid.
29.
Five white balls and five black balls are distributed in two urns in such a way that each
urn contains five balls. At each step we draw one ball from each urn and exchange
them. Let X
n
be the number of white balls in the left urn at time n.
(a) Compute the transition probability for X
n
.
(b) Find the stationary distribution and show that it corresponds to picking five balls
at random to be in the left urn.
Solution Clearly, (X
0
, X
1
, X
2
, . . .) is a Markov chain with state space
S = {0, 1, 2, 3, 4, 5}.
27
(a) If, at some point of time, X
n
= x (i.e. the number of white balls in the left urn is
x) then there are 5 −x black balls in the left urn, while the right urn contains x black
and 5 − x white balls. Clearly,
p
x,x+1
= P (X
n+1
= x + 1|X
n
= x)
= P (pick a white ball from the right urn and a black ball from the left urn)
=
5 − x
5
×
5 − x
5
,
as long as x < 5. On the other hand,
p
x,x−1
= P (X
n+1
= x − 1|X
n
= x)
= P (pick a white ball from the left urn and a black ball from the right urn)
=
x
5
×
x
5
,
as long as x > 0. When 0 < x < 5, we have
p
x,x
= 1 − p
x,x+1
− p
x,x−1
,
because there is no chance that the number of balls change by more than 1 ball.
Summarising, the ans wer is:
p
x,y
=
5−x
5
2
, if 0 ≤ x ≤ 4, y = x + 1
x
5
2
, if 1 ≤ x ≤ 5, y = x − 1
1 −
5−x
5
2
−
x
5
2
, if 1 ≤ x ≤ 4, y = x,
0, in all other cases.
If you want, you may draw the transition diagram:
5
5
2
4
5
2
3
5
2
2
5
2
1
5
2
1
5
2
2
5
2
3
5
2
5
5
2
4
5
2
0
1
2
3
4 5
On this diagram, I d id not indicate the p
x,x
.
(b) To compute the stationary distribution, cut the diagram between states x and
x − 1 and equate the two flows, as usual:
π(x)p
x,x−1
= π(x − 1)p
x−1,x
,
i.e.
π(x)
x
5
2
= π(x − 1)
5 − (x − 1)
5
2
which gives
π(x) =
6 − x
x
2
π(x − 1)
28
We thus have
π(1) =
5
1
2
π(0) = 25π(0)
π(2) =
4
2
2
π(1) =
4
2
2
5
1
2
π(0) = 100π(0)
π(3) =
3
3
2
π(2) =
3
3
2
4
2
2
5
1
2
π(0) = 100π(0)
π(4) =
2
4
2
π(3) =
2
4
2
3
3
2
4
2
2
5
1
2
π(0) = 25π(0)
π(5) =
1
5
2
π(4) =
1
5
2
2
4
2
3
3
2
4
2
2
5
1
2
π(0) = π(0).
We fin d π(0) by normalisation:
π(0) + π(1) + π(2) + π(3) + π(4) + π(5) = 1
⇒ π(0) = 1/(1 + 25 + 100 + 100 + 25 + 1) = 1/252.
Putting everything together, we have
π(0) =
1
252
, π(1) =
25
252
, π(2) =
100
252
, π(3) =
100
252
, π(4) =
25
252
, π(5) =
1
252
.
This is th e answer f or the stationary distribu tion.
We are also asked to interpret π(x) as
From a lot of 10 (= 5 black + 5 white balls) pick 5 at random and place
them in the left urn (place the rest in the right urn) and consider the chance
that amongst the 5 balls x are white.
We know how to answer this problem: it is a hypergeometric distribution:
Chance that amongst the 5 balls x are white =
5
x
5
5 − x
10
5
=
5
x
2
255
, x = 0, . . . , 5.
This is PRECISELY the distribution obtained ab ove. Hence π(x) IS A HYPERGE-
OMETRIC DISTRIBUTION.
30.
An auto insurance company classifies its customers in three categories: poor, satisfac-
tory and pr eferred. No one moves from poor to preferred or from preferred to poor
in one year. 40% of the customers in the poor category become satisfactory, 30% of
those in the satisfactory category moves to preferred, while 10% become poor; 20% of
those in th e preferred category are downgraded to satisfactory.
(a) Write the transition matrix for the m odel.
(b) What is the limiting fraction of drivers in each of these categories? (Clearly s tate
which theorem you are applying in order to compute this.)
29
Solution. (a) The transition probabilities for this Markov chain with three states are
as follows:
POOR SATISFACTORY PREFERRED
POOR 0.6 0.4 0
SATISFACTORY 0.1 0.6 0.3
PREFERRED 0 0.2 0.8
,
so that the transition probability matrix is
P =
0.6 0.4 0
0.1 0.6 0.3
0 0.2 0.8
.
(b) We will find the limiting fraction of drivers in each of these categories from the
components of the stationary distribution vector π, which satisfies the following equa-
tion:
π = πP.
The former is equivalent to the following system of linear equations:
π(1) = 0.6π(1) + 0.1π(2)
π(2) = 0.4π(1) + 0.6π(2) + 0.2π(3)
π(3) = 0.3π(2) + 0.8π(3)
1 = π(1) + π(2) + π(3). (7)
This has the following solution: π = (
1
11
,
4
11
,
6
11
).
Thus, the limiting f raction of drivers in th e POOR category is
1
11
, in the SATIS-
FACTO RY category—
4
11
, and in the PREFERRED category—
6
11
. By the way, the
proportions of the drivers in each category in 15 years ap proximate these numbers
with two significant digits (you can check it, calculating P
15
and looking at its rows).
31.
The President of the United States tells person A his or her intention to run or not to
run in the next election. Then A relays the news to B, who in turn relays the message
to C, and so forth, always to some new person. We assume that there is a probability
a that a person will change the answer from yes to no when transmitting it to the next
person and a p robability b that he or she will change it from no to yes. We choose as
states the message, either yes or no. The transition probabilities are
p
y es,no
= a, p
no,yes
= b.
The initial state represents the President’s choice. S uppose a = 0.5, b = 0.75.
(a) Assume that the President says that he or she will run. Find the expected length
of time before the first time the ans wer is passed on incorrectly.
(b) Find the mean recurrence time for each s tate. In other words, find the expected
amount of time r
i
, for i = yes and i = no required to return to that state.
(c) Write down the transition probability matrix P and find lim
n→∞
P
n
.
30
(d) Repeat (b) for general a and b.
(e) Repeat (c) for general a and b.
Solution. (a) The expected length of time before the first answer is passed on incor-
rectly, i.e. that the Pr esident will not run in the next election, equals the mean of the
geometrically distributed random variable with parameter 1 − p
y es,no
= 1 − a = 0.5.
Thus, the expected length of time before the first answer is passed on incorrectly is 2.
What is found can be viewed as the mean first passage time from the state yes to the
state no. By making the corresponding ergodic Markov chain with transition matrix
P =
0.5 0.5
0.75 0.25
(8)
absorbing (with absorbing state being no), check that the time until absorp tion will
be 2. This is nothing but the mean first passage time from yes to no in the original
Markov chain.
(b) We use the following result to find mean recurrence time for each state:
for an ergodic Markov chain, the mean recurrence time for state i is
r
i
= E
i
T
i
=
1
π(i)
,
where π(i) is the ith component of the stationary distribution for the tran-
sition probability matrix.
The transition probability matrix (8) has the following stationary distribution:
π =
.6, .4
,
from which we find the mean recurrence time for the state yes is
5
3
and for the state
no is
5
2
.
(c) The transition probability matrix is specified in (8)—it has no zero entries and the
corresponding chain is irreducible and aperiodic. For such a chain
lim
n→+∞
P
n
=
π(1) π(2)
π(1) π(2)
.
Thus,
lim
n→+∞
P
n
=
0.6 0.4
0.6 0.4
.
(d) We apply the same arguments as in (b) and fi nd that the transition probability
matrix
P =
1 − a a
b 1 − b
has th e following fixed probability vector:
π =
b
a+b
,
a
a+b
,
so that the mean recurrence time for the state yes is 1 +
a
b
and for the state no is
1 +
b
a
.
(d) Suppose a 6= 0 and b 6= 0 to avoid absorb ing states and achieve regularity. Then
the corresponding Markov chain is regular. Thus,
lim
n→+∞
P
n
=
b
a+b
a
a+b
b
a+b
a
a+b
.
31
32.
A fair die is rolled repeatedly and independently. S how by the results of the Markov
chain theory that the mean time between occurrences of a given number is 6.
Solution. We construct a Markov chain with the states 1, 2, . . . , 6 and transition
probabilities p
ij
=
1
6
for each i, j = 1, 2, . . . , 6. Such Markov chain has the transition
probability matrix which has all its entries equal to
1
6
. The chain is irr ed ucible and
aperiodic and its stationary distribution is nothing but
π =
1
6
,
1
6
,
1
6
,
1
6
,
1
6
,
1
6
.
This means that th e mean time between occurren ces of a given number is 6.
33.
Give an example of a three-state ir reducible-aperiodic Markov chain that is not re-
versible.
Solution.
We will see how to choose transition probabilities in such a way that the chain would
not be reversible.
If our three-state chain was a reversible chain, that would meant that the detailed
balance equations hold, i.e.
π(1)p
12
= π(2)p
21
π(1)p
13
= π(3)p
31
π(2)p
23
= π(3)p
32
.
From this it is easy to see that if the detailed balance equations hold, then necessarily
p
13
p
32
p
21
= p
12
p
23
p
31
. So, choose them in such a way that this does not hold.
For instance, p
13
= 0.7, p
32
= 0.2, p
21
= 0.3, p
12
= 0.2, p
23
= 0.2, p
31
= 0.1. And
these specify an ergodic Markov chain which is not reversible.
Another solution is: Consider the Markov chain with three states {1, 2, 3} and deter-
ministic transitions: 1 → 2 → 3 → 1. Clearly, the Markov chain in r everse time moves
like 1 → 3 → 2 → 1 and so its law is not the same. (We can tell the arrow of time by
runnin g the fi lm backward s.)
34.
Let P be the transition matrix of an irreducible-aperiodic Markov chain. Let π be its
stationary distribution. Suppose the Markov chain starts with P (X
0
= i) = π(i), for
all i ∈ S.
(a) [Review question] Show that P (X
n
= i) = π(i) f or all i ∈ S and all n.
(b) Fix N ≥ 1 and consider the process X
∗
0
= X
N
, X
∗
1
= X
N−1
, . . . Show that it is
Markov.
(c) Let P
∗
be the transition probability matrix of P
∗
(it is called: the reverse transition
matrix). Find its entries p
∗
i,j
.
(d) Show that P and P
∗
they have the same stationary d istrib ution π.
Solution. (a) By definition, π(i) satisfies
π(i) =
X
j
π(j)p
j,i
, i ∈ S.
32
If P (X
0
= i) = π(i), then
P (X
1
= i) =
X
j
P (X
0
= j, X
1
= i)
=
X
j
P (X
0
= j, X
1
= i)
=
X
j
π(j)p
j,i
= π(i).
Hence P (X
1
= i) ≡ π(i). Repeating the process we find P (X
2
= i) ≡ π(i), and so on,
we have P (X
n
= i) ≡ π(i) f or all n.
(b) Fix n and consider the future of X
∗
after n. This is X
∗
n + 1, X
∗
n + 2, . . .. Con-
sider also the past of X
∗
before n. This is X
∗
n−1
, X
∗
n−2
, . . .. But
(X
∗
n+1
, X
∗
n+2
, . . .) = (X
N−n−1
, X
N−n−2
, . . .)
is the past of X before time N − n. And
(X
∗
n−1
, X
∗
n−2
, . . .) = (X
N−n+1
, X
N−n+2
, . . .)
is the future of X after time N − n. Since X is Markov, these are independent,
conditional on X
N−n
. But X
N−n
= X
∗
n
. Hence, given X
∗
n
, the future of X
∗
after n is
independ ent of the past of X
∗
before n, and this is true for all n, and so X
∗
is also
Markov.
(c) Here we assume that P (X
0
= i) ≡ π(i). Hence, by (a), P (X
n
= i) ≡ π(i) for all
n. We have
p
∗
i,j
:= P (X
∗
n+1
= j|X
∗
n
= i) = P (X
N−n−1
= j|X
N−n
= i)
=
P (X
N−n
= i|X
N−n−1
= j)P (X
N−n−1
= j)
P (X
N−n
= i)
=
p
j,i
π(j)
π(i)
.
(d) We need to check that, for all i ∈ S,
π(i) =
X
k
π(k)p
∗
k,i
. (9)
This is a matter of algebra.
35.
Consider a random walk on the following graph consisting of two nested dodecagons:
33
(a) Explain why it is reversible (this is true for any RWonG).
(b) Find the stationary distribution.
(c) Show that the mean recurrence time (mean time to return) to any state is the
same for all states, and compute this time.
(d) Let X
n
be the position of the chain at time n (it takes values in a set of 24
elements). Let Z
n
= 1 if X
n
is in the inner dodecagon and Z
n
= 2 is X
n
is at the
outer dodecagon. Is (Z
n
) Markov?
Solution. (a) Our chain has 24 states. From each of the states we jump to any of three
neighbour ing states with equal probability
1
3
(see the figure below: each undirected
edge combines two directed edges-arrows). The chain is reversible, i.e. it is possible
to move from any state to any other state. This is obviously the case for any random
walk on a connected graph. Note that the notion of reversibility of the discrete Markov
chain is related to the topology of the graph on which the chain is being run.
1
2
3
4
5
6
7
8
10
11
12
24
13
14
15
16
17
18
19
20
21
22
23
9
1/3
1/3
1/3
(b) The stationary d istribution exists and because of the symmetry the stationary
vector has all components equal, and since the numb er of the components is 24 the
stationary vector is
π = (
1
24
,
1
24
, . . . ,
1
24
) ∈ R
24
.
(c) The mean recurrence time for the state i is 1/π(i) = 24, ∀i = 1, 2, . . . , 24.
(d) Observe first that
P (Z
n
= 2|X
n
= i) = 1/3, as long as i = 13, . . . , 24,
and
P (Z
n
= 1|X
n
= i) = 1/3, as long as i = 1, . . . , 12.
We now verify that (Z
n
) is Markov. (We s hall argue directly. Alternatively, see
section on “fu nctions of Markov chains” from my lecture notes.) By the definition of
conditional probability,
P (Z
n+1
= 2|Z
n
= 1, Z
n−1
= w, . . .)
=
24
X
i=13
P (Z
n+1
= 2|X
n
= i, Z
n
= 1, Z
n−1
= w, . . .) P (X
n
= i|Z
n
= 1, Z
n−1
= w, . . .)
34
Due to the fact that (X
n
) is Markov, when we know that X
n
= i that the future after
n is in dependent from the past before n. But Z
n+1
belongs to the future after n, while
Z
n−1
= w, . . . belongs to the past before n. Hence, for i = 13, . . . , 24,
P (Z
n+1
= 2|X
n
= i, Z
n
= 1, Z
n−1
= w, . . .) = P (Z
n+1
= 2|X
n
= i) = 1/3.
Hence
P (Z
n+1
= 2|Z
n
= 1, Z
n−1
= w, . . .) =
24
X
i=13
1
3
P (X
n
= i|Z
n
= 1, Z
n−1
= w, . . .) =
1
3
,
because, obviously,
24
X
i=13
P (X
n
= i|Z
n
= 1, Z
n−1
= w, . . .) = 1.
(If Z
n
= 1 then X
n
is in the ins ide dodecagon.) Thus,
P (Z
n+1
= 2|Z
n
= 1, Z
n−1
= w, . . .) = P (Z
n+1
= 2|Z
n
= 1).
Similarly, we can show
P (Z
n+1
= 1|Z
n
= 2, Z
n−1
= w, . . .) = P (Z
n+1
= 1|Z
n
= 2).
Hence, no matter what the value of Z
n
is, the future of Z after n is independent of
the past of Z before n. Hence Z is Markov as well.
36.
Consider a Markov chain in the set {1, 2, 3} with transition probabilities
p
12
= p
23
= p
31
= p, p
13
= p
32
= p
21
= q = 1 − p,
where 0 < p < 1. Determine whether the Markov chain is reversible.
Solution. If p = 1/2 then the chain is a random walk on a graph; so it is reversible.
If p 6= 1/2 then Kolmogorov’s loop criterion requires that
p
12
p
23
p
31
= p
13
p
32
p
21
.
But this is equivalent to
p
3
= q
3
which is not true (unless p = 1/2). Hence the chain is not reversible if p 6= 1/2.
37.
Consider a Markov chain whose transition diagram is as below:
1 2
3
4
5
6
7
8
9
10
0.6
0.1
1
11
1
1
1
0.3
0.7
0.2
0.5
0.7
1
0.4
1
0.5
1
(i) Which (if any) states are in essential?
(ii) Which (if any) states are absorbing?
(iii) Find the communication classes.
(iv) Is the chain irreducible?
(v) Find the period of each essential state. Verify that
essential s tates that belong to the same communica-
tion class have the same period.
(vi) Are there any aperiodic communication classes?
(vii) Will your answers to the questions (i)–(vi) change
if we replace the positive transition probabilities by
other positive probabilities and why?
35
Solution. (i) The inessential states are: 1, 2, 3, 5, 6, because each of them leads to a
state from which it is not possible to return.
(ii) 4 is the only absorbing state.
(iii) As usual, let [i] den ote the class of state i i.e. [i] = {j ∈ S : j ! i}. We have:
[1] = {1}.
[2] = {2}.
[3] = {3}.
[4] = {4}.
[5] = {5, 6}.
[6] = {5, 6}.
[7] = {7, 8}.
[8] = {7, 8}.
[9] = {9, 10, 11}
[10] = {9, 10, 11}
[11] = {9, 10, 11}
Therefore th ere are 7 communication classes:
{1}, {2}, {3}, {4}, {5, 6}, {7, 8}, {9, 10, 11}
(iv) No because there are many communication classes.
(v) Recall that for each essential state i, its period d(i) is the gcd of all n such that
p
(n)
i,i
> 0. So:
d(4) = gcd{1, 2, 3, . . .} = 1
d(7) = gcd{1, 2, 3, . . .} = 1
d(8) = gcd{1, 2, 3, . . .} = 1
d(9) = gcd{3, 6, 9, . . .} = 3
d(10) = gcd{3, 6, 9, . . .} = 3
d(11) = gcd{3, 6, 9, . . .} = 3
Observe d(7) = d(8) = 1, and d(10) = d(11) = d(9) = 3.
(vi) Yes: {4} and {7, 8} are aperiodic commun ication classes (each has period 1).
(vii) No the answers will not change. These questions depend only on whether, for
each i, j, p
i,j
is positive or zero.
38.
Consider a Markov chain, with state space S the set of all positive integers, whose
transition diagram is as f ollows:
1
2
3 4
5
6
7
1
1/2
1/2
1/2
1/2
1/3 1/3
1/3
1/3
2/3 2/3
2/3
(i) Which states are essential and which inessential?
(ii) Which states are transient and which recurrent?
(iii) Discuss the asymptotic behaviour of the chain, i.e. find the limit, as n → ∞, of
P
i
(X
n
= j) for each i and j.
36
Solution. (i) The states 3, 4, 5, . . . communicate with one another. So they are all
essential. However state 1 leads to 3 but 3 d oes not lead to 1. Hence 1 is in essential.
Likewise, 2 is inessential.
(ii) Every inessential state is transient. Hence both 1 and 2 are transient. On the other
hand, the Markov chain will eventually take values only in the set {3, 4, 5, . . .}. We
observe that the chain on this set is the same typ e of chain we discussed in gambler’s
ruin problem with p = 2/3, q = 1/3. Since p > q the chain is transient. Therefore all
states of the given chain are transient.
(iii) Since the states are transient, we have that X
n
→ ∞ as n → ∞, with pr ob ability
1. Therefore,
P
i
(X
n
= j) → 0, as n → ∞,
for all i and j.
39.
Consider the following Markov chain, which is motivated by the “umbrellas problem”
(see–but it’s not necessary–an earlier exercise). Here, p + q = 1, 0 < p < 1.
0
1 2
3
4
p
q
p q
q
p
p
1
(i) Is the chain irreducible?
(ii) Does it have a stationary distribution?
Hint: Write the balance equations, together with the normalisation condition and draw
your conclusions.
(iii) Find the period d(i) of each state i.
(iv) Decide which states are transient and which recurrent.
Hint: Let τ
j
be the first hitting time of state j. Let N ≥ 1 As in the gambler’s ruin
problem, let ϕ(i) := P
i
(τ
N
< τ
0
). What is ϕ(0)? What is ϕ(N)? For 1 < i < N , how
does ϕ(i) relate to ϕ(i − 1) and ϕ(i + 1)? Solve the equations you thus obtain to find
ϕ(i). Let N → ∞. What do you conclude?
Solution. (i) Yes because all states communicate with one another. (There is just
one communication class).
(ii) Let us write balance equations in the form of equating flows (see handou t). We
have
π(0) = π(1)q
π(1)p = π(1)p
π(2)q = π(2)q
···
Let π(1) = c. Then π(0) = cq and
π(1) = π(2) = π(3) = ··· = c.
The n ormalisation condition is
P
∞
i=0
π(i) = 1. This implies that c = 0. Hence
π(i) = 0 for all i. This is NOT a probability distribution. Hence there is no stationary
distribution.
37
(iii) We only have to find the period of one state, since all states communicate with
one another. Pick state 0. We have d(0) = gcd{2, 4, 6, . . .} = 2. Hence d(i) = 2 for all
i.
(iv) Let ϕ(i) := P
i
(τ
N
< τ
0
). We have
ϕ(0) = 0, ϕ(N) = 1.
Indeed, if X
0
= 0 then τ
0
= 0 and so ϕ(0) = P
0
(τ
N
< 0) = 0. On the other hand, if
X
0
= N then τ
N
= 0 and τ
0
≥ 1, so ϕ(N) = P
N
(0 < τ
0
) = 1.
Now, from first-step analysis, for each i ∈ [1, N − 1], we have
ϕ(i) = p
i,i+1
ϕ(i + 1) + p
i,i−1
ϕ(i).
But p
i,i+1
= p
i,i−1
= p if i is odd and p
i,i+1
= p
i,i−1
= q if i is even and positive. So
p[ϕ(i + 1) − ϕ(i)] = q[ϕ(i) − ϕ(i − 1)], i odd
q[ϕ(i + 1) − ϕ(i)] = p[ϕ(i) − ϕ(i − 1)], i even.
Hence
ϕ(2) − ϕ(1) =
q
p
[ϕ(1) − ϕ(0)] =
q
p
ϕ(1)
ϕ(3) − ϕ(2) =
p
q
[ϕ(2) − ϕ(1)] = ϕ(1)
ϕ(4) − ϕ(3) =
q
p
[ϕ(3) − ϕ(2)] =
q
p
ϕ(1)
ϕ(5) − ϕ(4) =
p
q
[ϕ(4) − ϕ(3)] = ϕ(1),
and, in general,
ϕ(i) − ϕ(i − 1) =
q
p
ϕ(1) i even
ϕ(i) − ϕ(i − 1) = ϕ(1) i odd.
Next, use the “fundamental theorem of (discrete) calculus”:
ϕ(i) = [ϕ(i) − ϕ(i − 1)] + [ϕ(i − 1) − ϕ(i − 2)] + ··· + [ϕ(2) − ϕ(1)] + ϕ(1).
If i is even then, amongst 1, 2, . . . , i there are i/2 even numbers and i/2 odd numbers.
ϕ(i) =
q
p
i/2
ϕ(1) +
i
2
ϕ(1) i even
Suppose N is even. Use ϕ(N) = 1 to get that, if both i and N are even,
ϕ(i) =
q
p
i/2
+
i
2
q
p
N/2
+
N
2
= P
i
(τ
N
< τ
0
).
Taking the limit as N → ∞, we find
P
i
(τ
0
= ∞) = 0, i even.
This implies that P
i
(τ
0
< ∞) = 1. The same conclusion holds for i odd. (After all,
all states communicate with one another.) Therefore all states are recurrent.
38
40.
Suppose that X
1
, X
2
. . . are i.i.d. random variables with values, say, in Z and common
distribution p(i) := P (X
1
= i), i ∈ Z.
(i) Explain why the sequence has the Markov property.
(ii) Let A be a subset of the integers such that
P
i∈A
p(i) > 0. Consider the first
hitting time τ
A
of A and the random variable Z := X
τ
A
. Show that the distribution
of Z is the conditional distribution of X
1
given that X
1
∈ A.
Hint: Clearly, {Z = i} =
S
∞
n=1
{Z = i, τ
A
= n}, and the events in this union are
disjoint; therefore the probability of the u nion is the su m of the probabilities of the
events comprising it.
Solution. (i) As explained in the beginning of the lectures.
(ii) Since τ
A
is the FIRST time th at A is hit, it means that
τ
A
= n ⇐⇒ X
1
6∈ A, X
2
6∈ A, . . . , X
n−1
6∈ A, X
n
∈ A.
Therefore, with Z = X
τ
A
, and i ∈ A,
P (Z = i) =
∞
X
n=1
P (X
τ
A
= i, τ
A
= n)
=
∞
X
n=1
P (X
n
= i, X
1
6∈ A, X
2
6∈ A, . . . , X
n−1
6∈ A, X
n
∈ A)
=
∞
X
n=1
P (X
n
= i, X
1
6∈ A, X
2
6∈ A, . . . , X
n−1
6∈ A)
=
∞
X
n=1
p(i)P (X
1
6∈ A)
n−1
[geometric series]
= p(i)
1
1 − P (X
1
6∈ A)
.
=
p(i)
P (X
1
∈ A)
.
If i 6∈ A, then, obviously, P (Z = i) = 0. So it is clear that P (Z = i) = P (X
1
= i|X
1
∈
A), for all i, from th e definition of conditional probability.
41.
Consider a random walk on the following infinite graph:
The graph continues
ad infinitum in the
same manner.
39
Here, each state has exactly 3 neighbouring states (i.e. its degree is 3) and so the
probability of moving to one of them is 1/3.
(i) Let 0 be th e “central” state. (Actually, a closer look shows that no state deserves
to be central, for they are all equivalent. So we just arbitrarily pick one and call it
central.) Having d on e that, let D(i) be the distance of a state i from 0, i.e. the number
of “hops” required to reach 0 starting from i. So D(0) = 0, each neighbour i of 0 has
D(i) = 1, etc. Let X
n
be the position of the chain at time n. Observe that th e process
Z
n
= D(X
n
) has the Markov property. (See lecture notes for criterion!) The question
is:
Find its transition probabilities.
(ii) Using the results from the gambler’s r uin pr ob lem, show that (Z
n
) is trans ient.
(iii) Use (ii) to explain why (X
n
) is also transient.
Solution. (i) First draw a figure:
The states with the
same distance from 0
are shown in this fig-
ure as belonging to
the same circle.
Next observe that if Z
n
= k (i.e. if the distance from 0 is k) then, no matter where
X
n
is actually located the distance Z
n+1
of the next state X
n+1
from 0 will either be
k + 1 with probability 2/3 or k − 1 with probability 1/3. And, of course, if Z
n
= 0
then Z
n+1
= 1. So
P (Z
n+1
= k + 1|Z
n
= k) = 2/3, k ≥ 0
P (Z
n+1
= k − 1|Z
n
= k) = 1/3, k ≥ 1
P (Z
n+1
= 1|Z
n
= 0) = 1.
(ii) Since 2/3 > 1/3, the chain (Z
n
) is trans ient.
(iii) We have that Z
n
→ ∞ as n → ∞, with probability 1. This means that for any k,
there is a time n
0
such that for all n ≥ n
0
we have D(X
n
) ≥ k, and this happens with
probability 1. So, with pr ob ability 1, the chain (X
n
) will visit states with distance from
0 less than k only finitely many times. This means that the chain (X
n
) is trans ient.
42.
A company requires N employees to function properly. If an employee becomes sick
then he or she is replaced by a new one. It takes 1 week for a new employee to be
recruited and to start working. Time here is measur ed in weeks.
(i) If at the beginning of week n there are X
n
employees working and Y
n
of them get
sick d uring week n then show that at the beginning of week n + 1 there will be
X
n+1
= N − Y
n
40
employees working.
(ii) Suppose that each employee becomes sick in dependently with probability p. Show
that
P (Y
n
= y|X
n
= x) =
x
y
p
y
(1 − p)
x−y
, y = 0, 1, . . . , x.
(iii) Show that (X
n
) is a Markov chain with state space S = {0, 1, . . . , N} and derive
its transition probabilities.
(vi) Write the balance equation for the stationary distribution π of the chain.
(v) What is the number of emp loyees working in steady state?
Do this without using (vi) by assuming that the X is in steady state [i.e. that X
0
(and
therefore each X
n
) has distribution π] and by taking expectations on the equation you
derived in (i).
Solution. (i) This is elementary: Since every time an employee gets sick he or she is
replaced by a new one, but it takes 1 week for the new employee to start working, it
means that those employees who got sick durin g week n − 1 will be replaced by new
ones who will start working sometime during week n and so, by the end of week n,
the number of employees will be brought up to N, pr ovided nobody got sick during
week n. If the latter happens, then we subtract the Y
n
employees who got sick during
week n to obtained the desired equation.
(ii) Again, this is easy: If X
n
= x, at most x employees can get sick. Each one gets
sick with probability p, independently of one another, so the total number, Y
n
, of sick
employees has the Binomial(x, p) distribution.
(iii) We have that Y
n
depends only on X
n
and not on X
n−1
, X
n−2
, . . ., and therefore
P (X
n+1
= j|X
n
= i, X
n−1
= i
1
, X
n−2
= i
2
. . .) = P (X
n+1
= j|X
n
= i). Hence X is
Markov. We are asked to derive p
i,j
= P (X
n+1
= j|X
n
= i) for all i, j ∈ S. If X
n
= i
then Y
n
≤ i and so X
n+1
≥ N − i, so the only possible values j for which p
i,j
> 0 are
j = N − i, . . . , N. In fact, P (X
n+1
= j|X
n
= i) = P (Y
n
= N − j|X
n
= i) and s o,
using the formulae of (ii),
p
i,j
=
i
N − j
p
N−j
(1 − p)
i−N+j
, j = N −i, . . . , N
0, otherwise
, i = 0, 1, . . . , N.
(vi) The balance equations are:
π(j) =
N
X
i=0
π(i)p
i,j
=
N
X
i=N−j
π(i)
i
N − j
p
N−j
(1 − p)
i−N+j
.
(v) If X
0
has distribution π then X
n
has distribution π for all n. S o EX
n
≡ µ does not
depend on n. Now , if X
n
= x, Y
n
is Binomial(x, p) and therefore E(Y
n
|X
n
= x) = px.
So
EY
n
=
N
X
x=0
pxP (X
n
= x) = pEX
n
= pµ.
41
Since EX
n+1
= N − EY
n
we have
µ = N − pµ,
whence
µ =
N
1 + p
.
This is the mean number of employees in steady state. So, for example, if p = 10%,
then µ ≈ 0.91N .
43.
(i) Let X be the number of heads in n i.i.d. coin tosses where the probability of heads
is p. Find the generating function ϕ(z) := Ez
X
of X.
(ii) Let Y be a random variable with P (Y = k) = (1 − p)
k−1
p, k = 1, 2, . . . Find the
generating function of Y .
Solution. (i) The random variable X, which is defined as the number of heads in n
i.i.d. coin tosses where the probability of heads is p, is binomially distributed:
P (X = k) =
n
k
p
k
(1 − p)
n−k
.
Thus,
ϕ(z) := Ez
X
=
n
X
k=0
P (X = k)z
k
=
n
X
k=0
n
k
(1 − p)
n−k
(pz)
k
= ((1 − p) + zp)
n
= (q + zp)
n
, where q = 1 − p.
(ii) The random variable Y , defined by
P (Y = k) = (1 − p)
k−1
p, k = 1, 2, . . .
has th e following generating function:
ϕ(z) := Ez
Y
=
∞
X
k=1
P (Y = k)z
k
=
∞
X
k=1
(1 − p)
k−1
pz
k
=
p
1 − p
∞
X
k=1
[(1 − p)z]
k
=
p
1 − p
1
1 − z(1 − p)
− 1
=
pz
1 − zq
, where q = 1 − p.
42
44.
A random variable X with values in {1, 2, . . . , }∪{∞} has generating function ϕ(z) =
Ez
X
.
(i) Express P (X = 0) in terms of ϕ.
(ii) Express P (X = ∞) in terms of ϕ.
(iii) Express EX and varX in terms of ϕ.
Solution. (i) ϕ(0) =
∞
P
k=0
P (X = k)z
k
|
z=0
= P (X = 0), thus, P (X = 0) = ϕ(0).
(ii) The following mus t hold:
∞
P
k=0
P (X = k) + P (X = ∞) = 1. This may be rewritten
as follows: ϕ(1) + P (X = ∞) = 1, fr om wh ich we get
P (X = ∞) = 1 − ϕ(1).
(iii) By definition of the expected value of a discrete random variable
EX =
∞
X
k=0
kP (X = k).
Now note, that
ϕ
′
(z) =
∞
X
k=0
kP (X = k)z
k−1
,
so that ϕ
′
(1) should give nothing but EX. We conclude that
EX = ϕ
′
(1).
Let p
k
:= P (X = k). Now we take the second derivative of ϕ(z):
ϕ
′′
(z) =
∞
X
k=2
k(k −1)p
k
z
k−2
,
so that
ϕ
′′
(1) =
∞
X
k=2
(k
2
p
k
− kp
k
) =
∞
X
k=2
k
2
p
k
−
∞
X
k=2
kp
k
=
∞
X
k=0
k
2
p
k
−
∞
X
k=0
kp
k
= EX
2
− EX = EX
2
− ϕ
′
(1),
from which we get that EX
2
= ϕ
′
(1) + ϕ
′′
(1). But this is enough for var X, since
var X = EX
2
− (EX)
2
= ϕ
′
(1) + ϕ
′′
(1) −
ϕ
′
(1)
2
.
45.
A random variable X with values in {1, 2, . . . , } ∪ {∞} has generating function
ϕ(z) =
1 −
p
1 − 4pqz
2
2qz
,
43
where p, q ≥ 0 and p + q = 1.
(i) Compute P (X = ∞). (Consider all possible values of p).
(ii) For those values of p for which P (X = ∞) = 0 compute EX.
Solution.
(i) As it was found above, P (X = ∞) = 1 − ϕ(1), and particularly
P (X = ∞) = 1 − ϕ(1) = 1 −
1 −
√
1 − 4pq
2q
= 1 −
1 − |p −q|
2q
=
1 −
p
q
, p < q
0, p ≥ q
(ii) It f ollows that P (X = ∞) = 0 for p ≥
1
2
. The expected value of X is given by
EX = ϕ
′
(1) =
1
p−q
, p >
1
2
∞, p =
1
2
and we are done.
46.
You can go up the stair by climbing 1 or 2 steps at a time. There are n steps in total.
In how many ways can you climb all steps?
Hint 1: If n = 3, you can reach the 3d step by climbing 1 at a time, or 2 first and 1
next, or 1 first and 2 next, i . e. there are 3 ways.
Hint 2: if w
m
is the number of ways to climb m steps, how is w
m
related to w
m−1
and
w
m−2
?
Hint 3: Consider the generating function
P
m
z
m
w
m
.
Solution. Jus t before being at step m you are either at step m −1 or at step m −2.
Hence
w
m
= w
m−1
+ w
m−2
, m ≥ 2. (10)
Here, s tep 0 means being at the bottom of the stairs. So
w
0
= 1, w
1
= 1.
So
w
2
= w
1
+ w
0
= 2
w
3
= w
2
+ w
1
= 3
w
4
= w
3
+ w
2
= 5
w
5
= w
4
+ w
3
= 8
w
6
= w
5
+ w
4
= 13
w
7
= w
6
+ w
5
= 21
············
How do we find a formula for w
n
? Here is where generating f unctions come to rescue.
Let
W (s) =
X
m≥0
w
m
s
m
be the generating of (w
m
, m ≥ 0). Then the generating f unction of (w
m+1
, m ≥ 0) is
X
m≥0
w
m+1
s
m
= s
−1
(W (s) − w
0
)
44
and the generating function of (w
m+2
, m ≥ 0) is
X
m≥0
w
m+2
s
m
= s
−2
(W (s) − w
0
− sw
1
).
From the recursion
w
m+2
= w
m+1
+ w
m
, m ≥ 0
(obtained from (10) by replacing m by m + 2) we have (and this is were linearity i s
used) that the generating fun ction of (w
m+2
, m ≥ 0) equals the sum of the generating
functions of (w
m+1
, m ≥ 0) and (w
m
, m ≥ 0), namely,
s
−2
(W (s) − w
0
− sw
1
) = s
−1
(W (s) − w
0
) + W (s). (11)
Since w
0
= w
1
= 1, we can solve for W (s) and find
W (s) =
−1
s
2
+ s − 1
.
Essentially, what generating functions have done for us is to transform the LIN-
EAR recursion (10) into the ALGEBRAIC equation (11). This is something you
have learnt in your introductory Mathematics courses. The tools and recipes
associated with LINEARITY are indispensable for anyone who does anything
of value. Thus, keep them always in your bag of tricks.
The question we ask is:
Which sequence (w
n
, n ≥ 0) has generating function W (s)?
We start by noting that the polynomial s
2
+ s − 1 has two roots:
a = (
√
5 − 1)/2, b = (−1 −
√
5)/2.
Hence s
2
+ s − 1 = (s − a)(s − b), and so, by simple algebra,
W (s) =
1
b − a
1
s − a
−
1
s − b
.
Write this as
W (s) =
1
b − a
b
bs − ab
−
a
as − ab
.
Noting that ab = −1, we further have
W (s) =
b
b − a
1
1 + bs
−
a
b − a
1
1 + as
.
But
1
1+bs
=
P
∞
n=0
(−bs)
n
,
1
1+as
=
P
∞
n=0
(−as)
n
, and so W (s) is the generating function
of
w
n
=
b
b − a
(−b)
n
−
a
b − a
(−a)
n
, n ≥ 0.
This can be written also as
w
n
=
(1 +
√
5)
n+1
− (1 −
√
5)
n+1
2
n+1
√
5
which is always an integer (why?)
45
47.
Consider a branching process starting with Z
0
= 1 and branching mechanism
p
1
= 1 − p, p
2
= p.
(Each individual gives birth to 1 or 2 children with probability 1−p or p, respectively.)
Let Z
n
be the size of the n-th generation. Compute the probabilities P (Z
n
= k) for
all possible values of k, the generating function ϕ
n
(z) = Ez
Z
n
, and the mean size of
the n-th generation m
n
= EZ
n
. Do the computations in whichever order is convenient
for you.
Solution. The mean number of offspring of a typical in dividual is
m := (1 − p) + 2p = 1 + p.
Therefore
EZ
n
= m
n
= (1 + p)
n
.
Let q = 1 − p. To compute P (Z
2
= 4), we consider all possibilities to have 4 children
in the second generation. There is only one possibility:
Therefore P (Z
2
= 4) = p
2
.
To compute P (Z
2
= 3) we have
and so P (Z
2
= 3) = pqp + ppq.
For P (Z
2
= 2) we have
and so P (Z
2
= 2) = qp + pq
2
And for P (Z
2
= 1) there is only one possibility,
and so P (Z
2
= 2) = q
2
.
You can continue in this mann er to compute P (Z
3
= k), etc.
The generating function of the branching mechanism is
ϕ(z) = p
1
z + p
1
z
2
= qz + pz
2
.
46
So ϕ
1
(z) = Ez
Z
1
= ϕ(z). Next, we have ϕ
2
(z) = ϕ
1
(ϕ(z)) an d so
ϕ
2
(z) = ϕ(ϕ(z)) = qϕ(z) + pϕ(z)
2
= p
3
z
4
+ 2 p
2
qz
3
+
qp + pq
2
z
2
+ q
2
z.
Similarly, ϕ
3
(z) = ϕ
2
(ϕ(z)) and so
ϕ
3
(z) = p
3
ϕ(z)
4
+ 2 p
2
qϕ(z)
3
+
qp + pq
2
ϕ(z)
2
+ q
2
ϕ(z)
= p
7
z
8
+ 4 p
6
qz
7
+ p(2 (qp + pq
2
)p
3
+ 4 p
4
q
2
)z
6
+ p(2 q
2
p
3
+ 4 (qp + pq
2
)p
2
q)z
5
+ (qp
3
+ p(4 q
3
p
2
+ (qp + pq
2
)
2
))z
4
+ (2 q
2
p
2
+ 2 pq
2
(qp + pq
2
))z
3
+ (q(qp + pq
2
) + pq
4
)z
2
+ q
3
z.
48.
Consider a branching process with Z
0
= 1 and branching mechanism
p
0
=
1
10
, p
1
=
7
10
, p
2
=
2
10
.
(i) Compute probability of ultimate extinction.
(ii) Compute the mean size of the n-th generation.
(iii) Compute the standard deviation of the size of the n-th generation.
Solution. (i) T he generating function of the branching mechanism is
ϕ(z) =
1
10
z
0
+
7
10
z
1
+
2
10
z
2
=
1
10
(1 + 7z + 2z
2
).
The probability ε of ultimate extinction is the smallest positive z such that
ϕ(z) = z.
We have to solve
1 + 7z + 2z
2
= 10z.
Its solutions are 1, 1/2. Therefore,
ε = 1/2.
(ii) The mean number of offspring of an individual is
m =
2
10
+
1
10
× 2 =
11
10
.
Therefore th e mean size of the n-th generation is
EZ
n
= m
n
= (11/10)
n
.
(iii) As in Exercise 2 above, we have that
ϕ
′
(1) = EX, ϕ
′′
(1) = EX
2
−EX, var X = EX
2
−(EX)
2
= ϕ
′′
(1) + EX −(EX)
2
.
Since ϕ
n
(z) = ϕ
n−1
(ϕ(z)), we have
ϕ
′
n
(z) = ϕ
′
n−1
(ϕ(z)) ϕ
′
(z)
ϕ
′′
n
(z) = ϕ
′′
n−1
(ϕ(z)) ϕ
′
(z)
2
+ ϕ
′
n−1
(ϕ(z)) ϕ
′′
(z).
47
Setting z = 1 and using that ϕ(1) = 1 we have
ϕ
′′
n
(1) = ϕ
′′
n−1
(1) ϕ
′
(1)
2
+ ϕ
′
n−1
(1) ϕ
′′
(1).
But ϕ
′
(1) = m, ϕ
′
n−1
(1) = m
n−1
and so
ϕ
′′
n
(1) = ϕ
′′
n−1
(1) m
2
+ m
n−1
ϕ
′′
(1).
Iterating this we find
ϕ
′′
n
(1) = ϕ
′′
(1)
2n−2
X
k=n−1
m
k
.
We here have m = 11/10, ϕ
′′
(1) = 4/10. But then
σ
2
n
= var Z
n
= ϕ
′′
n
(1) + EZ
n
− (EZ
n
)
2
= ϕ
′′
(1)
2n−2
X
k=n−1
m
k
+ m
n
−m
2n
= ϕ
′′
(1)m
n−1
m
n
− 1
m − 1
+ m
n
− m
2n
=
4
10
m
n−1
m
n
− 1
1/10
−m
n
(m
n
−1)
= 4m
n−1
(m
n
− 1) − m
n
(m
n
− 1)
= (4 − m)m
n−1
(m
n
− 1)
=
29
10
11
10
n−1
11
10
n
− 1
Of course, the standard deviation is the square r oot of this number.
49.
Consider the same branching process as above, but now start with Z
0
= m, an arbi-
trary positive integer. Answer the same questions.
Solution. (i) The process behaves as the superposition of N i.i.d. copies of the
previous process. This becomes extinct if and only if each of the N copies becomes
extinct and so, by in dependence, the extinction probability is
ε
N
= (1/2)
N
.
(ii) Th e n-th generation of the new process is the sum of the populations of the n-th
generations of each of the N constituent processes. T herefore the mean size of the
n-th generation is
Nm
n
= N(11/10)
n
.
(iii) For the same reason, the standard deviation of the size of the n-th generation is
√
Nσ
n
.
50.
Show th at a branching process cannot have a stationary distribution π with π(i) > 0
for s ome i > 0.
48
Solution. If the mean number m of offspring is ≤ 1 then we know that the process will
become extinct f or sure, i.e. it will be absorbed by state 0. Hence the only stationary
distribution satisfies
π(0) = 1, π(i) = 0, i ≥ 1.
If the mean number m of offspring is > 1 then we know that the probability that it
will become extinct is ε < 1, i.e. P
1
(τ
0
= ∞) = 1 − ε > 0. But we showed in Part
(i) of Problem 8 above that P
i
(τ
0
= ∞) = 1 − ε
i
> 0 for all i. Hence the process is
transient. And so there is NO stationary distribution at all.
51.
Consider the following Markov chain, which is motivated from the “umbrellas problem”
(see earlier exercise). Here, p + q = 1, 0 < p < 1.
0
1 2
3
4
p
q
p q
q
p
p
1
Is it positive recurrent?
Solution. We showed in another problem that the chain is irreducible and recurrent.
Let us now see if it is positive recurrent. In other words, let us see if E
i
T
i
< ∞ for
some (and thus all) i.
As we said in the lectures, this is equivalent to having π(i) > 0 for all i w here π is
solution to the balance equations. We solved the balance equations in the past and
found that π(i) = c for all i, where c is a constant. But there is no c > 0 for which
P
∞
i=0
π(i) = 1. And so th e chain is not positive recurrent; it is null recurrent.
52.
Consider a Markov chain with state sp ace {0, 1, 2, . . .} and transition probabilities
p
i,i−1
= 1, i = 1, 2, 3, . . .
p
0,i
= p
i
, i = 0, 1, 2, 3, . . .
where p
i
> 0 for all i and
P
i≥0
p
i
= 1.
(i) Is the chain irreducible?
(ii) What is the period of state 0?
(iii) What is the perio d of state i, for all values of i?
(iv) Under what condition is th e chain positive recurrent?
(v) If the chain is positive recurrent, what is the mean number of steps required for it
to return to state i if it starts from i?
Solution.
i−
1
p
2
i−
1
p
p
3
i
p
p
0
i
1
2
3
0
1
1
1 1
(i) Yes it is. It is possible to move from any state to any other state.
(ii) It is 1.
49
(iii) Same.
(iv) We write balance equations:
π(i) = π(i + 1) + π(0)p
i
, i ≥ 0.
Solving this we find
π(i) = π(0)(1 − p
0
− ··· − p
i−1
), i ≥ 1.
The normalising condition gives
1 =
∞
X
i=0
π(i) = π(0)
∞
X
i=0
(1 − p
0
−··· −p
i−1
).
This can be satisfied if and only if
∞
X
i=0
(1 − p
0
− ··· − p
i−1
) < ∞
This is th e condition for positive recurrence.
Note that, since p
0
+ ··· + p
i−1
= P
0
(X
1
≤ i − 1), the condition can be written as
∞
X
i=0
P
0
(X
1
≥ i) < ∞
But
∞
X
i=0
P
0
(X
1
≥ i) ==
∞
X
i=0
E
0
(X
1
≥ i) = E
0
∞
X
i=0
1(X
1
≥ i) = E
0
X
X
i=0
1 = E
0
(X + 1)
so the condition is equ ivalent to
E
0
X
1
< ∞.
(v)
E
i
T
i
=
1
π(i)
.
53.
Consider a simple symmetric random walk S
n
= ξ
1
+···+ξ
n
, started fr om S
0
= 0.
Find the following pr ob abilities:
(i) P (S
4
= k), for all possible values of k.
(ii) P (S
n
≥ 0 ∀n = 1, 2, 3, 4).
(iii) P (S
n
6= 0 ∀n = 1, 2, 3, 4).
(iv) P (S
n
≤ 2 ∀n = 1, 2, 3, 4).
(v) P (|S
n
| ≤ 2 ∀n = 1, 2, 3, 4).
Solution. (i) We have
P (S
4
= k) =
4
4+k
2
2
−4
, k = −4, − 2, 0, 2, 4,
50
and so
P (S
4
= −4) = P (S
4
= 4) = 1/16, P (S
4
= −2) = P (S
4
= 2) = 4/16, P (S
4
= 0) = 6/16.
0
1
2
3
4
−1
−2
−3
−4
0 1 2 3 4
(ii) Sin ce the random walk is symmetric, all paths of the
same length are equally likely. T here are 6 paths compris-
ing the event {(S
n
≥ 0 ∀n = 1, 2, 3, 4} and so P ((S
n
≥
0 ∀n = 1, 2, 3, 4) = 6/16.
(iii) There are just 2 paths comprising the event {S
n
>
0 ∀n = 1, 2, 3, 4}. Hence P (S
n
6= 0 ∀n = 1, 2, 3, 4) = 4/16.
(iv) There are 2 paths violating the condition {S
n
≤ 2 ∀n =
1, 2, 3, 4}. Hence P (S
n
≤ 2 ∀n = 1, 2, 3, 4) = (16 − 2)/16 =
14/16.
(v) Th ere are 4 paths violating the condition {|S
n
| ≤ 2 ∀n =
1, 2, 3, 4}. Hence P (|S
n
| ≤ 2 ∀n = 1, 2, 3, 4) = (16−4)/16 =
12/16.
54.
Consider a simple random walk S
n
= ξ
1
+ ··· + ξ
n
, started from S
0
= 0, with
P (ξ
1
= 1) = p, P (ξ
1
= −1) = q, p + q = 1.
(i) Show that
E(S
m
| S
n
) =
(
m
n
S
n
, if m ≤ n
S
n
, if m > n
.
(ii) Are you surprised by the fact that the answer does not depend on p?
Solution. (i) If m > n then S
m
= S
n
+ (S
m
− S
n
), so
E(S
m
| S
n
) = S
n
+ E(S
m
− S
n
| S
n
).
But S
m
− S
n
= ξ
n+1
+ ··· + ξ
m
. Since ξ
n+1
, . . . , ξ
m
are independent of S
n
, we have
E(S
m
− S
n
| S
n
) = E(S
m
− S
n
) =
m
X
k=n+1
Eξ
k
= (m − n)(p − q).
Thus,
E(S
m
− S
n
| S
n
) = S
n
+ (p − q)(m − n), if m > n.
If m ≤ n, then
E(S
m
| S
n
) = E
m
X
k=1
ξ
k
| S
n
!
=
m
X
k=1
E(ξ
k
| S
n
)
Now notice that for all k = 1, . . . , n,
E(ξ
k
| S
n
) = E(ξ
1
| S
n
),
because the random variables ξ
1
, . . . , ξ
n
are i.i.d. and S
n
is a symmetric function of
them (interchanging two does not change the sum). Hence for all m = 1, . . . , n,
E(S
m
| S
n
) = mE(ξ
1
| S
n
).
51
This is true even for m = n. But, in this case, E(S
m
| S
n
) = E(S
n
| S
n
) = S
n
, so that
E(ξ
1
| S
n
) = S
n
/n. Thus,
E(S
m
− S
n
| S
n
) =
m
n
S
n
, if m ≤ n.
(ii) At first sight, yes, you should be surprised. But look (think) again...
55.
Consider a simple random walk S
n
again, which does not necessarily start from 0,
and define the processes the processes:
X
n
= S
2n
, n ≥ 0
Y
n
= S
2n+1
, n ≥ 0
Z
n
= e
S
n
, n ≥ 0
(i) Show that each of them is Markov and identify their state spaces.
(ii) Compute their trans ition probabilities.
Solution. (i) The first two are Markov because they are a subsequence of a Markov
chain. The third is Markov because x 7→ e
x
is a bijection from R into (0, ∞). The
state space of the first two is Z. The state space of the third is the set S = {e
k
: k ∈
Z} = {. . . , e
−2
, e
−1
, 1, e, e
2
, e
3
, . . .}.
(ii) For the first one we h ave
P (X
n+1
= j|X
n
= i) = P (S
2n
= j|S
2n
= i) = P (i+ξ
2n+1
+ξ
2n
= j) = P (ξ
1
+ξ
2
= j−i).
Hence, given i, the only possible values of j are i − 2, i, i + 2. For all other values of
j, the trans ition probability is zero. We have
P (X
n+1
= i + 2|X
n
= i) = P (ξ
1
= ξ
2
= 1) = p
2
P (X
n+1
= i − 2|X
n
= i) = P (ξ
1
= ξ
2
= −1) = q
2
P (X
n+1
= i|X
n
= i) = P (ξ
1
= 1, ξ
2
= −1 or ξ
1
= −1, ξ
2
= 1) = 2pq
The second process has the same transition probabilities.
For the third process we have
P (Z
n+1
= e
k+1
|Z
n
e
k
) = P (S
n+1
= k + 1|S
n
= k) = p
P (Z
n+1
= e
k−1
|Z
n
e
k
) = P (S
n+1
= k −1|S
n
= k) = q
56.
Consider a simple random walk S
n
again, and suppose it starts from 0. As usual,
P (ξ
1
= 1) = p, P (ξ
1
= −1) = q = 1 − p. Compute Ee
αS
n
for α ∈ R.
Solution. We have S
n
= ξ
1
+ ··· + ξ
n
. By independence
Ee
αS
n
= E
h
e
αξ
1
···e
αξ
n
i
= E
h
e
αξ
1
i
···E
h
e
αξ
n
i
=
E
h
e
αξ
1
i
n
= (pe
α
+ qe
−α
)
n
.
52
57.
(i) Explain why P (lim
n→∞
S
n
= ∞) = 1 is p > q and, similarly, P (lim
n→∞
S
n
=
−∞) = 1 if p < q.
(ii) What can you say about the asymptotic behaviour of S
n
as n → ∞ when p = q?
Solution. (i) T he Strong Law of Large Numbers (SLLN) says that
P ( lim
n→∞
S
n
/n = p − q) = 1,
because Eξ
1
= p − q. If p > q, then SLLN implies that
P ( lim
n→∞
S
n
/n > 0) = 1.
But
{ lim
n→∞
S
n
/n > 0} ⊂ { lim
n→∞
S
n
= ∞}.
Since the event on the left has probability 1, so does the event on the right, i.e.
P ( lim
n→∞
S
n
= ∞) = 1, if p > q.
If, on the other hand , p < q, then p − q < 0, and so SLLN implies that
P ( lim
n→∞
S
n
/n < 0) = 1.
But
{ lim
n→∞
S
n
/n < 0} ⊂ { lim
n→∞
S
n
= −∞}.
Since the event on the left has probability 1, so does the event on the right, i.e.
P ( lim
n→∞
S
n
= −∞) = 1, if p < q.
(ii) If p = q, then p − q = 0, and the fact that S
n
/n converges to 0 cannot be used to
say something about the sequence S
n
other than that the sequence S
n
has no limit.
So, we may conclude that
P (S
n
has no limit as n → ∞) = 1, if p = q.
Stronger conclusions are possible, as we saw in the lectures.
58.
For a simple symmetric random walk let f
n
be the p robability of first return to 0
at time n. Compute f
n
for n = 1, . . . , 6 first by ap plying the general formula and then
by path counting (i.e. by considering the possible paths that contribute to the event).
Solution. Obviously, f
n
= 0 if n is odd. Recall the formula
f
2k
=
1/2
k
(−1)
k−1
, k ∈ N.
53
With k = 1, 2, 3, we have
f
2
=
1/2
1
=
1
2
f
4
= −
1/2
2
= −
(1/2)(1/2 − 1)
2
=
1
8
f
6
=
1/2
3
= −
(1/2)(1/2 −1)(1/2 − 2)
6
=
3
16
f
8
= −
1/2
4
= −
(1/2)(1/2 − 1)(1/2 − 2)(1/2 − 3)
24
=
5
128
.
To do path counting, we consider, e.g. th e last case. The possible paths contributing
to th e event {T
′
0
= 8} are the ones in the figure below as well as their reflections:
Each path consists of 8 segments, so it has probability 2
−8
. There are 5 paths, so
f
8
= 10/2
8
= 5/128.
59.
Consider a simple symmetric random walk starting from 0. Equalisation at time
n means that S
n
= 0, and its probability is denoted by u
n
.
(i) Show that for m ≥ 1, f
2m
= u
2m−2
− u
2m
.
(ii) Using part (i), find a closed-form expr ession for the sum f
2
+ f
4
+ ··· + f
2m
.
(iii) Using part (i), show th at
P
∞
k=1
f
2k
= 1. (One can also obtain this statement from
the fact that F (x) = 1 − (1 − x)
1/2
.)
(iv) Show that the probability of no equalisation in the first 2m steps equals the
probability of equalisation at 2m.
60.
A fair coin is tossed repeatedly and independently. Find th e expected number of tosses
required until the patter HTHH appears.
Solution. It’s easy to see that the Markov chain described by the following transition
diagram captures exactly what we are looking for.
H HT HTH HTHH
1/2
1/2 1/2 1/2
1/2
1/2
1/2
1/2
1
Rename the states ∅, H, HT, HT H, HT HH as 0, 1, 2, 3, 4, respectively, and let ψ
i
be
the average number of steps required for the state 4 to be reached if the starting state
54
is i. Writing fi rst-step (backwards) equations we have
ψ
0
= 1 +
1
2
ψ
0
+
1
2
ψ
1
ψ
1
= 1 +
1
2
ψ
1
+
1
2
ψ
2
ψ
2
= 1 +
1
2
ψ
0
+
1
2
ψ
3
ψ
3
= 1 +
1
2
ψ
3
+
1
2
ψ
4
.
Also, obviously, ψ
4
= 0. Solving, we fin d
ψ
3
= 8, ψ
2
= 14, ψ
1
= 16, ψ
0
= 18.
So the answer is: “it takes, on the average, 18 coin tosses to see the pattern HTHH
for th e first time”.
61.
Show that the stationary distribution for the Ehrenfest chain is Binomial.
Solution. The Ehr en fest chain has state space
S = {0, 1, . . . , n}
and transition probabilities
p
i,i+1
= 1 −
i
n
, p
i,i−1
=
i
n
, i = 0, . . . , n.
From the transition diagram we immediately deduce that detailed balance equations
must h old, so, if π denotes the stationary distribution,
π(i)p
i,i−1
= π(i − 1)p
i−1,i
, 1 ≤ i ≤ n,
or
π(i) =
n − i + 1
i
π(i −1), 1 ≤ i ≤ n,
iterating of which gives
π(i) =
n − i + 1
i
n − i + 2
i − 1
···
n − 1
2
n
1
π(0) =
n!
(n − i)!i!
π(0),
which is immediately recognisable as Binomial distribution.
62.
A Markov chain has transition probability matrix
P =
0 1 0 0
0 0 1/3 2/3
1 0 0 0
0 1/2 1/2 0
Draw the transition diagram.
Are there any absorbing states?
Which are the communicating classes?
Can you find a stationary distribution?
55
What are the periods of the states?
Are there any inessential states?
Which states are recurrent?
Which states are transient?
Which states are positive recurrent?
Solution.
1
3
2
4
1
1/3
2/3
1
1/2
1/2
• There are no abs orbing states because there is no state i for which p
i,i
= 1.
• All states commu nicate with one another. Therefore there is on ly one communicating
class, {1, 2, 3, 4}, the whole state space. (We r efer to this by saying that th e chain is
irreducible.)
• Yes, of course we can. We can ALWAYS find a stationary distribution if the state
space is FINITE. It can be found by solving the system of equations (known as balance
equations)
πP = π,
which, in explicit form, yield
π(1) = π(3)
π(2) = π(1) +
1
2
π(4)
π(3) =
1
3
π(2) +
1
2
π(4)
π(4) =
2
3
π(2)
Solving these, along with the normalisation condition π(1) + π(2) + π(3) + π(4) = 1,
we find
π(1) = π(4) = π(3) = 9/2, π(2) = 27/4.
• Since the chain is ir reducible the periods of all the states are the same. So let take
a particular state, say state 4 and consider th e set
{n ≥ 1 : p
(n)
4,4
> 0}.
We see that the first few elements of this set are
{2, 5, 6, . . .}.
We immediately deduce that the greatest common divisor of the set is 1. Therefore
the period of state 4 is 1. And so each state has period 1. (We refer to this by saying
that the chain is aperiodic.)
• Since all states communicate with one another there are no inessential states.
• Since π(i) > 0 for all i, all states are recurrent.
• Since all states are recurrent there are no transient states.
• Since π(i) > 0 for all i, all states are positive recurrent.
56
63.
In tennis the winner of a game is the first player to win four points, un less the score is
4–3, in which case the game must continue until one player wins by two points. Suppose
that the game has reached the point where one player is trying to get two points ahead
to win and that the server will independently win the point with probability 0.6. What
is the probability the s erver w ill win th e game if the score is tied 3-3? if she is ahead
by one point? Behind by one point?
Solution. Say that a score x-y means that the server has x points and the other
player y. If the current score is 3-3 the next s core is either 4-3 or 3-4. In either case,
the game must continue until one of the players is ahead by 2 points. So let us say
that i r ep resents the difference x − y. We model the situation by a Markov chain as
follows:
1
1
−2
−1 0
1
2
0.6 0.6 0.6
0.4 0.4 0.4
Let ϕ
i
be the probability that the server wins, i.e. that state 2 is reached before state
−2. First-step equations yield:
ϕ
i
= 0.6ϕ
i+1
+ 0.4ϕ
i−1
, −1 ≤ i ≤ 1.
In other words,
ϕ
−1
= 0.6ϕ
0
+ 0.4ϕ
−2
ϕ
0
= 0.6ϕ
1
+ 0.4ϕ
−1
ϕ
1
= 0.6ϕ
2
+ 0.4ϕ
0
Of course,
ϕ
−2
= 0, ϕ
2
= 1.
Solving, we find
ϕ
0
=
0.6
2
1 − 2 × 0.6 × 0.4
≈ 0.69, ϕ
1
≈ 0.88, ϕ
−1
≈ 0.42.
64.
Consider a simple rand om walk with p = 0.7, starting from zero. Find the probability
that state 2 is reached before state −3. Compu te the mean number of s teps until the
random walk reaches state 2 or state 3 for the first time.
Solution. Let ϕ
i
be the probability that state 2 is reached before state −3, starting
from state i. By writing first-step equations we have:
ϕ
i
= pϕ
i+1
+ qϕ
i−1
, −3 < i < 2.
In other words,
ϕ
−2
= 0.7ϕ
−1
+ 0.3ϕ
−3
ϕ
−1
= 0.7ϕ
0
+ 0.3ϕ
−2
ϕ
0
= 0.7ϕ
1
+ 0.3ϕ
−1
ϕ
1
= 0.7ϕ
2
+ 0.3ϕ
0
57
We also have, of course,
ϕ
−3
= 0, ϕ
2
= 1.
By solving these equations we find:
ϕ
i
=
(q/p)
i+3
− 1
(q/p)
5
− 1
, −3 ≤ i ≤ 2.
Therefore
ϕ
0
=
(3/7)
3
− 1
(3/7)
5
− 1
≈ 0.93.
Next, let t
i
be the mean number of steps until the random walk r eaches state 2 or state
3 for the first time, starting from state i. By w riting first-step equ ations we have:
t
i
= 1 + pt
i+1
+ qt
i−1
, −3 < i < 2.
In other words,
t
−2
= 1 + 0.7t
−1
+ 0.3t
−3
t
−1
= 1 + 0.7t
0
+ 0.3t
−2
t
0
= 1 + 0.7t
1
+ 0.3t
−1
t
1
= 1 + 0.7t
2
+ 0.3t
0
We also have, of course,
t
2
= 0, t
−3
= 0.
By solving these equations we find:
t
i
=
5
p − q
(q/p)
i+3
− 1
(q/p)
5
− 1
−
i + 3
p − q
, −3 ≤ i ≤ 2.
Therefore
t
0
=
5
0.4
(3/7)
3
− 1
(3/7)
5
− 1
−
3
0.4
≈ 4.18.
65.
A gambler has £9 and has the opportunity of p laying a game in which the pr ob ability
is 0.4 that he wins an amount equal to his stake, and probability 0.6 that he loses h is
stake. He is allowed to decide how much to stake at each game (in multiple of 10p).
How should he choose the stakes to maximise his chances of increasing his capital to
£10?
66.
Let ξ
1
, ξ
2
, . . . be i.i.d. r.v.’s with values in, say, Z and P (ξ
1
= x) = p(x), x ∈ Z.
Let A ⊆ Z such that P (ξ
1
∈ A) > 0. Let T
A
= inf{n ≥ 1 : ξ
n
∈ A}. Show that
P (ξ
T
A
= x) = p(x)/
P
a∈A
p(a), x ∈ A.
Solution. Let x ∈ A.
P (ξ
T
A
= x) =
∞
X
n=1
P (ξ
n
= x, ξ
1
6∈ A, . . . , ξ
n−1
6∈ A)
=
∞
X
n=1
p(x)P (ξ
1
6∈ A)
n−1
= p(x)
1
P (ξ
1
6∈ A)
=
p(x)
P
a∈A
p(a)
.
58
67.
For a simple symmetric random walk starting from 0, compute ES
4
n
.
Solution. We have that S
n
= ξ
1
+ ··· + ξ
n
, where ξ
1
, . . . , ξ
n
are i.i.d. with P (ξ
1
=
1) = P (ξ
1
= −1) = 1/2. When we expand the fourth power of the sum we have
S
4
n
=ξ
4
1
+ ··· + ξ
4
n
+ ξ
2
1
ξ
2
2
+ ··· + ξ
2
n−1
ξ
2
n
+ ξ
3
1
ξ
2
+ ··· + ξ
3
n−1
ξ
n
+ ξ
2
1
ξ
2
ξ
3
+ ··· + ξ
2
n−2
ξ
n−1
ξ
n
+ ξ
1
ξ
2
ξ
3
ξ
4
+ ··· + ξ
n−3
ξ
n−2
ξ
n−1
ξ
n
.
After taking expectation, we see that the expectation of each term in the last three
rows is zero, because Eξ
i
= 0 and because of independence. There are n terms in the
first row and 3(n
2
− n) terms in the second one. Hence
ES
4
n
= nEξ
4
1
+ 3(n
2
− n)Eξ
2
1
Eξ
2
2
.
But ξ
2
1
= ξ
4
1
= 1. So the answer is:
ES
4
n
= n + 3(n
2
− n) = 3n
2
− 2n.
68.
For a simple random walk, compute E(S
n
− ES
n
)
4
and observe that this is less
than Cn
2
for s ome constant C.
Solution. Write
S
n
−ES
n
=
b
S
n
=
n
X
k=1
b
ξ
k
,
where
b
ξ
k
= ξ
k
− Eξ
k
= ξ
k
− (p − q).
Notice that
E
b
ξ
k
= 0,
and repeat the computation of
b
S
4
n
as above but with
b
ξ
k
in place of ξ
k
:
b
S
4
n
=
b
ξ
4
1
+ ··· +
b
ξ
4
n
+
b
ξ
2
1
b
ξ
2
2
+ ··· +
b
ξ
2
n−1
b
ξ
2
n
+
b
ξ
3
1
b
ξ
2
+ ··· +
b
ξ
3
n−1
b
ξ
n
+
b
ξ
2
1
b
ξ
2
b
ξ
3
+ ··· +
b
ξ
2
n−2
b
ξ
n−1
b
ξ
n
+
b
ξ
1
b
ξ
2
b
ξ
3
b
ξ
4
+ ··· +
b
ξ
n−3
b
ξ
n−2
b
ξ
n−1
b
ξ
n
.
After taking expectation, we see that the expectation of each term in the last three
rows is zero. Hence
E
b
S
4
n
= nE
b
ξ
4
1
+ 3(n
2
− n)E
b
ξ
2
1
E
b
ξ
2
2
.
This is of the form c
1
n
2
+ c
2
n. And clearly this is less than Cn
2
where C = c
1
+ |c
2
|.
59
69.
For a simple symmetric random walk let T
′
0
be the time of first return to 0. Compute
P (T
′
0
= n) for n = 1, . . . , 6 first by applying the general formula and then by path
counting.
Solution. Obviously, P (T
′
0
= n) = 0 if n is odd. Recall the formula
P (T
′
0
= 2k) =
1/2
k
(−1)
k−1
, k ∈ N.
With k = 1, 2, 3, we have
P (T
′
0
= 2) =
1/2
1
=
1
2
P (T
′
0
= 4) = −
1/2
2
= −
(1/2)(1/2 −1)
2
=
1
8
P (T
′
0
= 6) =
1/2
3
= −
(1/2)(1/2 −1)(1/2 − 2)
6
=
3
16
P (T
′
0
= 8) = −
1/2
4
= −
(1/2)(1/2 −1)(1/2 − 2)(1/2 − 3)
24
=
5
128
.
To do path counting, we consider, e.g. th e last case. The possible paths contributing
to the event {T
′
0
= 8} are the ones in the figure below as well as th eir reflections:
Each path consists of 8 segments, so it has probability 2
−8
. There are 5 paths, so
P (T
′
0
= 8) = 10/2
8
= 5/128.
70.
Show that the formula P (M
n
≥ x) = P (|S
n
| ≥ x) −
1
2
P (|S
n
| = x) can also be derived
by summing up over y the formula P (M
n
< x, S
n
= y) = P(S
n
= y)−P (S
n
= 2x−y),
x > y.
Solution.
71.
How would you modify the formula we derived f or Es
T
a
for a simple random walk
starting from 0 in order to m ake it valid for all a, positive or negative? Here T
a
is the
first hitting time of a.
Solution. For a simple random walk S
n
= ξ
1
+ ··· + ξ
n
, with P (ξ
i
= +1) = p,
P (ξ
i
= −1) = q, we found
Es
T
1
=
1 −
p
1 − 4pqs
2
2qs
≡ ψ(p, s),
60
where T
1
is the first time that the RW hits 1 (starting fr om 0), and we use the notation
ψ(p, s) just to denote this function as a function of p and s. We argued that w hen
a > 0, the random variable T
a
is the s um of a i.i.d. copies of T
1
and so
Es
T
a
= ψ(p, s)
a
.
Let us now look at T
−1
. Since the distribution of T
−1
is the same as that of T
1
but
for a RW where the p and q are interchanged we have
Es
T
−1
= ψ(q, s).
Now, if −a < 0, the random variable T
−a
is the s um of a i.i.d. copies of T
−1
. Hence
Es
T
−a
= ψ(q, s)
a
.
72.
Consider a simple symmetric random walk starting from 0 and let T
a
be the first
time that state a will be visited. Find a formula for P (T
a
= n), n ∈ Z.
Solution. Let us consider the case a > 0, the other being similar. We have
Es
T
a
=
1 −
p
1 − 4pqs
2
2qs
!
a
,
whence
(2q)
a
E(s
a+T
a
) =
1 −
p
1 − 4pqs
2
a
.
We write power series for the right and left hand sides separately.
RHS =
a
X
r=0
a
r
−
p
1 − 4pqs
2
r
=
a
X
r=0
a
r
(−1)
r
∞
X
n=0
r/2
n
(−4pqs
2
)
n
=
∞
X
n=0
"
a
X
r=0
a
r
r/2
n
(−1)
n+r
(4pq)
n
#
s
2n
=
∞
X
n=0
"
a
X
r=1
a
r
r/2
n
(−1)
n+r
(4pq)
n
#
s
2n
LHS = (2q)
a
∞
X
m=0
P (T
a
= m)s
a+m
.
Equating powers of s in both sides, we see that we need a + m = 2n, i.e. m = 2n −a.
LHS = (2q)
a
X
n≥a
P (T
a
= 2n − a)s
2n
.
We conclude:
P (T
a
= 2n − a) =
1
(2q)
a
"
a
X
r=1
a
r
r/2
n
(−1)
n+r
(4pq)
n
#
, n ≥ a.
61
73.
Consider a simple symmetric random walk starting from 0 and let T
a
be the first
time that state a will be visited. Derive the formulæ for P (T
a
< ∞) in detail.
Solution. We have
P (T
a
< ∞) = lim
s↑1
Es
T
a
.
First consider the case a > 0. We have that, for all values of p,
Es
T
a
= (Es
T
1
)
a
=
1 −
p
1 − 4pqs
2
2qs
!
a
, |s| < 1.
So
P (T
a
< ∞) = lim
s↑1
1 −
p
1 − 4pqs
2
2qs
!
a
=
1 −
√
1 − 4pq
2q
a
=
1 − |p − q|
2q
a
.
If p ≥ q then |p − q| = p − q and simple algebra gives P (T
a
< ∞) = 1. If p < q then
|p − q| = q − p and simple algebra gives P (T
a
< ∞) = (q/p)
a
. Next consider the case
a < 0. By interchanging the roles of p and q we have
P (T
a
< ∞) =
1 − |q −p|
2p
a
.
If p ≥ q then |q − p| = p − q and simple algebra gives P (T
a
< ∞) = (p/q)
a
. I f p > q
then |q − p| = q − p and simp le algebra gives P (T
a
< ∞) = 1.
74.
Show that for a symm etric simple random walk any state is visited infinitely many
times with probability 1.
Solution.
75.
Derive the expectation of the running maximum M
n
for a SSRW starting from 0:
EM
n
= E|S
n
| +
n
n/2
2
−n−1
−
1
2
.
Conclude that EM
n
/E|S
n
| → 1, as n → ∞.
Solution. This follows from the formula
P (M
n
≥ x) = P (|S
n
| ≥ x) −
1
2
P (|S
n
| = x).
We have EM
n
=
P
∞
x=1
P (M
n
≥ x), E|S
n
| =
P
∞
x=1
P (|S
n
| ≥ x), so:
EM
n
= E|S
n
| −
1
2
∞
X
x=1
P (|S
n
| = x).
The last sum equals 1 − P (S
n
= 0) = 1 −
n
n/2
2
−n
.
62
76.
Using the ballot theorem, show that, for a SSRW starting from 0,
P (S
1
> 0, . . . , S
n
> 0) =
ES
+
n
n
,
where S
+
n
= max(S
n
, 0).
Solution. The ballot theorem says
P (S
1
> 0, . . . , S
n
> 0 | S
n
= x) = x/n, x > 0.
Hence
P (S
1
> 0, . . . , S
n
> 0) =
∞
X
x=1
P (S
1
> 0, . . . , S
n
> 0 | S
n
= x)P (S
n
= x)
=
∞
X
x=1
x
n
P (S
n
= x) =
1
n
ES
+
n
.
77.
For a simple random walk with p < q show that EM
∞
=
p
q−p
.
Solution. We have
EM
∞
=
∞
X
x=1
P (M
∞
≥ x) =
∞
X
x=1
P (T
x
< ∞) =
∞
X
x=1
(p/q)
x
=
p/q
1 − (p/q)
=
p
q −p
.
78.
Consider a SSRW, starting f rom some positive integer x, and let T
0
be the first n such
that S
n
= 0. Let M = max{S
n
: 0 ≤ n ≤ T
0
}. Show that M has th e same distribution
as the integer part of (i.e. the largest integer not exceeding) x/U, wh ere U is a uniform
random variable between 0 and 1.
Solution. Let T
a
be the first time that the random walk reaches level a ≥ x. Then
P (M ≥ a) = P (T
a
< T
0
) = x/a.
On the other hand, if [y] denotes the largest integer not exceeding the real number y,
we have, for all a ≥ x,
P ([x/U] ≥ a) = P (x/U ≥ a) = P (U ≤ x/a) = x/a.
Hence P ([x/U] ≥ a) = P (M ≥ a), for all x ≥ a (while both probabilities are 1 for
x < a). Hence M has the same distribution as [x/U].
79.
Show that (X
n
, n ∈ Z
+
) is Markov if and only if for all intervals I = [M, N] ⊆ Z
+
(X
n
, n ∈ I) (the process inside) is independent of (X
n
, n 6∈ I) (the process outside),
conditional on th e pair (X
M
, X
N
) (the process on the boundary).
63
80.
A deck of cards has 3 Red and 3 Blue cards. At each stage, a card is selected at
random. If it is Red, it is removed from the deck. If it is Blue then the card is not
removed and we move to the next stage. Find the average number of steps till the
process ends.
Solution. T he problem can be solved by writing fi rst step equations for the Markov
chain representing the number of red cards remaining: The transition probabilities
are:
p(3, 2) = 3/6, p(2, 1) = 2/5, p(1, 0) = 1/4,
p(i, i) = 1 − p(i, i − 1), i = 3, 2, 1, p(0, 0) = 1.
Let ψ(i) be the average number of steps till the process ends if the initial state is i.
Then
ψ(3) = 1 + (3/6)ψ(3) + (3/6)ψ(2),
ψ(2) = 1 + (3/5)ψ(2) + (2/5)ψ(1),
ψ(1) = 1 + (3/4)ψ(1).
Alternatively, observe that, to go from state i to i − 1, we basically toss a coin with
probability of success equal to p(i, i − 1). Hence the expected number of tosses till
success is 1/p(i, i − 1). Adding these up we have the answer:
ψ(3) = (6/3) + (5/2) + (2/1).
81.
There are two decks of cards. Deck 1 contains 50 Red cards, 30 Blue cards, and 20
Jokers. Deck 2 contains 10, 80, 10, respectively. At each stage we select a card fr om a
deck. If we select a Red card then, we select a card of the other deck at the next stage.
If we select a Blue card then we select a card from the same deck at the next stage.
If, at any stage, a Joker is selected, then the game ends. Cards are always replaced in
the decks. Set up a Markov chain and find , if we first pick up a card at random from
a deck at random, how many steps it takes on the average for the game to end.
Solution. The obvious Markov chain has three states: 1 (you take a card from Deck
1), 2 (you take a card from Deck 2), and J (you selected a Joker). We have:
p(1, 2) = 30/100, p(1, J) = 20/100,
p(2, 1) = 80/100, p(2, J) = 10/100,
p(J, J) = 1.
Let ψ(i) be the average number of steps for th e game to end. when we start from deck
i Then
ψ(1) = 1 + (50/100)ψ(1) + (30/100)ψ(2),
ψ(2) = 1 + (10/100)ψ(2) + (80/100)ψ(1).
Solve for ψ(1), ψ(2). Since the initial deck is selected at random, the answer is (ψ(1)+
ψ(1))/2.
64
82.
Give an example of a Markov chain with a small number of states that
(i) is irreducible
(ii) has exactly two communication classes
(iii) has exactly two inessential and two essential states
(iv) is irreducible and aperiodic
(v) is irreducible and has period 3
(vi) has exactly one stationary distribution but is not irreducible
(vii) has more than one stationary distributions
(viii) has one state with period 3, one with period 2 and one with period 1, as well as
a number of other states
(ix) is irreducible and detailed balance equations are satisfied
(x) has one absorbing state, one inessential state and two other states which form a
closed class
(xi) has exactly 2 transient and 2 recurrent states
(xii) has exactly 3 states, all recurrent, and exactly 2 communication classes
(xiii) has exactly 3 states and 3 communication classes
(xiv) has 3 states, one of which is visited at most finitely many times and the other
two are visited infinitely many times, with probability one
(xv) its stationary distribution is unique and uniform
83.
Give an example of a Markov chain with infinitely many states that
(i) is irreducible and positive recurrent
(ii) is ir reducible and null recurrent
(iii) is irreducible and transient
(iv) forms a random walk
(v) has an infinite number of inessential states and an infinite numb er of essential
states which are all positive recurrent
84.
A drunkard starts from the pub (site 0) and moves one step to the right with probability
1. If, at some stage, he is at site k he moves one step to the right with probability
p
k
, on e s tep to the left with p robability q
k
, or stays where he is with the remaining
probability. Suppose p + q = 1, 0 < p < q. Show that the drun kard will visit 0
infinitely many times with probability 1.
Solution. Write down balance equations for the stationary distribution. Observe
that, since
P
∞
k=1
(p/q)
k(k−1)/2
< ∞, we have that π(k) > 0 for all k. Hence, not only
0 w ill be visited infinitely many times, but also the expected time, starting from 0, till
the first r eturn to 0 is 1/π(0) < ∞.
85.
A Markov chain takes values 1, 2, 3, 4, 5. From i it can move to any j > i w ith equal
probability. State 5 is absorbing. Starting from 1, how many steps in the average will
it take till it reaches 5?
Solution. 2.08
86.
There are N individuals, some infected by a disease (say the disease of curiosity) and
65
some not. At each stage, exactly one uninfected individual is placed in contact with
the infected ones. An infected individual infects with probability p. So an uninf ected
individual becomes infected if he or she gets infected by at least one of the infected
individuals. Assume that, to start with, there is only one infected person. Build a
Markov chain with states 1, 2, . . . , N and argue that p(k, k + 1) = 1 − (1 − p)
k
. Show
that, on the average, it will take N +q(1−q
N
)/(1−q) for everyone to become infected.
Solution. When there are k inf ected individuals an d one uninfected is brought in
contact with them, the chance that the latter is not infected is (1 − p)
k
. So
p(k, k) = (1 − p)
k
, p(k, k + 1) = 1 − (1 − p)
k
, , k = 1, . . . , N − 1.
Of course, p(N, N) = 1. The average numb er of steps to go from k to k + 1 is
1/p(k, k + 1). Hence, starting with 1 infected individual it takes
N−1
X
k=1
1
1 − (1 − p)
k
for everyone to become infected.
87.
Assume, in addition, that exactly one infected individual is selected for treatment
and he or she becomes well with p robability α > 0, and this occurs independently of
everything else. (i) What is the s tate space and the transition probabilities? (ii) How
many absorbing states are there? (iii) What kind of question would you like to ask
here and how would you answer it?
Solution. (i) Since p(1, 0) is equal to α which is positive, we now need to include 0
among the states. So the state space is
S = {0, 1, 2, . . . , N}.
The transition probabilities now become
p(k, k − 1) = αq
k
, p(k, k) = (1 − α)q
k
, p(k, k + 1) = (1 − α)(1 − q
k
), k = 1, . . . N − 1
p(N, N − 1) = αq
N
, p(N, N ) = 1 − αq
N
, p(0, 0) = 1.
where q = 1 −p. (ii) There is only one absorbing state: the state 0. (iii) The question
here is: How long will it take for the chain to be absorbed at 0? Letting g(k) be the
mean time to absorption starting from k, we have
g(k) = 1 + (1 − αq
k
)g(k) + αq
k
g(k −1) + (1 − α)(1 − q
k
)g(k + 1), 1 ≤ k ≤ N
g(N) = 1 + (1 − αq
N
)g(N) + αq
N
g(N − 1),
g(0) = 0.
There is a unique solution.
88.
Prove that for an irreducible Markov chain with N states it is possible to go from any
state to any other state in at most N − 1 steps.
Solution. For any two distinct states i, j there is a path that takes you fr om i to j.
Cut out any loops from this path and you still have a path that takes you from i to j.
But this p ath has distinct states and distinct arrows. There are at most N − 1 such
arrows.
66
89.
Consider the general 2-state chain, where p(1, 2) = a, p(2, 1) = b. Give necessary and
sufficient conditions for the chain (i) to be aperiodic, (ii) to possess an absorbing state,
(iii) to have at least one stationary distribution, (iv) to have exactly one stationary
distribution.
Solution. (i) T here mus t be at least one self-loop. The condition is:
a < 1 or b < 1.
(ii)
a = 0 or b = 0.
(iii) It always does because it has a finite number of states.
(iv) There must exist exactly one communication class:
a > 0 or b > 0.
90.
Show th at the stationary distribution on any (undirected) graph whose vertices have
all the same degree is uniform.
Solution. We know th at
π(i) = cd(i),
where d(i) is the degree of i, an d c some constant. Indeed, the detailed balance
equations
π(i)p(i, j) = π(j)p(j, i), i 6= j
are trivially satisfied because p(i, j) = 1/d(i), p(j, i) = 1/d(i), by definition.
So when d(i) = d = constant, the distribution π is uniform.
91.
Consider the random walk on the graph
1 —– 2 —– 3 —– 4 —– ··· —– N-1 —– N
(i) Find its stationary distribution. (ii) Find the average number of steps to return to
state 2, starting from 2. (iii) Repeat for 1. (iv) Find the average number of steps f or
it to go from i to N. (v) Find the average number of steps to go from i to either 1 or
N. (vi) Find the average number of steps it takes to visit all states at least once.
Solution. Hint for (vi): The time to visit all states at least once is the time to hit
the boundary plus the time to hit the other end of the boundary.
92.
When a bus arrives at the HW campus, the next bus arrives in 1, 2, . . . , 20 minutes
with equal probability. You arrive at the bus stop without checking the schedule, at
some fixed time. How long, on the average, should you wait till the next bus arrives?
What is the standard deviation of this time?
Solution. This is based on one of the examples we discussed: Let X
n
be the time
elapsed from time n till the arrival of the next bus. Then X
n
is a Markov chain with
transition probabilities
p(k, k − 1) = 1, k > 0,
p(0, k) = p
k
, k > 0,
67
where p
k
= (1/20)1(1 ≤ k ≤ 20). We find that the stationary distribution is
π(k) = c
X
j≥k
p
k
= c
20
X
j=k
1
20
=
c(21 − k)
20
, 0 ≤ k ≤ 20.
where c a constant determined by normalisation:
1 =
20
X
k=0
π(k) =
c
20
20
X
k=0
(21 − k) =
c
20
21 ×22
2
, c =
20
231
.
Hence
π(k) =
21 −k
231
, 0 ≤ k ≤ 20,
and so the average waiting time is
20
X
k=0
kπ(k) =
20
X
k=0
k
21 − k
231
= 20/3 = 6
′
40
′′
The standard deviation is
v
u
u
t
20
X
k=0
k
2
π(k) − (20/3)
2
=
√
230/3 ≈ 5
′
3
′′
Note: To do the sums without too much work, use the f ormulae
n
X
k=1
k =
n(n + 1)
2
,
n
X
k=1
k
2
=
n(n + 1)(2n + 1)
6
,
n
X
k=1
k
3
=
n(n + 1)
2
2
.
93.
Build a Markov chain as follows: When in state k (k = 1, 2, 3, 4, 5, 6), roll a die k times,
take the largest value and move to th at state. (i) Comp ute the transition probabilities
and write d own the transition probability matrix. (ii) Is the chain aperiodic? (iii)
Do es it have a unique stationary distribution? (iv) Can you find which state will be
visited more frequently on the average?
Solution. (i) Let M
k
be the m aximum of k independent rolls. Then
P (M
k
≤ ℓ) = (ℓ/6)
k
, k, ℓ = 1, . . . , 6.
The transition probability from state k to state ℓ is
p(k, ℓ) = P (M
k
= ℓ) = (ℓ/6)
k
− ((ℓ − 1)/6)
k
, k, ℓ = 1, . . . , 6.
68
The transition probability matrix is
1/6 1/6 1/6 1/6 1/6 1/6
1/36 3/36 5/36 7/36 9/36 11/36
1/216 7/216 19/216 37/216 61/216 91/216
1/1296 15/1296 65/1296 175/1296 369/1296 671/1296
1/7776 31/7776 211/7776 781/7776 2101/7776 4651/7776
1/46656 63/46656 665/46656 3367/46656 11529/46656 31031/46656
≈
0.167 0.167 0.167 0.167 0.167 0.167
0.0278 0.0833 0.139 0.194 0.250 0.306
0.00463 0.0324 0.0880 0.171 0.282 0.421
0.000772 0.0116 0.0502 0.135 0.285 0.518
0.000129 0.00399 0.0271 0.100 0.270 0.598
0.0000214 0.00135 0.0143 0.0722 0.247 0.665
(ii) The chain is obviously aperiodic because it has at least one self-loop.
(iii) Yes it does because it is finite and irreducible.
(iv) Intuitively, this sh ould be state 6.
94.
Simple queueing system: Someone arrives at a bank at time n with probability α. He
or she waits in a queue (if any) which is served by one bank clerk in a FCFS fashion.
When at the head of the queue, the person requires a service which is distributed like
a random variable S with values in N: P (S = k) = p
k
, k = 1, 2, . . .. Different people
require services which are independent random variables. Consider the quantity W
n
which is the total waiting time at time n: if I take a look at the queue at time n then
W
n
represents the time I have to wait in line till I finish my service. (i) Show that W
n
obeys the recursion
W
n+1
= (W
n
+ S
n
ξ
n
− 1)
+
,
where the S
n
are i.i.d. random variables distributed like S, independent of the ξ
n
. The
latter are also i.i.d. with P (ξ
n
= 1) = α, P (ξ
n
= 0) = 1 − α. Thus ξ
n
= 1 indicates
that there is an arrival at time n. (ii) Show that W
n
is a Markov chain and compute
its tr ansition p robabilities p(k, ℓ), k, ℓ = 0, 1, 2, . . ., in terms of the parameters α and
p
k
. (iii) Sup pose that p
1
= 1 − β, p
2
= β. Find conditions on α and β so that the
stationary distribution exists. (iv) Give a physical interpretation of this condition. (v)
Find the stationary distribution. (vi) Find the average waiting time in steady-state.
(vii) If α = 4/5 (4 cu s tomers arrive every 5 units of time on the average–heavy traffic),
what is the maximum value of β so that a stationary distribution exists? What is the
average waiting time when β = 0.24?
Solution. (i) If, at time n the waiting time W
n
is nonzero and nobody arrives then
W
n+1
= W
n
− 1, because, in 1 unit of time the waiting time d ecreases by 1 unit.
If, at time n, somebody arrives and has service time S
n
then, immediately the wait-
ing time becomes W
n
+ S
n
and so, in 1 unit of time this decreases by 1 so that
W
n+1
= W
n
+ S
n
− 1. Putting things together we arrive at the announced equation.
Notice that the superscript + means maximum with 0, because, if W
n
= 0 and nobody
arrives, then W
n+1
= W
n
= 0.
69
(ii) That the W
n
form a Markov chain with values in Z
+
follows from th e previ-
ous exercise. To find the transition probabilities we argue as follows : Let p(k, ℓ) =
P (W
n+1
= ℓ | W
n
= k). First, observe that, for a given k, the ℓ cannot be less than
k − 1. In fact, p(k, k − 1) = 1 − α (the probability that nobod y arrives). Next, for
ℓ to be equal to k we need that somebody arrives and brings work equal to 1 unit:
p(k, k) = αp
1
. Finally, for general ℓ > k we need to have an arrival which brings work
equal to ℓ − k + 1: p(k, ℓ) = αp
ℓ−k+1
.
(iii) Here we have
p(k, k − 1) = 1 − α, p(k, k + 1) = αβ, p(k, k) = α(1 − β).
To compute the stationary distribution we write balance equations:
π(k)(1 − α) = π(k − 1)αβ, k ≥ 0.
Iterating this we get
π(k) =
αβ
1 − α
k
π(0).
We need to be able to normalise:
∞
X
k=0
αβ
1 − α
k
π(0) = 1.
We can do this if and only if the geometric series converges. This happens if and only
if
αβ
1 − α
< 1,
(iv) The condition can also be written as
1 + β < 1/α.
The left side is the average service time (1 × (1 − β) + 2 × β). Th e right side is the
average time between two successive arrivals. So the condition reads:
Average service time < average time between two successive arrivals.
(v) From the normalisation condition, π(0) = (1 − α(1 + β))/(1 − α). This follows
because
∞
X
k=0
αβ
1 − α
k
=
1
1 −
αβ
1−α
=
1 − α
1 − α(1 + β)
.
Hence
π(k) =
1 − α(1 + β)
1 − α
αβ
1 − α
k
, k ≥ 0.
This is of the form π(0) = (1 − ρ)ρ
k
, where ρ = αβ/(1 − α), hence a geometric
distribution.
(vi) The average waiting time in steady-state is
∞
X
k=0
kπ(k) =
∞
X
k=0
kρ
k
(1 − ρ) =
ρ
1 − ρ
=
αβ
1 − α(1 + β)
.
(vii) If α = 4/5 then β < (5/4) − 1 = 1/4. So the service time must be such that
P (S = 2) = β < 1/4, and P (S = 1) = 1 − β > 3/4. When β = 0.24 we are OK s ince
0.2 < 0.25. In th is case, the average waiting time is equal to 24, which is quite large
compared to the maximum value of S.
70
95.
Let S
n
be a simple symmetric random walk with S
0
= 0. Show that |S
n
| is Markov.
Solution. If we know the value of S
n
, we know two things: its absolute value |S
n
|
and its sign. But to determine the value of |S
n+1
|, knowledge of the sign is irrelevant,
since, by symmetry |S
n+1
| = |S
n
|±1 with probability 1/2 if S
n
6= 0, while |S
n+1
| = 1
is S
n
= 0. Hence P (|S
n+1
| = j | S
n
= i) depends only on |i|: if |i| > 0 it is 1/2 for
j = i ± 1, and if |i| = 0 it is 1 for j = 1.
96.
Let S
n
be a simple but not symmetric r an dom walk. Show that |S
n
| is not Markov.
Solution. In contrast to the above, P (|S
n+1
| = j | S
n
= i) is not a function of |i|.
97.
Consider a modification of a simple sym metric random walk that takes 1 or 2 steps
up with probability 1/4 or a step down with probability 1/2. Let Z
n
be the position
at time n. Show that P (Z
n
→ ∞) = 1.
Solution. From the Strong Law of Large Numbers, Z
n
/n converges, as n → ∞, with
probability 1, to the expected value of the step:
(−1) × 0.5 + (+1) × 0.25 + (+2) × 0.25 = 0.25.
Since this a positive number it follows that Z
n
must converge to infinity with proba-
bility 1.
98.
There are N coloured items. There are c possible colours. Pick an items at r andom
and change its colour to one of the other c − 1 colours at random. Keep doing this.
What is the Markov chain describing this experiment? Find its stationary distribution.
(Hint: When c = 2 it is the Ehrenfest chain.)
Solution. The Markov chain has states
x = (x
1
, . . . , x
c
),
where x
i
is the number of items having colour i. Of course, x
1
+ ··· + x
c
= N . If we
let e
i
be the vector with 1 in the i-th position and 0 everywh ere else, then we see that
from state x only a transition to a state of th e form x − e
i
+ e
j
is possible if x
i
> 0.
The transition probability is
p(x, x − e
i
+ e
j
) =
x
i
N
1
c − 1
,
because x
i
/N is the probability that you pick an item with colour i, and 1/(c − 1) is
the probability that its new colour will be j. To find the stationary distribu tion π(x)
we just try to see if detailed balance equations hold. If they do then we are happy and
know that we have found it. If they don’t, well, we don’t give up and try to see how
to s atisfy the (full) balance equations. Recall:
• Full balance equations: π(x) =
P
y
π(y)p(y, x), for all x.
If the chain is finite (and here it is), we can always find a probability distribution π
that satisfies the full balance equations.
• Detailed balance equations: π(x)p(x, y) = π(y)p(y, x), for all x, y.
71
Even if the chain is finite, it is NOT always the case that detailed balance hold. If
they do, then we should feel lucky!
Since, for c = 2 (the Ehrenfest chain) the stationary distribution is the binomial
distribution, we may GUESS th at the stationary distribution here is multinomial:
GUESS: π(x) = π(x
1
, . . . , x
c
) =
N
x
1
, . . . , x
c
c
−N
=
N!
x
1
! ···x
c
!
c
−N
.
Now
CHECK WHETHER: π(x)p(x, y) = π(y)p(y, x) HOLD FOR ALl x, y.
If y, x are not related by y = x − e
i
+ e
j
for some distinct colours i, j, then p(x, y) =
p(y, x) = 0, and so the equations hold trivially. Suppose then that y = x − e
i
+ e
j
for some distinct colours i, j, then p(x, y) = p(y, x) = 0, and so the equations hold
trivially. Suppose then that y = x − e
i
+ e
j
for s ome distinct colours i, j. We have
π(x)p(x, x −e
i
+ e
j
) =
N!c
−N
x
1
! ···x
i
! ···x
j
! ···x
c
!
x
i
N
1
c − 1
and
π(x, x − e
i
+ e
j
)p(x − e
i
+ e
j
, x) =
N!c
−N
x
1
! ···(x
i
− 1)! ···(x
j
+ 1)! ···x
c
!
x
j
+ 1
N
1
c − 1
The two qu antities are obviously the same. Hence detailed balance equations are
satisfied. Hence the multinomial distrib ution IS THE stationary distribution.
99.
In the previous problem: If there are 9 balls and 3 colours (Red, Green, Blue) and we
initially s tart with 3 balls of each colour, how long will it take on the average till we
see again the same configu ration? (Suppose th at 1 step = 1 minute.) If we start we
all balls coloured Red, how long will it take on the average till we see the same again?
Solution.
π(3, 3, 3) =
9!
3!3!3!
3
−9
= 560/6561.
Hence the average number of steps between two successive occurrences of the state
(3, 3, 3) is 6561/560 ≈ 11.72 minutes. Next,
π(9, 0, 0) =
9!
9!0!0!
3
−9
= 1/19683.
Hence the average number of steps between two successive occurrences of the state
(9, 0, 0) is 19683 minutes = 328.05 hours ≈ 13 and a half days.
100.
Consider a rand om walk on a star-graph that has one centre vertex 0 and N legs
emanating from 0. Leg i contains ℓ
i
vertices (in addition to 0) labelled
v
i,1
, v
i,2
, . . . , v
i,ℓ
i
.
The vertices are in sequence: 0 is connected to v
i,1
which is connected to v
i,2
, etc. till
the end vertex v
i,ℓ
i
. (i) A particle starts at 0. Find the probability that it reaches the
72
1,1
v
2,1
v
3,1
v
2,2
v
3,2
v
5,2
v
5,1
v
1,2
v
0
4,1
v
end of leg i before reaching the end of any other leg. (ii) Suppose N = 3, ℓ
1
= 2, ℓ
2
=
3, ℓ
3
= 100. Play a game as follows: start from 0. If end of leg i is reached you win ℓ
i
pounds. Find how much money you are willing to pay to participate in this game.
Solution. Let ϕ
i
(x) be the probability that end of leg i is reached before reaching
the end of any other leg. Clearly,
ϕ
i
(v
i,ℓ
i
) = 1, ϕ
i
(v
k,ℓ
k
) = 0, k 6= i.
Now, if v
i,r
is an interior vertex of leg i (i.e. neither 0 nor the end vertex), then
ϕ
i
(v
k,r
) =
1
2
ϕ
i
(v
k,r−1
) +
1
2
ϕ
i
(v
k,r+1
).
This means that th e function
r 7→ ϕ
i
(v
k,r
)
must be linear for each k (for the same r eason that the probability of hitting the left
boundary of an interval before hitting the right one is linear for a simple symm etric
random walk). Hence
ϕ
i
(v
k,r
) = a
i,k
r + b
i,k
,
where a
i,k
, b
i,k
are constants. For any leg we determine the constants in terms of the
values of ϕ
i
at the centre 0 and the end vertex. Thus,
ϕ
i
(v
k,r
) =
ϕ
i
(0)
ℓ
k
(ℓ
k
− r), k 6= i,
ϕ
i
(v
i,r
) =
r
ℓ
i
+
ϕ
i
(0)
ℓ
i
(ℓ
i
−r).
Now, for vertex 0 we have
ϕ
i
(0) =
1
N
N
X
k=1
ϕ
i
(v
k,1
) =
1
N
1
ℓ
i
+
ϕ
i
(0)
ℓ
i
(ℓ
i
− 1) +
X
k6=i
ϕ
i
(0)
ℓ
k
(ℓ
k
− 1)
=
1
N
1
ℓ
i
+ ϕ
i
(0)
1
N
N
X
k=1
1 −
1
ℓ
k
whence
ϕ
i
(0) =
1
ℓ
i
P
N
k=1
1
ℓ
k
.
73
(ii)
ϕ
3
(0) =
1/600
1/2 + 1/3 + 1/600
, ϕ
2
(0) =
1/3
1/2 + 1/3 + 1/600
, ϕ
1
(0) =
1/2
1/2 + 1/3 + 1/600
.
The average winnings are:
600ϕ
3
(0) + 3ϕ
2
(0) + 2ϕ
1
(0) ≈ 1.2 pounds.
74
