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.