{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$.  {solution} * As suggested, let$h$be a harmonic function obtaining its maximum value at$h(s) = M$. Suppose$p_{sz} >0$. Since$Ph = h$, we have \begin{eqnarray*} M =& &h(s) \\ &=& (Ph)_s \\ &=& \sum_j p_{sj} h(j) \\ &=& p_{sz}h(z) + \sum_{j\not=z} p_{sj} h(j) \\ &\leq& p_{sz}h(z) + (1-p_{sz})M. \end{eqnarray*} Rearranging, we obtain $$p_{sz}M \leq p_{sz}h(z),$$ so that$h(z) \geq M$and since$M$is the maximum, we have the desired equality. Since$P$is irreducible, for every$z \in S$, there is an$n \geq 1$such that$p_{sz}(n) >0$. Since we also have $$P^n h = h,$$ the previous argument with$P^n$taking the place of$P$applies to show that$h(z) = M$. * Notice any solution to$(P-I)v = 0$must be harmonic and thus must be a constant function/vector, so that the nullspace of$P-I$is generated by the constant (column) vector$(1,1,1)$. * By the rank-nullity theorem, the matrix$P_I$has rank$n-1$, and thus its transpose,$P^t -I$also has a kernel of dimension$1$. Notice that$v = vP$if and only$P^tv^t = v^t$; that is,$v$is a solution to$vP = v$if and only if$v^t$is the nullspace of$P^t - I$. Hence the set subspace of solutions to$v P = v$has dimension$1$. * By definiton, a stationary distribution$\pi$satisfies$\pi = \pi P$and$\pi$has all nonnegative entries that sum to$1$; thus if$\pi'$is another stationary distribution, since the solution space has dimension$1$, we must that$c \pi = \pi'$--summing both sides yields that$c=1$.  {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$. {solution} It is easy to verify that$P$is irreducible and aperiodic, since$P^3$has all positive entries:  {r} Q = P %*% P%*%P Q  Thus we know that the stationary distribution$\pi$satisfies $$\pi_s = (\mathbb{E} T^s)^{-1}.$$ We easily compute$\pi$. {r} eigen(t(P)) stat = eigen(t(P))$vectors[,1] stat = stat/sum(stat) stat  {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$. 
{solution} The gamma distibution is available in R via; rgamma(n, shape, rate = 1, scale = 1/rate). For this question, we can also see it as the sum of two independent exponentials of rate $\lambda = 3$. The following code is adapted from the excessive life code; it gives the number of arrivals by time $t$:  {r} number<- function(t){ arr = rexp(1,3) + rexp(1,3) inter = arr while(arr[length(arr)] {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.  {solution} Let $N$ be a Poisson counting process with intensity $\lambda$; then the inter-arrival times are exponential with rate $\lambda = \mu^{-1}$, which have variance $\mu^2$ We know that $N(t)$ is a random variable with Poisson mean $\lambda t$. We already have a proof that $N(t)/t \to \lambda$, but now we can also verify that, without a limit, we have $$\mathbb{E} N(t) /t = \lambda.$$ In addition, the sum of independent Poissons is again Poisson, thus $N(n)$ has the same law as the sum of $n$ independent Poisson random variables $X_i$ with mean $\lambda$, and variance $\lambda$. Considering, first only integer times, $n$, we have that $$\frac{N(n) -n\lambda}{\sqrt{n \lambda}}$$ has the same law as $$\frac{ \sum_{i=1} ^n X_i - n \lambda}{\sqrt{n \lambda}},$$ which the regular central limit assures us converges in distirbution to a standard normal. Let $[t]$ denote the integer part of $t$, so that $[1.5] = 1$. Notice that $$N([t] -1) \leq N(t) \leq N( [t] +1)$$ so that standard arguments give the result for general $t$. 
{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}^{+}$ 
{solution} Let $T_i$ be the $i$th return time to $s$, so that $T_0 = 0$. We already know that $T_1 < \infty$ with probability one. By the Strong Markov property, the same holds for all the $T_i$; in particular, $$\mathbb{P}(T_1 < \infty, T_2 < \infty) = (\mathbb{P}(T_1 < \infty))^2.$$ Hence $$\mathbb{P} \big( \bigcap _{i=0} ^{\infty} \{ T_i < \infty \} \big) = 1.$$ 
{exercise} Prove that if an irreducible Markov chain has a recurrent state, then all the states must also be recurrent. 
{solution} Let $s\in S$ be the given recurrent state of the Markov chain $X$, so that we know that $$T^s = \inf \{ n \geq 1: X_n=s | X_0 = s\}$$ is finite with probability one. Let $t \in S$ be another state. By irreducibility, there exists $n \geq 1$, so that $p_{st}(n) >0$ and in $n$ steps it is possible to reach $t$ from $s$, and on this event, we still must have with the chain will return to $s$. Thus by the strong Markov property, $T^{ts}$, the time it takes for a chain starting at $t$ to reach $s$ is finite with probability one. *One* way to return to $t$ starting at $t$, is to go to $s$ and then from $s$ to go to $t$. Thus it suffices to argue that $T^{st}$ is also finite with probability one. Since each time the chain returns to $s$, we have an independent nonzero chance of reaching $t$ again, by the strong Markov property, this will eventually happen with probability $1$. 

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