AMATH 562 WI24 - Problem Set 1 Solutions 2025 | 100% Correct | The Ultimate Study Guide for Yr. (2026/2027)

AMATH 562 WI24 - Problem Set 1 Solutions



Solution 1. Let S = {0, 1, . . . , N } be the state space of the time homogeneous Markov chain {Xn }n≥0 . Suppose Xn = i,
0 ≤ i ≤ N . This implies that there are i white balls in the second urn. Thus, there are four different events that may happen
in a transition:
probability second urn black 1 − i/N second urn white i/N
first urn black i/N i/N (1 − i/N ) (i/N )2
first urn white 1 − i/N (1 − i/N )2 i/N (1 − i/N )

Thus, the transition probabilities are given by



 (i/N )2 if j = i − 1 ≥ 0


2i/N (1 − i/N )

if j = i ≥ 0
p(i, j) := P(Xn+1 = j|Xn = i) = .
(1 − i/N )2
 if j = i + 1 ≥ 0




0 otherwise

The transition matrix is given by
 
0 1 0 ··· 0
1/N 2 2/N (1 − 1/N ) (1 − 1/N )2 ··· 0
 
 
2
P = 0
 (2/N ) 4/N (1 − 2/N ) · · · 0  .
 . .. .. .. .. 
 . .
 . . . .


0 0 ··· 1 0
(N +1)×(N +1)

Suppose there exists a stationary distribution π = (π0 , π1 , . . . , πN ) that satisfies the detailed balance. Then it must admit
i
p(i, i + 1) (1 − i/N )2 (N − i)2 Y (N − j)2
πi+1 = πi = πi = π i = π0 .
p(i + 1, i) (i + 1)2 /N 2 (i + 1)2 j=0
(j + 1)2

We can choose π0 as
 −1 !−1
N −1 i N −1
X Y (N − j)2  X (N − i)2 (N − i + 1)2 . . . N 2
π0 = 1 + = 1+ .
i=0 j=0
(j + 1)2 i=0
12 22 . . . (i + 1)2

Thus, Xn satisfies detailed balance with respect to π.

Solution 2. For the Markov chain to be reversible, we need that πi p(i, j) = πj p(j, i) for i, j = 0, 1, 2, . . . , n. Of interest is
πi p(i, i + 1) = πi+1 p(i + 1, i). This implies that for i = 1, 2, 3, . . . , n − 1,
p(i, i + 1) λi λi−1 λi λ0 λ1 . . . λi
πi+1 = πi = πi = πi−1 = · · · = π0 .
p(i + 1, i) µi+1 µi µi+1 µ1 µ2 . . . µi+1

1

, We can choose π0 as
1
π0 = Pn λ0 λ1 ...λi−1
1+ i=1 µ1 µ2 ...µi

so that π0 + π1 + · · · + πn = 1.

Solution 3. (i) Suppose there exist a stationary distribution π = (π1 , π2 , . . . , π5 ). Then π must satisfy the system of equations

1

 (1 − 2m )π1 + 12 π2 = π1 
1
π2 = m π1

 
 
1
π + 1π = π2

 

 2m 1 2 3
 
π3 1
= m π1
 
1 1 ⇒
2 π2 + 2 π4 = π3
1

 
π4 = m π1
 21 π3 + 2m1
 

 π5 = π4 


π


1 5 = π1
1

2 π4 + (1 − 2m π5 ) = π5
P5
Since π is a probability distribution, i=1 π1 = 1. This implies that
m
π1 = .
2m + 3
Therefore, the only stationary distribution reads
 
m 1 1 1 m
π= , , , , .
2m + 3 2m + 3 2m + 3 2m + 3 2m + 3

The following 4 equations
1 1 1 1
π1 p12 = = π2 p21 , π2 p23 = = π3 p32 , π3 p34 = = π4 p43 , π4 p45 = = π5 p54
4m + 6 4m + 6 4m + 6 4m + 6
imply that the Markov Chain determined by transition matrix P satisfies detailed balance with repect to π.
(ii) The characterstic polynomial reads

1 1
λ − (1 − 2m ) − 2m 0 0 0
− 12 λ − 21 0 0
1
p(λ) = 0 − 12 λ − 12 0 = (λ − 1)[4mλ2 − (4m − 2)λ − 1][4mλ2 + 2λ + (1 − 2m)].
16m2
0 0 − 21 λ − 21
1 1
0 0 0 − 2m λ − (1 − 2m )

Hence the 5 eigenvalues are
√ √ √ √
2m − 1 + 4m2 + 1 2m − 1 − 4m2 + 1 −1 + 8m2 − 4m + 1 −1 − 8m2 − 4m + 1
λ1 = 1, λ2 = , λ3 = , λ4 = , λ5 = .
4m 4m 4m 4m
Given that m ≥ 1, we have that
√ √
|2m − 1 − 4m2 + 1| 2m − 1 + 4m2 + 1 2m − 1 + 2m + 1
|λ3 | = ≤ = |λ2 | < = 1.
4m 4m 4m
√ √ √
| − 1 + 8m2 − 4m + 1| 1 + 8m2 − 4m + 1 (1 + 2 2)m
|λ4 | = < = |λ5 | < < 1.
4m 4m 4m
Observe that
p √
1+ (4m2 − 8m + 4) + 4m2 + 4m − 3 2m − 1 + 4m2 + 4m − 3
|λ5 | = ≤ ≤ |λ2 |,
4m 4m

2