```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
```


```{exercise, name="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$.  
```


<br>


```{exercise}
Consider the Markov chain $X$ on five states $\{1,2,3,4,5\}$ started at $1$ 
with transition matrix given by
```
```{r}  
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
```
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}
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$.
```

<br>


```{exercise}
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.
```

<br>


```{exercise}
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}^{+}$
```


<br>

```{exercise}
Prove that if an irreducible Markov chain has a recurrent state,  then all the states must also be recurrent.   
```



<br>
<br>

*  Version: `r format(Sys.time(), '%d %B %Y')`
* [Rmd Source](https://tsoo-math.github.io/ucl/QHW6.Rmd)

