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
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
