Homework 6

Exercise 1 (Multiplying on the right) Let \(P\) be an irreducible transition matrix on a finite state space \(S\) of size \(n\). Let \(h :S \to \mathbb{R}\) be a function on \(S\), and regard \(h\) as a column vector. Call a function \(h\) harmonic if \(Ph = h\).

• Show that every harmonic function is a constant. Hint: every function achieves its maximum, since \(S\) is finite. Let \(M= \max_{s \in S} h(s) = h(s)\) for some \(s \in S\). First, show that \(h(z) = M\) for every \(z \in S\) for which \(p_{sz} >0\). Finally, use irreducibility, to extend the claim for all \(z \in S\).

• Show that the matrix \(P- I\) has a kernel of dimension \(1\); that is, the set of vectors \(v\) such that \((P-I)v = 0 \in \mathbb{R}^n\) has dimension \(1\).

• Recall that the rank of a matrix is equal to the rank of its transpose. Use this fact to show that the set of vectors \(v\) such that \(v = vP\) has dimension \(1\).

• Use the previous part to argue that there is at most one stationary distribution for \(P\).

Exercise 2 Consider the Markov chain \(X\) on five states \(\{1,2,3,4,5\}\) started at \(1\) with transition matrix given by

P <- matrix(c(1/4, 1/4, 1/2, 0,0, 
              1/4, 1/8,1/8,0,1/2, 
              1/4,0,0, 1/2, 1/4, 
              0,0,0,1/2, 1/2, 1/3, 1/3, 0, 0, 1/3), nrow =5)
P <-t(P)
P

##           [,1]      [,2]  [,3] [,4]      [,5]
## [1,] 0.2500000 0.2500000 0.500  0.0 0.0000000
## [2,] 0.2500000 0.1250000 0.125  0.0 0.5000000
## [3,] 0.2500000 0.0000000 0.000  0.5 0.2500000
## [4,] 0.0000000 0.0000000 0.000  0.5 0.5000000
## [5,] 0.3333333 0.3333333 0.000  0.0 0.3333333

For each \(s \in \{1,2,3,4,5\}\), let \(T^s = \inf \{ n \geq 1: X(n)=s | X(0)=s\}\).

• By running simulations, estimate \(\mathbb{E} T^s\), for each \(s\).
  
• Using our theory of Markov chains, compute exactly \(\mathbb{E} T^s\), for each \(s\).

Exercise 3 By running simulations, verify the central limit theorem for renewal processes, in the case where the inter-arrival times are given by a gamma distribution with shape \(n=2\) and rate \(\lambda=3\).

Exercise 4 Check (by pen and paper), the law of large numbers and the central limit theorem for renewal processes, for the special case where the renewal process is a Poisson process.

Exercise 5 Prove that if \(s\) is a recurrent state of a Markov chain that is started at \(s\), then with probability one, it must return to that state for infinitely many \(n \in \mathbb{Z}^{+}\)

Exercise 6 Prove that if an irreducible Markov chain has a recurrent state, then all the states must also be recurrent.

• Version: 19 November 2020
• Rmd Source