Chapter 11: Markov ChainsContent check — Probability (Grinstead and Snell), Chapter 11: Markov Chains

(a), (f)

(a) $a=0$ or $b=0$

(b) $a=b=1$

(c) $(0<$ $a<$ $1\text{ and }0<$ $b<$ $1)$ or $(a=1\text{ and }0<b<1)$ or $(0<a<1\text{ and }b=1)$⁠.

(a) $(2/\mathrm{3,1}/3)$

(b) $(1/\mathrm{2,1}/2)$

(c) $(2/\mathrm{7,3}/\mathrm{7,2}/7)$

The fixed vector is $(\mathrm{1,0})$ and the entries of this vector are not strictly positive, as required for the fixed vector of an ergodic chain.

Let $$𝐏=\left(\begin{array}{ccc}{p}_{11}& p_{12}& p_{13}\\ p_{21}& p_{22}& p_{23}\\ p_{31}& p_{32}& p_{33}\end{array}\right),$$ with column sums equal to 1. Then $$\begin{array}{cc}\hfill (1/\mathrm{3,1}/\mathrm{3,1}/3)𝐏& =(1/3\sum _{j=1}^3{p}_{j1},1/3\sum _{j=1}^3{p}_{j2},1/3\sum _{j=1}^3{p}_{j3})\hfill \\ \hfill & =(1/\mathrm{3,1}/\mathrm{3,1}/3).\hfill \end{array}$$ The same argument shows that if $𝐏$ is an $n\times n$ transition matrix with columns that add to 1 then $$𝐰=(1/n,\cdots ,1/n)$$ is a fixed probability vector. For an ergodic chain this means the the average number of times in each state is $1/n$⁠.

In Example 11.11 of Section 11.1, the state $(GG,GG)$ is absorbing, and the same reasoning as in the immediately preceding answer applies to show that this chain is not ergodic.

The fixed vector is $𝐰=(a/(b+a),b/(b+a))$⁠. Thus in the long run a proportion $b/(b+a)$ of the people will be told that the President will run. The fact that this is independent of the starting state means it is independent of the decision that the President actually makes. (See Exercise 2 of Section 11.1)

It is clearly possible to go between any two states, so the chain is ergodic. From 0 it is possible to go to states 0, 2, and 4 only in an even number of steps, so the chain is not regular. For the general Erhrenfest Urn model the fixed vector must statisfy the following equations: $$\frac{1}{n}{w}_1=w_0,$$ $$w_{j+1}\frac{j+1}{n}+w_{j-1}\frac{n-j+1}{n}=w_j,\text{if }0<j<n,$$ $$\frac{1}{n}{w}_{n-1}=w_n.$$ It is easy to check that the binomial coefficients satisfy these conditions.

Consider the Markov chain whose state is the value of $S_{n}mod(7)$⁠, that is, the remainder when $S_n$ is divided by 7. Then the transition matrix for this chain is $$𝐏=\begin{array}{cc}0& \phantom{01/61/61/61/61/61/6}\\ 1& \phantom{1/601/61/61/61/61/6}\\ 2& \phantom{1/61/601/61/61/61/6}\\ 3& \phantom{1/61/61/601/61/61/6}\\ 4& \phantom{1/61/61/61/601/61/6}\\ 5& \phantom{1/61/61/61/61/601/6}\\ 6& \phantom{1/61/61/61/61/61/60}\end{array}\stackrel{\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6\\ \phantom{0}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}\\ \phantom{1/6}& \phantom{0}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}\\ \phantom{1/6}& \phantom{1/6}& \phantom{0}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}\\ \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{0}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}\\ \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{0}& \phantom{1/6}& \phantom{1/6}\\ \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{0}& \phantom{1/6}\\ \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{1/6}& \phantom{0}\end{array}}{\left(\begin{array}{ccccccc}\phantom{0}& \phantom{1}& \phantom{2}& \phantom{3}& \phantom{4}& \phantom{5}& \phantom{6}\\ 0& 1/6& 1/6& 1/6& 1/6& 1/6& 1/6\\ 1/6& 0& 1/6& 1/6& 1/6& 1/6& 1/6\\ 1/6& 1/6& 0& 1/6& 1/6& 1/6& 1/6\\ 1/6& 1/6& 1/6& 0& 1/6& 1/6& 1/6\\ 1/6& 1/6& 1/6& 1/6& 0& 1/6& 1/6\\ 1/6& 1/6& 1/6& 1/6& 1/6& 0& 1/6\\ 1/6& 1/6& 1/6& 1/6& 1/6& 1/6& 0\end{array}\right)}.$$ Since the column sums of this matrix are 1, the fixed vector is $$𝐰=(1/\mathrm{7,1}/\mathrm{7,1}/\mathrm{7,1}/\mathrm{7,1}/\mathrm{7,1}/\mathrm{7,1}/7).$$

(a) For the general chain it is possible to go from any state $i$ to any other state $j$ in $r^2-2r+2$ steps. We show how this can be done starting in state 1. To return to 1, circle $(\mathrm{1,2},..,r-\mathrm{1,1})$ $r-2$ times ($r^2-3r+2$ steps) and $(1,...,r,1)$ once ($r$ steps). For $k=1,...,r-1$ to reach state $k+1$⁠, circle $(\mathrm{1,2},\dots ,r,1)$ $r-k$ times ($r^2-rk$ steps) then $(\mathrm{1,2},\dots ,r-\mathrm{1,1})$ $k-2$ times ($rk-2r-k+2$ steps) and then move to $k+1$ in $k$ steps.You have taken $r^2-2r+2$ steps in all. The argument is the same for any other starting state with everything translated the appropriate amount.

(b) $$𝐏=\left(\begin{array}{ccc}0& \ast & 0\\ \ast & 0& \ast \\ \ast & 0& 0\end{array}\right),{𝐏}^2=\left(\begin{array}{ccc}\ast & 0& \ast \\ \ast & \ast & 0\\ 0& \ast & 0\end{array}\right),{𝐏}^3=\left(\begin{array}{ccc}\ast & \ast & 0\\ \ast & \ast & \ast \\ \ast & 0& \ast \end{array}\right),$$ $${𝐏}^4=\left(\begin{array}{ccc}\ast & \ast & \ast \\ \ast & \ast & \ast \\ \ast & \ast & 0\end{array}\right),{𝐏}^5=\left(\begin{array}{ccc}\ast & \ast & \ast \\ \ast & \ast & \ast \\ \ast & \ast & \ast \end{array}\right).$$

To each Markov chain we can associate a directed graph, whose vertices are the states $i$ of the chain, and whose edges are determined by the transition matrix: the graph has an edge from $i$ to $j$ if and only if $p_{ij}>0$⁠. Then to say that $𝐏$ is ergodic means that from any state $i$ you can find a path following the arrows until you reach any state $j$⁠. If you cut out all the loops in this path you will then have a path that never interesects itself, but still leads from $i$ to $j$⁠. This path will have at most $r-1$ edges, since each edge leads to a different state and none leads to $i$⁠. Following this path requires at most $r-1$ steps.

If $𝐏$ is ergodic it is possible to go between any two states. The same will be true for the chain with transition matrix $\frac{1}{2}(𝐈+𝐏)$⁠. But for this chain it is possible to remain in any state; therefore, by Exercise 26, this chain is regular.

(b) Since $𝐏$ has rational transition probabilities, when you solve for the fixed vector you will get a vector $𝐚$ with rational components. We can multiply through by a sufficiently large integer to obtain a fixed vector $𝐮$ with integer components such that each component of $𝐮$ is an integer multiple of the corresponding component of $𝐚$⁠. Let ${𝐚}^{(n)}$ be the vector resulting from the $n$⁠th iteration. Let ${𝐛}^{(n)}={𝐚}^{(n)}𝐏$⁠. Then ${𝐚}^{(n+1)}$ is obtained by adding chips to ${𝐛}^{(n+1)}$⁠. We want to prove that ${𝐚}^{(n+1)}\ge {𝐚}^{(n)}$⁠. This is true for $n=0$ by construction. Assume that it is true for $n$⁠. Then multiplying the inequality by $𝐏$ gives that ${𝐛}^{(n+1)}\ge {𝐛}^{(n)}$⁠. Consider the component $a_j^{(n+1)}$⁠. This is obtained by adding chips to $b_j^{(n+1)}$ until we get a multiple of $a_j$⁠. Since $b_j^{(n)}\le b_j^{(n+1)}$⁠, any multiple of $a_j$ that could be obtained in this manner to define $a_j^{(n+1)}$ could also have been obtained to define $a_j^{(n)}$ by adding more chips if necessary. Since we take the smallest possible multiple $a_j$⁠, we must have $a_j^{(n)}\le a_j^{n+1}$⁠. Thus the results after each iteration are monotone increasing. On the other hand, they are always less than or equal to $𝐮$⁠. Since there are only a finite number of integers between components of $𝐚$ and $𝐮$⁠, the iteration will have to stop after a finite number of steps.

If the maximum of a set of numbers is an average of other elements of the set, then each of the elements with positive weight in this average must also be maximum. By assumption, $𝐏𝐱=𝐱$⁠. This implies ${𝐏}^n𝐱=𝐱$ for all $n$⁠. Assume that $x_i=M$⁠, where $M$ is the maximum value for the $x_k$⁠’s, and let $j$ be any other state. Then there is an $n$ such that $p_{ij}^n>0$⁠. The $i$⁠th row of the equation ${𝐏}^n𝐱=𝐱$ presents $x_i$ as an average of values of $x_k$ with positive weight,one of which is $x_j$⁠. Thus $x_j=M$⁠, and $𝐱$ is constant.