Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: YSYY66

MATH 337 Assignment 2 Hints

1. (a) Fix ε > 0. If an → a as n → o then there exists N such that whenever n > N |an _ a| < ε.

Also note that if an → a as n → o, then there exists M such that |an _ a| < M for all M . Furthermore, since → 0 as n → o (with N and M ﬁx ed as above) there exists N ′ such that whenever n > N ′

< ε

Take n > max{N, N ′ }. Then

│ │ ak _ a │ = │ ╱ ← │

<

= +

n n

< ε + ε = 2ε,

k(n)ì9 ak → a as n → o.

(b) The sequence an = (_1)n does not converge, but converse is false.

k(n)ì9 (_1)k does, so the

2. (a) From the transition diagram: ❼ Recurrent states: 0, 1, 3 ❼ Transient states: 2

❼ Absorbing states: None

(b) From the transition diagram we see that there is no way to enter state 2 from states 0, 1 or 3 (i.e. the digraph is not strongly connected) and so the Markov chain is not irreducible.

3. From the transition matrix given in problem 2 and the identity fik = may obtain the system of equations:

f ← 9 = f ← 9 + f99

f99 = f ← 9 + fá9

fí9 = fí9 + fá9

fá9 = f ← 9 .

j(n)ì ← pij fjk we

It follows that f ← 9 = f99 = fí9 = fá9 . As state 1 is recurrent we have that f99 = 1 and so f ← 9 = f99 = fí9 = fá9 = 1.

4. (a) P is the transition matrix of an irreducible Markov chain with ﬁnitely many states. By deﬁnition there exists n e 良 such that Pn > 0. We may compute directly that Q := (I + P)/2 is stochastic, as P is stochastic, and so it is the transition matrix for some ﬁnite state Markov chain. Expanding Qn = ((I + P)/2)n using the binomial theorem, that Pn > 0 and that Pk 2 0 for k e {1, . . . , n _ 1} we see that Qn > 0.

(b) If π is a stationary distribution for P , then it follows that π Q = π ╱ 、 = + = π.

5. (a) It is not hard to see from the transition diagram for the matrix P that the Markov chain is irreducible.

For aperiodicity, you may either show that each state has period equal to 1, or prove that one state has period equal to 1, and use that aperiodicity is a class property.

(b) As the chain is irreducible and aperiodic, you may use the ergodic theorem for ﬁnite state Markov chains to ﬁnd the limiting distribution and recall that the limiting distribution is a stationary distribution.

6. As P is doubly stochastic, then we can compute directly that πP = π, where π is the row vector described by πj = for j = 0, . . . , M . As the Markov chain described by P is irreducible and aperiodic, there is a unique stationary distribution and the result follows.

7. The transition matrix for a fair die is given by the doubly stochastic matrix P = (pij ) where pij = 1/6 for i, j e {1, . . . , 6}. The result follows from problem 6, and the deﬁnition of ‘mean recurrence time’ for a given state.

8. Let A and B be row stochastic matrices and deﬁne C := AB. Denote the ij-th entry of C by cij . Then

M M M

← cij = ← ← aik bkj .

jì9 jì9 kì9

Interchanging summation and using that A and B are row stochastic gives the result.

9. Suppose there exist two states i and j such that the shortest path between them has length l > M . Then by the pigeonhole principle we visit some intermediate state k state twice. Removing this loop results in a shorter path between i and j, contradicting the minimality of l. Therefore it is possible to go from one state to another in at most M steps.

10. The transition matrix for the 2-state Markov process suggested in the hint of the problem is given by

P = ╱ 1_pN 一 p 一 9 ← .

Let Pn := ╱ p 、 for i, j e {1, 2}. Now

p = . . . = ╱ 1 _ p _ ← p 9(L)9(n) 一 9{ + .

From the lectures we know that such recurrence relations have solution given by:

p p 一 9 + p +pNp 一 9 ╱ 1 _ p _ ← .

Simplifying gives the result.