Solution-Assignment 1 (for Stat3021)
1. Assume Xn are independent and identically distributed with P (X1 = 1) = p,
P (X1 = 0) = r and P (X1 = −1) = q. where p, r, q > 0 and p + r + q = 1.
Let Sn =
∑n
i=1Xi, n = 1, 2, . . ..
(a) Prove that {S1, S2, . . .} is an irreducible Markov chain with state space S =
{0,±1,±2, ...} and write down its transition matrix.
(b) Is the chain aperiodic?
(c) Find expressions for:
i. P (S3 = 2).
ii. P (S4 = 1|S1 = 1).
iii. P (S10 = 1|S7 = 0).
iv. ESn and var(Sn).
Solution:
(a) It’s a MC since Sn+1 = Sn + Xn+1 so that conditional on S1, S2, . . . , Sn, or
equivalently X1, X2, . . . , Xn, it is only Sn that is relevant for predicting the
value of Sn+1. It’s clear that all states communicate, since any state j can be
reached from any other state i, in |j − i| steps, with positive probability. The
transition matrix is (with r’s on diagonal)
P =

...
...
...
...
...
...
...
. . . q r p . . . . . . . . .
. . . . . . q r p . . . . . .
. . . . . . . . . q r p . . .
...
...
...
...
...
...
...

(b) Yes, it’s aperiodic, since e.g. pn00 ≥ rn > 0 for n = 1, 2, . . ..
(c) i. {S3 = 2} involves two +1’s and one 0 so the answer is 3p2r.
ii. P (S4 = 1|S1 = 1) = P (S3 = 0). This involves three 0’s or one each of 0,
−1 and +1, so the answer is r3 + 6pqr.
iii. This is the same as P (S3 = 1) which entails two 0’s and a +1 or two +1’s
and a −1. So the answer is 3r2p+ 3p2q.
iv. ESn = n(p− q) and var(Sn) = n(4pq + r(p+ q)).
2. Suppose a transition diagram is given as follows:
1 2
5
3
4 6 7
1/2
1/2
1/2
1/4
1/4
For this chain, there are two recurrent classes R1 = {6, 7} and R2 = {1, 2, 5}, and
one transient class R3 = {3, 4}.
(a) Find the period of state 3 and the probability that, starting at state 3, the
state 3 is eventually re-entered (i.e., f33).
(b) Assuming X0 = 3, find the probability that the chain gets absorbed in R1.
(c) Assuming X0 = 3, find the expected time (number of steps) until the chain
gets absorbed in R1 or R2. More specifically, let T be the absorption time,
i.e., the first time the chain visits a state in R1 or R2. We would like to find
E[T |X0 = 3].
Note: there are missing transition probabilities for this chain, but no impact for
your solution.
Solution:
(a) Note that
p
(2k)
33 = (0.5× 0.4)k > 0, p(2k+1)33 = 0, k = 1, 2, ...
The period of state 3 is 2. Similarly, we have
f
(1)
33 = 0, f
(2)
33 = 1/2× 1/4 = 1/8, f (k)33 = 0, k ≥ 3
It follows that f33 =
∑∞
n=1 f
(n)
33 = 1/8.
(b) We can apply the standard methodology to find probability of absorption in
state R1. Define
ai = P (absorption in R1|X0 = i), for all i ∈ S.
We have aR1 = 1, and aR2 = 0. To find the unknown values of ai’s, we can use
the following equations
ai =
∑
k
akpik, for i ∈ S.
2
We obtain
a3 =
1
2
aR1 +
1
2
a4
=
1
2
+
1
2
a4,
a4 =
1
4
aR1 +
1
4
a3 +
1
2
aR2
=
1
4
+
1
4
a3.
Solving the above equations, we obtain
a3 =
5
7
, a4 =
3
7
.
Therefore, if X0 = 3, the chain will end up in class R1 with probability a3 =
5
7
.
(c) For all i ∈ S, define
ti = E[T |X0 = i].
By the above definition, we have tR1 = tR2 = 0. To find t3 and t4, we can use
the following equations
ti = 1 +
∑
k
tkpik, for i = 3, 4.
Specifically, we obtain
t3 = 1 +
1
2
tR1 +
1
2
t4
= 1 +
1
2
t4,
t4 = 1 +
1
4
tR1 +
1
4
t3 +
1
2
tR2
= 1 +
1
4
t3.
Solving the above equations, we obtain
t3 =
12
7
, t4 =
10
7
.
Therefore, if X0 = 3, it will take on average
12
7
steps until the chain gets
absorbed in R1 or R2.
3
3. An apparatus consists of two containers C1 and C2, and four balls, in one or the
other of the two containers. At regular times the following procedure is carried out:
with probability θ a ball is chosen uniformly at random (from all four balls) and
is removed from its container and placed in the other one; with probability 1 − θ
things are left as they were. Let Xn denote the number of balls in container C1 at
time n.
(a) Explain why Xn forms a Markov chain with stationary transition probabilities.
(b) Complete the following transition matrix P
P =

1− θ θ ∗ ∗ ∗
θ/4 1− θ 3θ/4 ∗ ∗
0 θ/2 ∗ ∗ ∗
∗ ∗ ∗ 1− θ θ/4
∗ ∗ ∗ ∗ 1− θ

(c) Classify the states, taking care to distinguish the cases θ = 0, 0 < θ < 1 and
θ = 1.
Draw a transition diagram to aid your explanation.
(d) Suppose 0 < θ < 1. Calculate the stationary distribution pi = (pi0, · · · , pi4).
Explain briefly why the distribution is the same for all θ ∈ (0, 1).
(e) Suppose 0 < θ < 1. What is the limit of P n, where P is the transition matrix
given in part (b)? Explain.
(f) Let mj be the expected time to reach state 4, given X0 = j, for j = 0, 1, 2, 3.
Calculate mj when θ = 0
Solution:
(a) Given the values of {X0 = i0, X1 = i1, ..., Xn = in}, Xn+1 can only take the
three possible values in and in ± 1. Thus
P (Xn+1 = j | X0 = i0, X1 = i1, ..., Xn = in) = P (Xn+1 = j | Xn = in),
i.e., it’s a Markov Chain. Furthermore the transition probabilities donot de-
pend on n, so it has stationary transition probabilities.
(b)
P =

1− θ θ 0
θ/4 1− θ 3θ/4 0
0 θ/2 1− θ θ/2 0
0 3θ/4 1− θ θ/4
0 θ 1− θ

(c) θ = 0: Each state is absorbing (and therefore aperiodic and positive recurrent).
θ ∈ (0, 1): State form a single class, aperiodic and positive recurrent.
θ = 1: states form a single class, period 2.
4
(d) The stationary dist. satisfies that pi = pi P , i.e.,
pi0 = (1− θ)pi0 + θpi1/4
pi1 = θpi0 + (1− θ)pi1 + θpi2/2
pi2 = 3θpi1/4 + (1− θ)pi2 + 3θpi3/4
pi3 = θpi2/2 + (1− θ)pi3 + θpi4/2
pi4 = θpi3/4 + (1− θ)pi4
This yields that
pi1 = 4pi0
pi2 = 2(pi1 − pi0) = 6pi0
pi3 =
4
3
(pi2 − 3
4
pi1) = 4pi0
pi4 =
1
4
pi3 = pi0
and it follows from
∑4
j=0 pii = 1 that pi0 = 1/16, i.e., the stationary dist.
pi0 = 1/16, pi1 = 1/4, pi2 = 3/8, pi3 = 1/4, pi4 = 1/16.
Note that the stationary dist. is Binomial B(4, 1/2).
θ affects the rate of change from state to state but not the limit distribution.
(e) The limit of P n =
pipi
pi
 where each row is the stationary dist since it is an
irreducible, aperiodic and positive recurrent MC.
(f) θ = 0: Each state is absorbing (and therefore aperiodic and positive recurrent).
Therefore, mj =∞, given X0 = j, for j = 0, 1, 2, 3.
5







































































































































































































































































学霸联盟