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 fixed 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 finitely many states.  By definition 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 finite 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 finite state Markov chains to find 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 definition of ‘mean recurrence time’ for a given state.

8. Let A and B be row stochastic matrices and define 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.