Finite-state Markov chains

If state $i_{1}$ is transient, then there is some other state $i_{2}$ such that $i_{1} \rightarrow i_{2}$ and $i_{2} \not\rightarrow i_{1}$.

If the $i_{2}$ of (a) is also transient, there is a third state $i_{3}$ such that $i_{2} \rightarrow i_{3}$, $i_{3} \not\rightarrow i_{2}$; that state must satisfy $i_{3} \neq i_{2}$, $i_{3} \neq i_{1}$.

Continue iteratively to repeat (b) for successive states, $i_{1}, i_{2}, \ldots$. That is, if $i_{1}, \ldots , i_{k}$ are generated as above and are all transient, generate $i_{k+1}$ such that $i_{k} \rightarrow i_{k+1}$ and $i_{k+1} \not\rightarrow i_{k}$. Then $i_{k+1} \neq i_{j}$ for $1 \leq j \leq k$.

Show that for some $k \leq \mathsf{M}$, $k$ is not transient, i.e., it is recurrent, so a recurrent class exists.

Show that an ergodic Markov chain with $\mathsf{M} > 1$ states must contain a cycle with $\tau < \mathsf{M}$ states. Hint: Use ergodicity to show that the smallest cycle cannot contain $\mathsf{M}$ states.

Let $\ell$ be a fixed state on this cycle of length $\tau$. Let $\mathcal{T}(m)$ be the set of states accessible from $\ell$ in $m$ steps. Show that for each $m \geq 1$, $\mathcal{T}(m) \subseteq \mathcal{T}(m + \tau )$. Hint: For any given state $j \in \mathcal{T}(m)$, show how to construct a walk of $m + \tau$ steps from $\ell$ to $j$ from the assumed walk of $m$ steps.

Define $\mathcal{T}(0)$ to be the singleton set $\left\{ \ell \right\}$ and show that

Show that if one of the inclusions above is satisfied with equality, then all subsequent inclusions are satisfied with equality. Show from this that at most the first $\mathsf{M} - 1$ inclusions can be satisfied with strict inequality and that $\mathcal{T}(n\tau ) = \mathcal{T}((\mathsf{M}-1)\tau )$ for all $n \geq \mathsf{M} - 1$.

Show that all states are included in $\mathcal{T}((\mathsf{M}-1)\tau )$.

Show that $P_{ij}^{(\mathsf{M}-1)^{2}+1} > 0$ for all $i, j$.

Let $\tau$ be the number of states in the smallest cycle of an arbitrary ergodic Markov chain of $\mathsf{M} \geq 3$ states. Show that $P_{ij}^{n} > 0$ for all $n \geq (\mathsf{M}-2)\tau + \mathsf{M}$. Hint: Look at the proof of Theorem 4.2.11 in Exercise 4.5.

For $\tau = 1$, draw the graph of an ergodic Markov chain (generalized for arbitrary $\mathsf{M} \geq 3$) for which there is an $i,j$ for which $P_{ij}^{n} = 0$ for $n = 2\mathsf{M}-3$. Hint: Look at Figure 4.4.

For arbitrary $\tau < \mathsf{M}-1$, draw the graph of an ergodic Markov chain (generalized for arbitrary $\mathsf{M}$) for which there is an $i,j$ for which $P_{ij}^{n} = 0$ for $n = (\mathsf{M}-2)\tau + \mathsf{M}-1$. Assume that $\mathsf{M}$ and $\tau$ are relatively prime.

Find the steady-state probabilities $\pi_{0}, \ldots , \pi_{k-1}$ for the Markov chain below. Express your answer in terms of the ratio $\rho = p/q$, where $q = 1-p$. Pay particular attention to the special case $\rho = 1$.

[width=0.9figs/figs_original/ch4_ex9.png

Sketch $\pi_{0}, \ldots , \pi_{k-1}$. Give one sketch for $\rho = 1/2$, one for $\rho = 1$, and one for $\rho = 2$.

Find the limit of $\pi_{0}$ as $k$ approaches $\infty$; give separate answers for $\rho < 1$, $\rho = 1$, and $\rho > 1$. Find limiting values of $\pi_{k-1}$ for the same cases.

Find the steady-state probabilities for each of the Markov chains in the figure below. Assume that all clockwise probabilities in the first graph are the same, say $p$, and assume that $P_{4,5} = P_{4,1}$ in the second graph.

[width=0.85figs/figs_original/ch4_ex10.png

Find the matrices $[P^{2}]$ for the same chains. Draw the graphs for the Markov chains represented by $[P^{2}]$, i.e., the graph of two step transitions for the original chains. Find the steady-state probabilities for these two-step chains. Explain why your steady-state probabilities are not unique.

Find $\lim_{n \rightarrow \infty }[P^{2n}]$ for each of the chains.

Assume that $\nu^{(i)}$ is a right eigenvector and $\pi^{(j)}$ is a left eigenvector of an $\mathsf{M} \times \mathsf{M}$ stochastic matrix $[P]$ where $\lambda_{i} \neq \lambda_{j}$. Show that $\pi^{(j)}\nu^{(i)} = 0$. Hint: Consider two ways of finding $\pi^{(j)}[P]\nu^{(i)}$.

Assume that $[P]$ has $\mathsf{M}$ distinct eigenvalues. The right eigenvectors of $[P]$ then span $\mathsf{M}$ space (see Section 5.2 of Strang [28]), so the matrix $[U]$ with those eigenvectors as columns is non-singular. Show that $U^{-1}$ is a matrix whose rows are the $\mathsf{M}$ left eigenvectors of $[P]$. Hint: Use (a).

For any given integer $i \in \left\{ 1, \mathsf{M}\right\}$, let $[A]$ be a diagonal matrix with a single non-zero element, $A_{ii} = a \neq 0$. Using the assumptions and results of (b), show that

Hint: Visualize straightforward vector/matrix multiplication.

Verify $(4.30)$ (referenced here; restated: $[U\Lambda^{n}U^{-1}] = \sum_{i=1}^{\mathsf{M}} \lambda_{i}^{n}\nu^{(i)}\pi^{(i)}$, where $[\Lambda ]$ is the diagonal matrix of eigenvalues $\lambda_{i}$ of $[P]$).

Let $\lambda_{k}$ be an eigenvalue of a stochastic matrix $[P]$ and let $\pi^{(k)}$ be a left eigenvector for $\lambda_{k}$. Show that for each component $\pi_{j}^{(k)}$ of $\pi^{(k)}$ and each $n$ that

By taking magnitudes of each side and looking at the appropriate $j$, show that

Show that $\left|\lambda_{k}\right| \leq 1$.

Find $[P^{n}]$ in closed form for arbitrary $n > 1$.

Find all distinct eigenvalues and the multiplicity of each distinct eigenvalue for $[P]$.

Find a right eigenvector for each distinct eigenvalue, and show that the eigenvalue of multiplicity 2 does not have two linearly independent eigenvectors.

Use (c) to show that there is no diagonal matrix $[\Lambda ]$ and no invertible matrix $[U]$ for which $[P][U] = [U][\Lambda ]$.

Rederive the result of (d) using the result of (a) rather than (c).

Let $[J_{i}]$ be a 3 by 3 block of a Jordan form, i.e.,

Show that the $n$th power of $[J_{i}]$ is given by

Hint: Perhaps the easiest way is to calculate $[J_{i}^{2}]$ and $[J_{i}^{3}]$ and then use iteration.

Generalize (a) to a $k \times k$ block of a Jordan form. Note that the $n$th power of an entire Jordan form is composed of these blocks along the diagonal of the matrix.

Let $[P]$ be a stochastic matrix represented by a Jordan form $[J]$ as $[P] = [U][J][U^{-1}]$ and consider $[U^{-1}][P^{n}][U] = [J]$ (i.e., $[U^{-1}][P][U] = [J]$). Show that any repeated eigenvalue of $[P]$ (and, in particular, any eigenvalue represented by a Jordan block of $2 \times 2$ or more) must be strictly less than 1. Hint: Upper bound the elements of $[U^{-1}][P^{n}][U]$ by taking the magnitude of the elements of $[U]$ and $[U^{-1}]$ and upper bounding each element of a stochastic matrix by 1.

Let $\lambda_{s}$ be the eigenvalue of largest magnitude less than 1. Assume that the Jordan blocks for $\lambda_{s}$ are at most of size $k$. Show that each ergodic class of $[P]$ converges at least as fast as $n^{k}\lambda_{s}^{n}$.

Let $\lambda$ be an eigenvalue of a matrix $[A]$, and let $\nu$ and $\pi$ be right and left eigenvectors respectively of $\lambda$, normalized so that $\pi \nu = 1$. Show that

Show that $[[A^{n}] - \lambda^{n}\nu \pi ][[A] - \lambda \nu \pi ] = [A^{n+1}] - \lambda^{n+1}\nu \pi$.

Use induction to show that $[[A] - \lambda \nu \pi ]^{n} = [A^{n}] - \lambda^{n}\nu \pi$.

Show that $[P^{n}]$ can be partitioned as

That is, the blocks on the diagonal are simply products of the corresponding blocks of $[P]$, and the upper right block is whatever it turns out to be.

Let $q_{i}$ be the probability that the chain will be in a recurrent state after $t$ transitions, starting from state $i$, i.e., $q_{i} = \sum_{j \in \mathcal{R}} P_{ij}^{t}$. Show that $q_{i} > 0$ for all transient $i$.

Let $q$ be the minimum $q_{i}$ over all transient $i$ and show that $P_{ij}^{nt} \leq (1-q)^{n}$ for all transient $i,j$ (i.e., show that $[P_{\mathcal{T}}^{n}]$ approaches the all zero matrix $[0]$ with increasing $n$).

Let $\pi = (\pi_{\mathcal{T}}, \pi_{\mathcal{R}})$ be a left eigenvector of $[P]$ of eigenvalue 1. Show that $\pi_{\mathcal{T}} = \overrightarrow {0}$ and show that $\pi_{\mathcal{R}}$ must be positive and be a left eigenvector of $[P_{\mathcal{R}}]$. Thus show that $\pi$ exists and is unique (within a scale factor).

Show that $\overrightarrow {e}$ is the unique right eigenvector of $[P]$ of eigenvalue 1 (within a scale factor).

$[P]$ has exactly $\kappa$ linearly independent left eigenvectors, $\pi^{(1)}, \pi^{(2)}, \ldots , \pi^{(\kappa )}$ of eigenvalue 1, and that the $m$th can be taken as a probability vector that is positive on the $m$th recurrent class and zero elsewhere.

$[P]$ has exactly $\kappa$ linearly independent right eigenvectors, $\nu^{(1)}, \nu^{(2)}, \ldots , \nu^{(\kappa )}$ of eigenvalue 1, and the $m$th can be taken as a vector with $\nu_{i}^{(m)}$ equal to the probability that recurrent class $m$ will ever be entered starting from state $i$.

Show that

Show that $[P^{d}]$ has the form

where $[Q_{m}] = [P_{m}][P_{m+1}] \cdots [P_{d-1}][P_{0}] \cdots [P_{m-1}]$. Expressing $[Q_{m}]$ as an $\mathsf{M} \times \mathsf{M}$ matrix $[Q_{m}']$ whose entries are 0 except for the rows and columns of $\mathcal{S}_{m}$ where the entries are equal to those of $[Q_{m}]$, this becomes $[P^{d}] = \sum_{m=0}^{d-1}[Q_{m}']$.

Show that $[Q_{m}]$ is the matrix of an ergodic Markov chain and let its eigenvector of eigenvalue 1 (scaled to be a probability vector) be $\hat{\pi }_{m}$ and let $\hat{\nu }_{m}$ be the corresponding right eigenvector scaled so that $\hat{\pi }_{m}\hat{\nu }_{m} = 1$. Let $\hat{\pi }_{m}'$ and $\hat{\nu }_{m}'$ be the corresponding $\mathsf{M}$-vectors. Show that $\lim_{n \rightarrow \infty }[P^{nd}] = \sum_{m=0}^{d-1} \hat{\nu }_{m}'\hat{\pi }_{m}'$.

Show that $\hat{\pi }_{m}'[P_{m}'] = \hat{\pi }_{m+1}'$. Note that $\hat{\pi }_{m}'$ is an $\mathsf{M}$-tuple that is non-zero only on the components of $\mathcal{S}_{m}$.

Let $\phi = 2\pi \sqrt{-1}/d$ and let $\pi^{(k)} = \sum_{m=0}^{d-1} \hat{\pi }_{m}'e^{mk\phi }$. Show that $\pi^{(k)}$ is a left eigenvector of $[P]$ of eigenvalue $e^{-\phi k}$.

Show that, with the eigenvectors defined in Exercise 4.19,

where, as before, $(d-1)+1$ is taken to be 0.

Show that, for $1 \leq j < d$,

Show that

Show that

where $\pi$ is the steady-state probability vector for $[P]$. Hint: Show that $\overrightarrow {e} = \sum_{m} \nu^{(m)}$ and $\pi = (1/d)\sum_{m} \pi^{(m)}$.

Show that the above result is also valid for periodic unichains.

Assume that $\epsilon > 0$, $\delta = 0$ (i.e., that $A$ is a set of transient states in the combined chain). Starting in state $A_{1}$, find the conditional expected time to return to $A_{1}$ given that the first transition is to some state in chain $A$.

Assume that $\epsilon > 0$, $\delta = 0$. Find $T_{A,B}$, the expected time to first reach state $B_{1}$ starting from state $A_{1}$. Your answer should be a function of $\epsilon$ and the original steady-state probabilities $\left\{ \pi_{A_{i}}\right\}$ in chain $A$.

Assume $\varepsilon > 0$, $\delta > 0$. Find $T_{B,A}$, the expected time to first reach state $A_{1}$, starting in state $B_{1}$. Your answer should depend only on $\delta$ and $\left\{ \pi_{B_{i}}\right\}$.

Assume $\varepsilon > 0$ and $\delta > 0$. Find $P'(A)$, the steady-state probability that the combined chain is in one of the states $\left\{ A_{j}\right\}$ of the original chain $A$.

Assume $\varepsilon > 0$, $\delta = 0$. For each state $A_{j} \neq A_{1}$ in $A$, find $v_{A_{j}}$, the expected number of visits to state $A_{j}$, starting in state $A_{1}$, before reaching $B_{1}$. Your answer should depend only on $\varepsilon$ and $\left\{ \pi_{A_{i}}\right\}$.

Assume $\varepsilon > 0$, $\delta > 0$. For each state $A_{j}$ in $A$, find $\pi_{A_{j}}'$, the steady-state probability of being in state $A_{j}$ in the combined chain. Hint: Be careful in your treatment of state $A_{1}$.

For the chain on the left side of Figure 4.6 (a four-state recurrent Markov chain, restated below), draw the graph for the modified chain with five states where state 1 has been split into two states.

[width=0.5figs/figs_original/ch4_fig46.png

Suppose one has found the expected first-passage times $v_{j}$ for states $j = 2, \ldots , 4$ (or in general from 2 to $\mathsf{M}$). Find an expression for $v_{1}$, the expected first recurrence time for state 1 in terms of $v_{2}, v_{3}, \ldots v_{\mathsf{M}}$ and $P_{12}, \ldots , P_{1\mathsf{M}}$.

Assume throughout that $[P]$ is the transition matrix of a unichain (and thus the eigenvalue 1 has multiplicity 1). Show that a solution to the equation $[P]\overrightarrow {w} - \overrightarrow {w} = \overrightarrow {r} - g\overrightarrow {e}$ exists if and only if $\overrightarrow {r} - g\overrightarrow {e}$ lies in the column space of $[P-I]$, where $[I]$ is the identity matrix.

Show that this column space is the set of vectors $\overrightarrow {x}$ for which $\pi \overrightarrow {x} = 0$. Then show that $\overrightarrow {r} - g\overrightarrow {e}$ lies in this column space.

Show that, with the extra constraint that $\pi \overrightarrow {w} = 0$, the equation $[P]\overrightarrow {w} - \overrightarrow {w} = \overrightarrow {r} - g\overrightarrow {e}$ has a unique solution.

Find the solution to $(4.37)$ (referenced here; restated: the relative-gain equation $\overrightarrow {w} + g\overrightarrow {e} = [P]\overrightarrow {w} + \overrightarrow {r}$, together with the normalization $\pi \overrightarrow {w}=0$) and find the gain $g$.

Modify the figure above by letting $P_{12}$ be an arbitrary probability. Find $g$ and $\overrightarrow {w}$ again and give an intuitive explanation of why $P_{12}$ affects $w_{2}$.

Show that the gain per stage $g$ is 0. Hint: Show that $\overrightarrow {r}$ is zero where the steady-state vector $\pi$ is non-zero.

Let $[P_{\mathcal{R}}]$ be the transition matrix for the recurrent states and let $\overrightarrow {r}_{\mathcal{R}} = 0$ be the reward vector and $\overrightarrow {w}_{\mathcal{R}}$ the relative-gain vector for $[P_{\mathcal{R}}]$. Show that $\overrightarrow {w}_{\mathcal{R}} = 0$. Hint: Use Theorem 4.5.4.

Show that $w_{i} = 0$ for all $i \in \mathcal{R}$. Hint: Compare the relative-gain equations for $[P]$ to those for $[P_{\mathcal{R}}]$.

Show that for each $n \geq 0$, $[P^{n}]\overrightarrow {w} = [P^{n+1}]\overrightarrow {w} + [P^{n}]\overrightarrow {r}$. Hint: Start with the relative-gain equation for $[P]$.

Show that $\overrightarrow {w} = [P^{n+1}]\overrightarrow {w} + \sum_{m=0}^{n}[P^{m}]\overrightarrow {r}$. Hint: Sum the result in (d).

Show that $\lim_{n \rightarrow \infty }[P^{n+1}]\overrightarrow {w} = 0$ and that $\lim_{n \rightarrow \infty }\sum_{m=0}^{n}[P^{m}]\overrightarrow {r}$ is finite, non-negative, and has positive components for $r_{i} > 0$. Hint: Use Lemma 4.3.6.

Demonstrate the final result of the corollary by using the previous results on $\overrightarrow {r} = \overrightarrow {r}' - \overrightarrow {r}''$.

Suppose the chain is started in state $i$ and goes through $n$ transitions; let $v_{i}(n)$ be the expected number of transitions (out of the total of $n$) until the chain enters the trapping state, state 1. Find an expression for $\overrightarrow {v}(n) = (v_{1}(n), v_{2}(n), v_{3}(n))^{\mathsf{T}}$ in terms of $\overrightarrow {v}(n-1)$ (take $v_{1}(n) = 0$ for all $n$). Hint: View the system as a Markov reward system; what is the value of $\overrightarrow {r}$?

Find the numerical value of $\lim_{n \rightarrow \infty } \overrightarrow {v}(n)$. Interpret the meaning of the elements $v_{i}$ in the solution of $(4.32)$.

Give a direct argument why $(4.32)$ provides the solution directly to the expected time from each state to enter the trapping state.

Show that $(4.48)$ (referenced here; restated: the dynamic-programming recursion $v_{i}^{*}(n, \overrightarrow {u}) = \max_{\overrightarrow {k}} \left(r_{i}^{(k)} + \sum_{j} P_{ij}^{(k)}v_{j}^{*}(n-1,\overrightarrow {u})\right)$, in vector form $\overrightarrow {v}^{*}(n,\overrightarrow {u}) = \max_{\overrightarrow {k}}\left(\overrightarrow {r}^{\overrightarrow {k}} + [P^{(\overrightarrow {k})}]\overrightarrow {v}^{*}(n-1,\overrightarrow {u})\right)$) can be rewritten in the more compact form

Explain why it is also true that

One might guess that (A.63) could be used iteratively, finding $\overrightarrow {v}^{*}(2^{n+1}, \overrightarrow {u})$ from $\overrightarrow {v}^{*}(2^{n}, \overrightarrow {u})$. Explain why this is not possible in any straightforward way. Hint: Think through explicitly how one might calculate $\overrightarrow {v}^{*}(n, \overrightarrow {v}^{*}(n, \overrightarrow {u}))$ from $\overrightarrow {v}^{*}(n, \overrightarrow {u})$.

Following the procedure in Example 4.5.1, draw the 3 state Markov chain for the string $(0,1)$. Find the expected number of trials until the first occurrence of that string.

For (b) and (c), let $(a_{1}, a_{2}, a_{3}, \ldots , a_{k}) = (0,1,1,\ldots ,1)$, i.e., zero followed by $k-1$ ones. Draw the corresponding Markov chain for $k = 4$.

Let $v_{i}$, $1 \leq i \leq k$ be the expected first-passage time from state $i$ to state $k$. Note that $v_{k} = 0$. For each $i$, $1 \leq i < k$, show that $v_{i} = \alpha_{i} + v_{i+1}$ and $v_{0} = \beta_{i} + v_{i+1}$ where $\alpha_{i}$ and $\beta_{i}$ are each expressed as a product of powers of $p_{0}$ and $p_{1}$. Hint: use induction on $i$ using $i=1$ as the base. For the inductive step, first find $\beta_{i+1}$ as a function of $\beta_{i}$ starting with $i=1$ and using the equation $v_{0} = 1/p_{0} + v_{1}$.

Let $\overrightarrow {a} = (0,1,0)$. Draw the corresponding Markov chain for this string. Evaluate $v_{0}$, the expected time for $(0,1,0)$ to occur.

Find $\lim_{n \rightarrow \infty }[P^{n}]$ for the Markov chain below. Hint: Think in terms of the long term transition probabilities. Recall that the edges in the graph for a Markov chain correspond to the positive transition probabilities.

[width=0.35figs/figs_original/ch4_ex29.png

Let $\pi^{(1)}$ and $\pi^{(2)}$ denote the first two rows of $\lim_{n \rightarrow \infty }[P^{n}]$ and let $\nu^{(1)}$ and $\nu^{(2)}$ denote the first two columns of $\lim_{n \rightarrow \infty }[P^{n}]$. Show that $\pi^{(1)}$ and $\pi^{(2)}$ are independent left eigenvectors of $[P]$, and that $\nu^{(1)}$ and $\nu^{(2)}$ are independent right eigenvectors of $[P]$. Find the eigenvalue for each eigenvector.

Let $\overrightarrow {r}$ be an arbitrary reward vector and consider the equation