MATH 303 Practice Problems Solutions - Week 2 Jamuary 22, 2021
Problem 1
1.
P =

1
2
1
2 0 0 0 0
1
2
1
2 0 0 0 0
0 0 12 0
1
2 0
1
4
1
4 0 0
1
4
1
4
0 0 12 0
1
2 0
0 13 0
1
3
1
3 0

2. The transition diagram may be represented as:
1
2
3
4
5
6
1/2
1/2 1/2
1/2
1/2 1/2
1/4
1/4
1/4
1/4
1/2
1/2
1/3
1/3
1/3
There are three communicating classes:
• C1 = {1, 2} (P12 > 0 and P21 > 0 so 1↔ 2, and 1 and 2 do not give access to other states).
• C2 = {3, 5} (by the same argument as above).
• C3 = {4, 6} (4↔ 6 and they do not communicate with any other classes).
3. Since periodicity, transience and recurrence are class properties, we can consider each class to
study the properties of all the states they contain.
States in:
• C1 are aperiodic (since p
(1)
11 > 0 for example).
• C2 are aperiodic (same as above).
• C3 are of period 2 (starting from any state it takes an even number of steps to revisit the
state)
States in:
• C1 and C2 are recurrent (since the class is closed and finite)
• C3 are transient (for example 4→ 2 and 2 6→ 4).
Problem 2
1. 
r p 0 0 0 q
q r p 0 0 0
0 q r p 0 0
0 0 q r p 0
0 0 0 q r p
p 0 0 0 q r

2. For all states i, j, i↔ j since one can move from any vertex to any other by successively moving
in one direction. So the chain has only one communicating class and it is irreducible.
3. If r > 0, then p11 = r > 0, so the period divides 1, so it is equal to 1 and the chain is aperiodic.
4. If N is even, then there exists a proper 2-coloring of the N -gon: the states can be colored
red or blue such that Pij > 0 if and only if i and j have different colors. Suppose state
1 is colored blue, and consider any path 1 → 1 of length n, say (X0 = 1, X1 = x1, X2 =
x2, . . . , Xn−1 = xn−1, Xn = 1), that has positive probability to occur. Since xj and xj−1 have
different colors for j = 1, 2, . . . , n, and Xn = 1 is blue, there are exactly
n
2 blue states in the
sequence (x0, x1, . . . , xn−1), namely x0, x2, . . . , xn−2. Thus n2 is an integer, so n must be even,
and Pn11 = 0 if n is odd. Finally, p
2
11 > p
1
12p
1
21, so d(1) = 2.
If N is odd then,
p
(N)
11 ≥ p12p23p34 . . . pN1 = qN > 0
so d(1)|N . As we observed previously, d(1)|2 (this did not depend on the parity of N). So
d(1) = 1 and the chain is aperiodic.
5. Let (Xn)n≥0 describe the position of the random walk at time n, and suppose that we start
at X0 = 1. If X1 = 2, the the probability to visit all states before returning to 1 is the same
as the probability of hitting N − 1 before getting ruined in the gambler’s ruin problem, with
a probability of winning a single game p and starting from 1. From class we know that this
probability is
P1 =
{
1− a−1
aN−1−1 , where a =
1
p − 1, if p 6= 12
1− 1N−1 if p = 12 .
Similarly, if X1 = N , we have that the probability of visiting all states before returning to 1 is
P2 =
{
1− b−1
bN−1−1 , where b =
1
q − 1, if q 6= 12
1− 1N−1 if q = 12 .
The reasoning is the same for any initial position X0 and p+ q = 1, so we may conclude that
P (visiting all states before returning to initial position) = pP1 + qP2
=
{
p
(
1− a−1
aN−1−1
)
+ q
(
1− b−1
bN−1−1
)
, where a = 1p − 1, b = 1q − 1, if p 6= 12
1− 2N−1 if p = 12 .
Problem 3
1. The 2-step transition matrix is M2 =
1
4


2 1 1
1 2 1
1 1 2
2. (1, 0, 0)M2 = 14 (2, 1, 1), so E(X2) =
1
4
(0× 2 + 1× 1 + 2× 1) = 3
4
.
3. Let N(i) be the mean number of transitions before visiting 2, given that X0 = i, i = 0, 1.
Then, by conditioning on the outcome of X1, N(0) = (1 +N(0))p00 + (1 +N(1))p01 + p02, and
N(1) = (1 + N(0))p10 + (1 + N(1))p11 + p12. Solving for N(0) and N(1), we obtain that the
answer is N(0) = 4.
Problem 4
1.
E0(T ) = 0, EN (T ) = 0.
2.
Ek(T ) = Ek(T | win first game)P (win first game) + Ek(T | lose first game)P (lose first game)
= (Ek+1(T ) + 1)p+ (Ek−1(T ) + 1)(1− p)
⇐⇒ xk = (xk+1 + 1)p+ (xk−1 + 1)(1− p)
⇐⇒ pxk+1 − xk + (1− p)xk−1 = −1
3. (a) We solve the characteristic equation
pX2 −X + (1− p) = 0
with discriminant
∆ = 1− 4p(1− p) = (2p− 1)2
• If p 6= 12 then ∆ > 0 and
yn = A
(
1 + 2p− 1
2p
)n
+B
(
1− 2p+ 1
2p
)n
so
yn = A+B
(
1− p
p
)n
if p 6= 1
2
.
• If p = 12 then ∆ = 0 and
yn = A
(
1
2p
)n
+Bn
(
1
2p
)n
so
yn = A+Bn if p =
1
2
.
(b) Replacing xi with Ci in (∗) gives C = − 12p−1 if p 6= 12 . Replacing xi with Ci2 in (∗) gives
C = −1 when p = 12 .
(c) If p 6= 12 , initial conditions impose{
A+B = 0,
A+B(α− 1)N = N2p−1 , where α = 1p
⇐⇒
{
A = −B,
−B(1− (α− 1)N ) = N2p−1 ,
(1)
⇐⇒
{
A = − N1−2p 11−(α−1)N ,
B = N1−2p
1
1−(α−1)N ,
(2)
So
Ek(T ) = xk = yk + Ck =
1
1− 2p
( −N
1− (α− 1)N +
N(α− 1)k
1− (α− 1)N + k
)
for p 6= 12 ,
Ek(T ) =
1
1− 2p
(
k +N
1− (α− 1)k
1− (α− 1)N
)
where α = 1p .
If p = 12 , similarly, we find {
A = 0
B = N
and Ek(T ) = Nk − k2 so for p = 12 we have Ek(T ) = k(N − k).





















































































































































































































































学霸联盟