**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\).

```
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\).

- Version: 19 November 2020
- Rmd Source