Discrete-Time Markov Chains
Definition (5.3.1)
The sequence of r.v. \(X_1, X_2, ...\) is said to be a Markov chain if for any event \(A\) we have
\[P(X_n \in A | X_1 = x_1, .., X_{n-1}=x_{n-1}) = P(X_n \in A | X_{n-1}=x_{n-1})\]
that is \(X_n\) depends only on \(X_{n-1}\) but not on any of the r.v. before it.
Clearly a Markov chain is a discrete-time space stochastic process. It can have either a discrete or continuous state space.
If we think of the index n as a time variable, then all that matters for the state of the system at time n is where it was at time n-1, but not on how it got to that state.
Example (5.3.2)
Random Walk
Say we flip a coin repeatedly. Let the random variable \(Y_i\) be 1 if the ith flip is heads, -1 otherwise. Now let \(X_n = \sum^n_{i=1} Y_i\).
Clearly we have
\[ P(X_n=x_n|X_1=x_1,...,X_{n-1}=x_{n-1}) =\\ \left\{ \begin{array} .\frac12 & \text{if} & x_n=x_{n-1}-1 \\ \frac12 & \text{if} & x_n=x_{n-1}+1\\ 0 & & \text{otherwise} \end{array}\right.=\\ P(X_n=x_n|X_{n-1}=x_{n-1}) \]
For a Markov chain all the relevant (probability) information is contained in the probability to get from state i to state j in k steps. For k=1 this is contained in the transition matrix \(P = (p_{ij})\), and in fact as we shall see P is all we need.
Example (5.3.4)
Asymmetric Random Walk
As above the state space are the integers but now we go from i to i+1 with probability p, to i-1 with probability q and stay at i with probability 1-p-q. Therefore
\[p_{ij}=\left\{\begin{array} .p & \text{if} & i=j+1 \\ q & \text{if} & i=j-1\\ 1-p-q & \text{if} & i=j\\ 0 & & \text{otherwise} \end{array}\right.\]
Example (5.3.5)
Ehrenfest chain
Say we have two boxes, box 1 with k balls and box 2 with r-k balls. We pick one of the balls at random and move it to the other box. Let \(X_n\) be the number of balls in box 1 at time n.
First note that we have \(X_n \in \{0,1,..,r\}\). Now say \(X_n =k\), so there are k balls in urn 1, therefore r-k balls in urn 2. In the next step we either move a ball from urn 1 to urn 2, or vice versa, so \(X_{n+1} =k+1\) or \(X_{n+1} =k-1\). Now
\(p_{k,k+1} = P(X_{n+1} =k+1|X_n =k) =\)
P(move ball from urn 2 to urn 1 | k balls in urn 1) =
P(pick one of the r-k balls in urn 2) = (r-k)/r
also
\(p_{k,k-1} = 1-p_{k,k+1} = k/r\) and \(p_{i,j} = 0\) otherwise.
If all the balls are in urn 2, the only possibility is to move one of them to urn 1, therefore \(p_{0,1}=1\). Similarly \(p_{n,n-1}=1\).
Ehrenfest used this model to study the exchange of air molecules in two chambers connected by a small hole.
Example (5.3.6)
Umbrella
Say you own r umbrellas, which are either at home or in your office. In the morning if it rains you take an umbrella, if there is one at home, equally in the evening in the office. Say it rains in the morning or in the evening independently with probability p. Analyze this as a Markov chain and find the transition matrix.
Solution 1: Say \(X_n\) is the number of umbrellas at home in the morning of the nth day, then \(X_n \in \{0,1,..,r\}\). Let \(q=1-p\). Now
\(P(X_n =i|X_{n-1} =i) =\) P(it is raining in the morning and evening or it is not raining in the morning and evening) = \(p^2+q^2, 1 \le i \le r\)
\(P(X_n =i-1|X_{n-1} =i) =\) P(it is raining in the morning but not in the evening) = \(pq, 1 \le i \le r\)
\(P(X_n =i+1|X_{n-1} =i) =\) P(it is not raining in the morning but it is raining in the evening) = \(qp, 1 \le i \le r-1\)
\(P(X_n =0|X_{n-1} =0) =\) P(it is not raining in the evening) = \(q\)
\(P(X_n =1|X_{n-1} =0) =\) P(it is raining in the evening) = \(p\)
\(P(X_n =r|X_{n-1} =r) =\) P(it is not raining in the morning or it is raining both times) = \(q+p^2\)
\[ \begin{bmatrix} q & p & 0 & ... & ... &0 \\ pq & p^2+q^2 & pq & ... &...&0\\ 0 & pq & p^2+q^2 & pq & ... &0\\ \vdots &&&&&\vdots \\ 0&0&0&0&pq&q+p^2 \end{bmatrix} \]
Solution 2: Say \(X_n\) is the number of umbrellas at your present location (home or work), then \(X_n \in \{0,1,..,r\}\). Now
\[P(X_n=r|X_{n-1}=0) = P(\text{ no umbrellas where you were last }) = 1\]
\[P(X_n=r-i|X_{n-1}=i) = P(\text{ it is not raining }) = q, 1 \le i \le r\]
\[P(X_n=r-i+1|X_{n-1}=i) = P(\text{ it is raining }) = p, 1 \le i \le r\]
\[ \begin{bmatrix} 0 & 0 & 0 & ... & ... &1 \\ 0 & 0 & 0 & ... &q&p\\ 0 & 0 & 0 & q & p &0\\ \vdots &&&&&\vdots \\ q&p&0&0&0&0 \end{bmatrix} \] both of these describe the “experiment”.
Definition (5.3.7)
Say we have a Markov chain \(\{X_n, n=1,2,...\}\) with transition matrix P. The n-step transition matrix is given by
\[P^{(n)} = (p^{(n)}_{ij} )=P(X_n=j|X_0=i)\]
Theorem (5.3.8)
\[P^{(n)} = P^n = \prod_{k=1}^n P\] proof Of course \(P^{(1)} = P\). Now
\[ \begin{aligned} &p_{ij}^{(2)} =P(X_2=j|X_0=i) =\\ &\sum_{k\in S} P(X_2=j|X_0=i,X_1=k)P(X_1=k|X_0=i) = \\ &\sum_{k\in S} P(X_2=j|X_1=k)P(X_1=k|X_1=i) = \\ &\sum_{k\in S} p_{kj}p_{ik} = (PP)_{ij} \end{aligned} \]
Example (5.3.9)
Ehrenfest chain
Let’s find the 2-step transition matrix for the Ehrenfest chain with r=3. The transition matrix is given by
\[ \pmb{P} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ \frac13 & 0& \frac23 & 0\\ 0 & \frac23 & 0 & \frac13 \\ 0 & 0& 1&0\\ \end{pmatrix} \]
and so the 2-step transition matrix is
\[ \pmb{PP} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ \frac13 & 0& \frac23 & 0\\ 0 & \frac23 & 0 & \frac13 \\ 0 & 0& 1&0\\ \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 \\ \frac13 & 0& \frac23 & 0\\ 0 & \frac23 & 0 & \frac13 \\ 0 & 0& 1&0\\ \end{pmatrix}=\\ \begin{pmatrix} \frac13 & 0 & \frac23 & 0 \\ 0 & \frac79& 0&\frac29\\ \frac29 & 0 & \frac79 & 0 \\ 0 & \frac23 & 0&\frac13\\ \end{pmatrix} \]
Example (5.3.10)
Umbrellas
We want to find \(P^{(2)}\) for solution 1 (in this generality) is difficult, but for solution 2 we have
\[ \pmb{PP}= \begin{bmatrix} 0 & 0 & 0 & ... & ... &1 \\ 0 & 0 & 0 & ... &q&p\\ 0 & 0 & 0 & q & p &0\\ \vdots &&&&&\vdots \\ q&p&0&0&0&0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & ... & ... &1 \\ 0 & 0 & 0 & ... &q&p\\ 0 & 0 & 0 & q & p &0\\ \vdots &&&&&\vdots \\ q&p&0&0&0&0 \end{bmatrix}=\\ \begin{bmatrix} q & p & 0 & ... & ... &1 \\ pq & q^2+p^2 & pq & ... &q&p\\ 0 & pq & q^2+p^2 & pq & p &0\\ \vdots &&&&&\vdots \\ 0&0&0&0&pq&q+p^2 \end{bmatrix} \]
Eigenvalues and Eigenvectors
In order to find \(P^{(n)}\) we could just find PPP..P n-times. With a little linear algebra this becomes easier: For many matrices P there exists a matrix U and a diagonal matrix D such that
\[P=UDU^{-1}\]
D is the matrix with the eigenvalues on the diagonal and U is the corresponding matrix of eigenvectors.
Example (5.3.11)
Ehrenfest chain
First we need to find the eigenvalues of the matrix P, that is we need to find the solutions of the equations \(Px=\lambda x\). This is equivalent to \((P-\lambda I)x=0\) or to \(\det(P-\lambda I)=0\). So we have:
\[ |\pmb{P-\lambda I}| = \begin{vmatrix} -\lambda & 1 & 0 & 0 \\ \frac13 & -\lambda& \frac23 & 0\\ 0 & \frac23 & -\lambda & \frac13 \\ 0 & 0& 1&-\lambda\\ \end{vmatrix}=\\ -\lambda\begin{vmatrix} -\lambda& \frac23 & 0\\ \frac23 & -\lambda & \frac13 \\ 0& 1&-\lambda\\ \end{vmatrix} -1\begin{vmatrix} \frac13 & \frac23 & 0\\ 0 & -\lambda & \frac13 \\ 0 & 1&-\lambda\\ \end{vmatrix}=\\ \\ -\lambda\left[-\lambda \left((-\lambda)^2-\frac13-\frac23(-\frac23\lambda) \right)\right]\\ -1\left[\frac13 ((-\lambda)^2-\frac13)\right]=\\ \\ \lambda^4-\frac{10}9\lambda+\frac19 \] \[\lambda^2= \left(\frac{10}9\pm\sqrt{(\frac{10}9)^2-4\times1\times\frac19} \right)/2=\frac{10\pm 8}{18}\] and so the eigenvalues are
\[\lambda_1=-1;\lambda_2=-\frac13;\lambda_3=\frac13;\lambda_4=1\]
The D above now is the matrix with the eigenvalues on the diagonal. The columns of the matrix U are the corresponding eigenvectors (with Euclidean length 1), so for example
\[ \begin{aligned} &(\pmb{P-\lambda_1 I})\pmb{x} = \begin{pmatrix} 1 & 1 & 0 & 0 \\ \frac13 & 1& \frac23 & 0\\ 0 & \frac23 & 1 & \frac13 \\ 0 & 0& 1&1\\ \end{pmatrix} \begin{pmatrix} x_1 \\x_2\\x_3\\x_4\end{pmatrix} = 0 \end{aligned} \]
\[ \begin{aligned} &x_1+x_2=0 \\ &\frac13x_1+x_2+\frac23x_3=0 \\ &\frac23x_2+x_3+\frac13 x_4 = 0\\ &x_3+x_4=0 \end{aligned} \] Of course we have \(\det(P-\lambda I)=0\), so this system is does not have a unique solution. Setting \(x_1 =1\) we can then easily find a solution \(x=(1,-1,1,-1)\).
This vector has Euclidean length \(\sqrt{(1^2+(-1)^2+1^2+(-1)^2)} = 2\), so the normalized eigenvector is \(x=(1/2,-1/2,1/2,-1/2)\).
Similarly we can find eigenvectors for the other eigenvalues.
Why does this help in computing \(P^{(n)}\)? It turns out that we have
\[P^{(2)} = PP = UDU^{-1}UDU^{-1} = UDDU^{-1} = UD^2U^{-1}\]
and the power of a diagonal matrix is easy to find:
\[ \pmb{D^2} = \begin{pmatrix} \lambda_1 & 0 & 0& 0 \\ 0&\lambda_2 & 0 & 0\\ 0& 0&\lambda_3 & 0 \\ 0& 0&0&\lambda_4 \end{pmatrix}^2= \begin{pmatrix} \lambda_1^2 & 0 & 0& 0 \\ 0&\lambda_2^2 & 0 & 0\\ 0& 0&\lambda_3^2 & 0 \\ 0& 0&0&\lambda_4^2 \end{pmatrix} \] in general we have \(P^{(n)} = UD^nU^{-1}\).
We can also make use of R here:
P=rbind(c(0,1,0,0),
c(1/3,0,2/3,0),
c(0,2/3,0,1/3),
c(0,0,1,0))
round(P, 3)## [,1] [,2] [,3] [,4]
## [1,] 0.000 1.000 0.000 0.000
## [2,] 0.333 0.000 0.667 0.000
## [3,] 0.000 0.667 0.000 0.333
## [4,] 0.000 0.000 1.000 0.000D=diag(eigen(P)$values)
U=eigen(P)$vectors
round(U%*%D%*%solve(U), 3)## [,1] [,2] [,3] [,4]
## [1,] 0.000 1.000 0.000 0.000
## [2,] 0.333 0.000 0.667 0.000
## [3,] 0.000 0.667 0.000 0.333
## [4,] 0.000 0.000 1.000 0.000round(U%*%D^2%*%solve(U), 3)## [,1] [,2] [,3] [,4]
## [1,] 0.333 0.000 0.667 0.000
## [2,] 0.000 0.778 0.000 0.222
## [3,] 0.222 0.000 0.778 0.000
## [4,] 0.000 0.667 0.000 0.333Theorem (5.3.12)
1 is always an eigenvalue of a transition matrix.
proof Note
\[P\begin{pmatrix}1\\1\\\vdots\end{pmatrix}=\begin{pmatrix}\sum_k p_{1k}\\\sum_k p_{2k}\\\vdots\end{pmatrix}=1\begin{pmatrix}1\\1\\\vdots\end{pmatrix}\] so \(\lambda=1\) is an eigenvalue of a transition matrix P, with (unnormalized) eigenvector \(x=(1,1,..,1)\).
Example (5.3.13)
Random Walk We have
\[ P= \begin{bmatrix} & &&&... \\ ... & 0 & \frac12 & 0 & \frac12 &0 & 0 &... \\ ... & 0 & 0 & \frac12 & 0 & \frac12 &0 &... \\ &&&&... \end{bmatrix} \] so this is an infinite matrix, and the solution via eigenvalues is out (actually, it can be done but requires a lot of matrix algebra). However
\[ \begin{aligned} &P_{ij}^{(2)} = P(X_2=j|X_0=i) = \\ &\sum_k P(X_2=j|X_1=k,X_0=i)P(X_1=k|X_0=i) = \\ &\sum_k P(X_2=j|X_1=k)P(X_1=k|X_0=i) = \\ &\frac12\left(I(j=k\pm 1)I(k=i\pm 1)\right) = \\ &\frac12\left(I(j=i-2)+2I(j=i)+I(j=i+2)\right) \\ \end{aligned} \]
An important consequence of the Markov property is the fact that given the present the past and the future are independent. This is formalized in the
Theorem (5.3.14)
Chapman-Kolmogorov equations
Let \(\{X_n ,n \ge 0\}\) be a Markov chain. Let x,y,z be in the state space, then
\[P \left(X_{n+m}=z|X_1=x \right)=\sum_{y\in S}P \left(X_{m}=y|X_1=x \right)P \left(X_{n}=z|X_1=y \right)\]
proof
theorem is an immediate consequence of the law of total probability and the Markov property.
Classification of States
There are a number of properties a Markov chains may or may not have. Here are some:
Definition (5.3.15)
A Markov chain is said to be irreducible if for each pair of states i and j there is a positive probability that starting in state i the chain will eventually move to state j.
Example (5.3.16)
Both the two random walks, the Ehrenfest chain and the Umbrella chains are irreducible.
Example (5.3.17)
Casino
Consider the following chain: you go to the Casino with $10. You play Blackjack, always betting $5. Let \(X_n\) be your “wealth” after the nth game. Then \(X_n \in \{0,5,10,15,..\}\) and
\[P(X_{n+k} = j|X_k =0) = 0\] for all n > 1.
(“0” is called a coffin or absorbing state). So this chain is not irreducible.
Definition (5.3.18)
A Markov chain is said to be aperiodic if for some \(n \ge 0\) and some state j we have
\[P(X_n = j|X_0 =j) > 0\]
and
\[P(X_{n+1} = j|X_0 =j) > 0\]
In other words there should be a chance to return to state j in either n steps or in n+1 steps.
Example (5.3.19)
Random walk I, the Ehrenfest chain and the Umbrella chain are not aperiodic because it is only possible to return to the same state in an even number of steps, but not an odd number. Random Walk II is aperiodic.
Definition (5.3.20)
A state x of a Markov chain is said to be recurrent if P(the chain returns to x infinitely often) = 1. A Markov chain is called recurrent if all its states are recurrent. A state that is not recurrent is called transient.
A recurrent state i is said to be positive recurrent if starting at i the expected time until the return to i is finite, otherwise it is called null recurrent.
Theorem (5.3.21)
In a finite-state chain all recurrent states are positive recurrent.
proof
Say \(S=\{x_1 ,...,x_m \}\) and assume (wlog) \(\{x_1 ,...,x_k\}\) are recurrent. Then for any \(i \ne j, i,j \le m\)
\[P(X_n =x_i |X_0 =x_j )>0\]
because \(x_i\) is recurrent, so we have to be able to get there infinitely often no matter where we start. Therefore any recurrent state is reachable from any other recurrent state.
Assume that there is no positive recurrent state. Then all states are either transient or null recurrent. So the expected return time to all the states is infinite. But there are only finitely many states, so this is impossible. Therefore there has to be at least one positive-recurrent state.
Say y is a positive-recurrent state, and x is recurrent. Then by the Chapman-Kolmogorov equations we find
\[ \begin{aligned} &P\left(X_{n+1}=y|X_0=x \right) = \\ &\sum_{j=1}^{m}P\left(X_{n+1}=y|X_0=x,X_n=x_j \right)P\left(X_{n}=x_j|X_0=x\right)\ge \\ &P\left(X_{n+1}=y|X_n=x \right)P\left(X_{n}=x|X_0=x\right)=\\ &p_{xy}P\left(X_{n}=x|X_0=x\right)\\ &\\ &P\left(X_{n+1}=y|X_0=x \right) = \\ &\sum_{j=1}^{m}P\left(X_{n+1}=y|X_0=x,X_1=x_j \right)P\left(X_{1}=x_j|X_0=x\right)\ge \\ &p_{xy}P\left(X_{n}=x|X_0=y\right) \end{aligned} \]
and so
\[ \begin{aligned} &E \left[\text{expected time until return to }x \right] = \\ &\sum_{n=1}^{\infty}nP\left(X_{n}=x|X_0=y\right) \le \\ &\sum_{n=1}^{\infty}n\frac1{p_{xy}}P\left(X_{n+1}=y|X_0=y\right) = \\ &\frac1{p_{xy}}E \left[\text{expected time until return to }y \right]<\infty \end{aligned} \] because y is positive recurrent, and so x is positive recurrent as well.
Example (5.3.22)
The Ehrenfest chain and the Umbrella chains are clearly positive recurrent. In the Casino example “0” is a recurrent state, the others are not.
Are the random walks recurrent? Good question! It seems clear that the asymmetric r.v. is not (if \(p \ne 0.5\)), because eventually one expects the walk to run off to infinity (or - infinity). How about Random Walk I? Actually let’s consider a more general problem:
Example (5.3.23)
Random Walk III
let the state space be the lattice of integers on \(\mathbb{R}^d\), that is
\[X_n =(i_1 , ..., i_d)\]
for \(i_k\) any integer. Then the chain goes from one point on the lattice to any of the 2d points that differ by one in one coordinate with probability 1/2d.
Here is an illustration for d=2
One of the great results in probability states:
Theorem (5.3.24)
The simple random walk is recurrent if \(d \le 2\), transient otherwise
or as Kakutani once said “A drunk man will find his way home but a drunk bird may get lost”.
proof omitted
Definition (5.3.25)
Positive recurrent aperiodic states are called ergodic.
Stationary Distribution
Until now we started the chain at time 0 in some specified state j. Let’s consider what happens if we choose that state according to some distribution \(\pi\):
\[ \begin{aligned} &P_\pi(X_1=k) = \\ &\sum_{j} P(X_1=k|X_0=j)P(X_0=j) = \\ &\sum_{j} P(X_1=k|X_0=j)\pi(j) = \left(\pi^T P \right)_k\\ \end{aligned} \] and clearly an interesting case is if the probability to be in a certain state does not change, that is if
\[\pi^T P= \pi^T\]
Note:
\[\pi^TP^{(n)} = \pi ^T P P^{(n-1)} = \pi^T P^{(n-1)} = ... = \pi^T\]
so this immediately implies that the probability for the chain to be in state k is always \(\pi_k\).
With this idea we have the
Definition (5.3.26)
Let \(S\) be the state space of a Markov chain \(X_n\) with transition matrix \(P\). Let \(\pi\) be a “measure” on S. Then \(\pi\) is called a stationary measureif
\[\pi^TP=\pi^T\].
We won’t discuss exactly what it means for \(\pi\) to be a “measure”. You can think of it in the same way as a probability distribution, only that we don’t have \(\sum \pi_i =1\).
Note:
\(\pi^TP=\pi^T\) iff
\((P^T\pi)^T=\pi^T\) iff
\(P^T\pi=\pi\) iff
\((P^T-I)\pi=0\)
so again this leads to a system of equations that is singular. Often we can get a unique solution by requiring that \(\pi\) be a proper probability distribution, that is that \(\sum \pi_i = 1\).
The interpretation is the following: Say we choose the initial state \(X_0\) according to \(\pi\), that is \(P(X_0 =i) = \pi_i\). Then \(\pi_i\) is the long-run proportion of time the chain visits state i, that is
\[\pi_i = \lim_{N\rightarrow \infty} \frac1N \sum^N_{k=1} I[X_i =i]\]
There is an extension of the WLLN to Markov chains:
Theorem (5.3.27)
Say \(\{X_n \}\) is a Markov chain with stationary distribution \(\pi\), and \(Z\sim \pi\). Say h is a function on the state space, then
\[\lim_{n\rightarrow \infty} \frac1n \sum_{k=1}^n h(X_i)=E[h(Z)]\] proof omitted
One of the main results for Markov chains is the following:
Theorem
If the Markov chain \(\{X_n \}\) is irreducible and ergodic, then
\[\lim_{n\rightarrow \infty} P(X_n=j)=\pi_j\]
proof omitted
Example (5.3.28)
Ehrenfest chain
To find a (?) stationary measure we have to solve the system of equations
\[\pi^TP=\pi^T\]
Let’s start with the case r=3:
\[ \begin{aligned} &\begin{pmatrix} \pi_1 &\pi_2&\pi_3&\pi_4\end{pmatrix}=\\ &\begin{pmatrix} \pi_1 &\pi_2&\pi_3&\pi_4\end{pmatrix} \begin{pmatrix} 1 & 1 & 0 & 0 \\ \frac13 & 1& \frac23 & 0\\ 0 & \frac23 & 1 & \frac13 \\ 0 & 0& 1&1\\ \end{pmatrix} \end{aligned} \] Here this means the system
\(\pi_0 = 1/3 \pi_1\)
\(\pi_1 = \pi_0 +2/3\pi_2\)
\(\pi_2 = 2/3 \pi_1 + \pi_3\)
\(\pi_3 = 1/3\pi_2\)
\(\pi_0 + \pi_1 + \pi_2 + \pi_3 = 1\)
and so
\[\pi = (1/8,3/8,3/8,1/8)\]
Before doing the general case it is often a good idea to do a specific case that has all the “parts” (ie equations), so let’s do next r=5:
First the transition matrix:
\[ \pmb{P} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0\\ \frac15 & 0 &\frac45 & 0 & 0 & 0\\ 0 & \frac25 & 0 &\frac35 & 0& 0\\ 0 & 0 & \frac35 & 0 &\frac25 & 0 & \\ 0 & 0 & 0 &\frac45 & 0 &\frac15 \\ 0 & 0 & 0 &0 & 1 & 0 \end{pmatrix} \]
and now the equations:
\[ \begin{aligned} &\pi_0=\frac15 \pi_1 \\ &\pi_1 = \pi_0+\frac25 \pi_1\\ &\pi_2 = \frac45\pi_1+\frac35 \pi_3 \\ &\pi_3 = \frac35\pi_2+\frac45 \pi_4 \\ &\pi_4 = \frac25\pi_3+\pi_5 \\ &\pi_5 = \frac15\pi_4 \end{aligned} \]
\[ \begin{aligned} &\pi_1=5\pi_0 \\ &\pi_2 = \frac52(\pi_1-\pi_0)=10\pi_0\\ &\pi_3 = \frac53(\pi_2-\frac45\pi_1)=10\pi_0\\ &\pi_4 = \frac54(\pi_3-\frac35\pi_2)=5\pi_0\\ &\pi_5 = \frac15\pi_4 =\pi_0\\ &\sum \pi_i =32\pi_0 \end{aligned} \]
and so we find
\[\pmb{\pi}=\frac1{32} \begin{pmatrix} 1 \\ 5 \\ 10 \\ 10 \\ 5 \\ 1 \\ \end{pmatrix}\]
or
\[\pi_j= {{5}\choose{j}}/2^5\] Finally, for the general case. The previous calculation gives us an idea: maybe a stationary distribution is give by
\[\pi_j= {{r}\choose{j}}/2^r\] Let’s check. We have \[ \begin{aligned} &p_{j,j-1} =\frac{j}{r} \\ &p_{j,j+1} =\frac{r-j}{r} \text{ if }1\le j\le r-1 \\ &p_{0,1} = p_{r,r-1}=1\\ \end{aligned} \] Let \(P_i\) be the \(i^{th}\) column of P. Notice that all the terms always include a \(1/2^r\), so we can ignore those. First we do the first two and last two columns:
\[ \begin{aligned} &\pmb{\pi^TP_0} =\pi_1\frac1{r}= {{r}\choose{1}}\frac1r=1=\pi_0\\ &\pmb{\pi^TP_1} =\pi_0+\pi_2\frac2{r}= 1+{{r}\choose{2}}\frac2r=\\ &1+\frac{r(r-1)}{2}\frac2r= 1+(r-1) = r={{r}\choose{1}}=\pi_1\\ &\pmb{\pi^TP_{r-1}} =\frac{2}{r}\pi_{r-2}+\pi_r= {{r}\choose{r-2}}\frac2r+1=\\ &\frac{r(r-1)}{2}\frac2r+1= 1+(r-1) = r={{r}\choose{1}}=\pi_{r-1}\\ &\pmb{\pi^TP_r} =\pi_{r-1}\frac1{r}= {{r}\choose{r-1}}\frac1r=1=\pi_r\\ \end{aligned} \]
and for \(2\le j\le r-2\) we find
\[ \begin{aligned} &\pmb{\pi^TP_j} = \pi_{j-1}P_{j-1,j}+\pi_{j+1}P_{j+1,j}=\\ &{{r}\choose{j-1}}\frac{r-j+1}{r}+{{r}\choose{j+1}}\frac{j+1}{r} = \\ &\frac{r!}{(r-j+1)!(j-1)!}\frac{r-j+1}{r}+\frac{r!}{(r-j-1)!(j+1)!}\frac{j+1}{r} = \\ &\frac{r!}{(r-j)!(j-1)!}\frac{1}{r}+\frac{r!}{(r-j-1)!j!}\frac{1}{r} = \\ &\frac{r}{(r-j)!j!}\frac{r!}{r} = {{r}\choose{j}}=\pi_j \\ \end{aligned} \]
Example (5.3.29)
Umbrellas
For solution 1 the system of equations is
\[ \begin{aligned} &\pi_0q\pi_0 +p\pi_1 \\ &\pi_i=p\pi_{i-1} +(p^2+q^2)\pi_i+pq\pi_{i+1} \text{ for }i=1,...,r-1 \\ &\pi_r = pq\pi_{r-1}+(q+p^2)\pi_r \\ \end{aligned} \] and so
\[ \begin{aligned} &\pi_0 =q\pi_1 \\ &\pi_1=p\pi_{0} +(p^2+q^2)\pi_1+pq\pi_{2} = \\ &(pq+p^2+q^2-1)\pi_1+pq\pi_2=0 \\ &((p+q)^2-pq-1)\pi_1+pq\pi_2=0 \\ &-pq\pi_1+pq\pi_2=0 \\ &\pi_2=\pi_1 \end{aligned} \] and so on shows \(x=(q,1,..,1)^T\) solves the system. Now \(q+1+..+1=q+r\), so the stationary distribution is
\[\pi_0 =q/(q+r), \pi_i =1/(q+r) \text{ }i=1,..,r\]
For solution 2 we have
\[ \begin{aligned} &\pi_0=q\pi_r \\ &\pi_i=q\pi_{r-i}+p\pi_{r-i+1} \\ &\pi_r =\pi_0+p\pi_r \\ \end{aligned} \]
and we see that we get the same stationary distribution as in solution 1.
So, what percentage of times do you get wet? Clearly this is
\[P(\text{no umbrella and it rains}) = q\pi_0 =q^2/(q+r)\]
Example (5.3.30)
Random Walk
Let \(\mathbb{N}\) be the integers and define a Markov chain by \(p_{i,i+1} = p\) and \(p_{i,i-1} = q = 1-p\). A stationary measure is given by \(\pi_i =1\) for all i because \((\pi P)_i = 1p+1q = 1\).
Now assume \(p\ne q\) and define \(\pi_i =(p/q)^i\). Then
\[ \begin{aligned} & \sum_{i} \pi p_{ij}=\pi_{j+1}p_{j+1,j}+\pi_{j-1}p_{j-1,j} =\\ & \left(\frac{p}{q} \right)^{j+1}q+\left(\frac{p}{q} \right)^{j-1}p = \\ &\left(\frac{p}{q} \right)^{j}(p+q) = \left(\frac{p}{q} \right)^{j}=\pi_j\\ \end{aligned} \] and this shows that stationary measure are not unique.
Definition (5.3.31)
A Markov chain is said to be time-reversible if
\[\pi_i P_{ij} =\pi_j P_{ji}\]
for all \(i\ne j\). It can be shown that for a time reversible Markov chain if the chain is started from \(\pi\) and run backwards in time it again has transition matrix P.
Example (5.3.32)
The Ehrenfest chain is time-reversible. We will show this for the case i=k, j=k+1:
\[ \begin{aligned} &2^r\pi_kp_{k,k+1} = {{r}\choose{k}}\frac{r-k}{r} =\\ &\frac{r!}{(r-k)!k!}\frac{r-k}{r} = \\ &\frac{r!}{(r-k-1)!k!}\frac{1}{r} = \\ &\frac{r!(k+1)}{(r-k-1)!(k+1)!}\frac{1}{r} = \\ &{{r}\choose{k+1}}\frac{k+1}{r}=\\ &2^r\pi_{k+1}p_{k+1,k} \end{aligned} \]
The Gambler’s Ruin Problem
Suppose you go to the casino and repeatedly play a game where you win and double your “bet” with probability p and loose with probability q=1-p. For example, if you play roulette and always place your bet on “red” we have p=18/38.
Suppose you go in with the following plan: you have \(\$m\) to start, you always bet \(\$1\) in each round and you stay until you either lost all your money or until you have reached \(\$N\). What is the probability of reaching \(\$N\) before going broke?
If we let \(X_n\) denote your “fortune” after n rounds \(\{X_n \}\) is a Markov chain on \(\{0,1,..,N\}\) with transition probabilities
\[ \begin{aligned} &p_{00}=p_{NN} = 1\\ &p_{i,i+1} = p =1-q=1-p_{i,i-1} \end{aligned} \]
for \(i \in \{1,..,N-1\}\).
Also we have \(X_0 =m\).
Let \(P_m\) denote the probability that, starting at m the fortune will eventually reach N. We have:
\[ \begin{aligned} &P_m = P\left(X_n=N\text{ for some n}\ge 1|X_0=m\right) = \\ &P\left(X_n=N\text{ for some n}\ge 1|X_0=m,X_1=m-1\right)P(X_1=m-1|X_0=m) + \\ &P\left(X_n=N\text{ for some n}\ge 1|X_0=m,X_1=m+1\right)P(X_1=m+1|X_0=m) = \\ &P_{m-1}q+P_{m+1}p \end{aligned} \] so we have
\[P_m=P_{m-1}q+P_{m+1}p\] for \(m=1,...,N-1\). Therefore
\[P_{m-1}q+P_{m+1}p=P_m=P_m(q+p)=qP_m+pP_m\] \[q(P_{m+1}-P_{m})=q(P_m-P_{m-1})\] \[P_{m+1}-P_{m}=\frac{q}p(P_m-P_{m-1})\] Also \(P_0=0\), and so
\[ \begin{aligned} &P_{m}-P_{m-1}=\frac{q}{p}(P_{m-1}-P_{m-2}) = \\ &\left(\frac{q}{p}\right)^2(P_{m-2}-P_{m-3}) = ... =\\ &\left(\frac{q}{p}\right)^{m-1}(P_{1}-P_{0}) = \\ &\left(\frac{q}{p}\right)^{m-1}P_{1} \end{aligned} \] now
\[P_m =\sum_{i=1}^m (P_i-P_{i-1})=\sum_{i=1}^m \left(\frac{q}{p}\right)^{m-1}P_{1}=\] \[P_M=P_1\sum_{i=0}^m \left(\frac{q}{p}\right)^{j}=P_1\left\{\begin{array}.m&\text{ if }&p=\frac12\\\frac{1-(q/p)^m}{1-q/p}&\text{ if }&p\ne\frac12\\\end{array}\right.\] Note that \(P_N =1\) and that the formula above also holds for i=N, so we have
\[1=P_N=P_1\left\{\begin{array}.N&\text{ if }&p=\frac12\\\frac{1-(q/p)^N}{1-q/p}&\text{ if }&p\ne\frac12\\\end{array}\right.\]
\[P_1=\left\{\begin{array}.\frac1N&\text{ if }&p=\frac12\\\frac{1-q/p}{1-(q/p)^N}&\text{ if }&p\ne\frac12\\\end{array}\right.\]
\[P_m=\left\{\begin{array}.\frac{m}N&\text{ if }&p=\frac12\\\frac{1-(q/p)^m}{1-(q/p)^N}&\text{ if }&p\ne\frac12\\\end{array}\right.\]
The main “trick” in this calculation was to condition on the “right” event (here \(X_1\)). This is often the case when doing math with Markov chains.
Say in our example playing roulette you start with $100. What is the probability of reaching N before going broke? We find
N=101:130
m=100
p=18/38;x=(1-p)/p
plot(N,(1-x^m)/(1-x^N),pch=20)
Is it the same probability to start with $100 and reach $110 or to start with $200 and reach $220? The answer is no:
round(c((1-x^100)/(1-x^110), (1-x^200)/(1-x^220)), 4)## [1] 0.3487 0.1216Example (5.3.33)
two-state process
Here \(X_n\) takes only two possible states, coded as 0 and 1. Therefore the transition matrix is given by
\[ \pmb{P} = \begin{pmatrix} a & 1-a \\ 1-b & b \end{pmatrix} \] Now
\[ \begin{aligned} &|P-\lambda I| = (a-\lambda)(b-\lambda)-(1-a)(1-b)=\\ &(\lambda-1)(\lambda+1-a-b) =0 \end{aligned} \] and so we have eigenvalues \(\lambda_1=1\) and \(\lambda_1=a+b-1\). The eigenvectors are
\[ \begin{aligned} &(P-\lambda_1 I)x = \begin{pmatrix} a-1 & 1-a \\ 1-b & b-1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}= \begin{pmatrix} 0 \\ 0 \end{pmatrix}\\ &(a-1)x_1+(1-a)x_2=0 \\ &x_1 = x_2\\ &\sqrt{1^2+1^2}=\sqrt 2\\ &u_1=(1\text{ }1)^T/\sqrt 2 \end{aligned} \] \[ \begin{aligned} &(P-\lambda_2 I)x = \begin{pmatrix} a-(a+b-1) & 1-a \\ 1-b & b-(a+b-1) \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}= \begin{pmatrix} 0 \\ 0 \end{pmatrix}\\ &(1-b)x_1+(1-a)x_2=0 \\ &x_2=1\rightarrow x_1=-\frac{1-a}{1-b}\\ &\sqrt{(-\frac{1-a}{1-b})^2+1^2}=\frac{\sqrt{(1-a)^2+(1-b)^2} }{1-b}\\ \end{aligned} \] If we define \(q=\sqrt{(1-a)^2+(1-b)^2}\) the second eigenvector is
\[u_2=\begin{pmatrix} a-1 \\ 1-b\end{pmatrix}/q\]
\[ \pmb{U} = \begin{pmatrix} \frac1{\sqrt 2} & \frac{a-1}{q} \\ \frac1{\sqrt 2} & \frac{1-b}{q} \end{pmatrix}\\ \pmb{U}^{-1} = \frac1{\frac1{\sqrt 2}\frac{1-b}{q}-\frac{a-1}{q}\frac1{\sqrt 2}} \begin{pmatrix} \frac{1-b}{q} & -\frac{a-1}{q} \\ -\frac1{\sqrt 2} & \frac1{\sqrt 2} \end{pmatrix}=\\ \frac{\sqrt 2 q}{2-a-b} \begin{pmatrix} \frac{1-b}{q} & \frac{1-a}{q} \\ -\frac1{\sqrt 2} & \frac1{\sqrt 2} \end{pmatrix} \]
\[ \begin{aligned} &P^n=UD^nU^{-1} = \\ &\begin{pmatrix} \frac1{\sqrt 2} & \frac{a-1}{q} \\ \frac1{\sqrt 2} & \frac{1-b}{q} \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & (a+b-1)^n \end{pmatrix} \frac{\sqrt 2 q}{2-a-b} \begin{pmatrix} \frac{1-b}{q} & \frac{1-a}{q} \\ -\frac1{\sqrt 2} & \frac1{\sqrt 2} \end{pmatrix}= \\ &\frac{1}{2-a-b} \begin{pmatrix} 1-b+(1-a)(a+b-1)^n & 1-a+(1-a)(a+b-1)^n \\ 1-b+(1-a)(a+b-1)^n & 1-a+(1-a)(a+b-1)^n \end{pmatrix} \end{aligned} \]
For the stationary distribution we find
\[ \begin{aligned} &\begin{pmatrix} \pi_1&\pi_2\end{pmatrix} \begin{pmatrix} a & 1-a \\ 1-b & b \end{pmatrix} \begin{pmatrix} \pi_1\\\pi_2\end{pmatrix}\\ & a\pi_1+(1-b)\pi_2=\pi_1 \\ &\pi_1+\pi_2 = 1\\ &\pi=\frac{1}{2-a-b}\begin{pmatrix} 1-b\\1-a\end{pmatrix} \end{aligned} \] Finally note that \(0<a,b<1\), therefore \(0<a+b<2\) and \(-1<a+b-1<1\), and so
\[(a+b-1)^n\rightarrow 0\] which means
\[\lim_{n\rightarrow \infty}P^n=\begin{pmatrix} \pi&\pi\end{pmatrix}\]