Markov chains

Show that any sequence of independent random variables taking values in the countable set $S$ is a Markov chain. Under what condition is this chain homogeneous?

A die is rolled repeatedly. Which of the following are Markov chains? For those that are, supply the transition matrix.

Let $\left\{ S_{n}: n \geq 0\right\}$ be a simple random walk with $S_{0} = 0$, and show that $X_{n} = \left|S_{n}\right|$ defines a Markov chain; find the transition probabilities of this chain. Let $M_{n} = \max \left\{ S_{k}: 0 \leq k \leq n\right\}$, and show that $Y_{n} = M_{n}-S_{n}$ defines a Markov chain. What happens if $S_{0} \neq 0$?

Let $X$ be a Markov chain and let $\left\{ n_{r}: r \geq 0\right\}$ be an unbounded increasing sequence of positive integers. Show that $Y_{r} = X_{n_{r}}$ constitutes a (possibly non-homogeneous) Markov chain. Find the transition matrix of $Y$ when $n_{r} = 2 r$ and $X$ is:

Let $X$ be a Markov chain on $S$, and let $I: S^{n} \rightarrow \left\{ 0,1\right\}$. Show that the distribution of $X_{n}, X_{n+1}, \ldots$, conditional on $\left\{ I\left(X_{1}, \ldots , X_{n}\right) = 1\right\} \cap \left\{ X_{n} = i\right\}$, is identical to the distribution of $X_{n}, X_{n+1}, \ldots$ conditional on $\left\{ X_{n} = i\right\}$.

Let $X$ be a Markov chain on $S$, and let $T$ be a random variable taking values in $\left\{ 0,1,2, \ldots \right\}$ with the property that the indicator function $I_{\left\{ T = n\right\} }$, of the event that $T = n$, is a function of the variables $X_{1}, X_{2}, \ldots , X_{n}$. Such a random variable $T$ is called a stopping time, and the above definition requires that it is decidable whether or not $T = n$ with a knowledge only of the past and present, $X_{0}, X_{1}, \ldots , X_{n}$, and with no further information about the future.

Show that

for $m \geq 0, i, j \in S$, and all sequences $\left(x_{k}\right)$ of states.

Let $X$ be a Markov chain with state space $S$, and suppose that $h: S \rightarrow T$ is one-one. Show that $Y_{n} = h\left(X_{n}\right)$ defines a Markov chain on $T$. Must this be so if $h$ is not one-one?

Let $X$ and $Y$ be Markov chains on the set $\mathbb {Z}$ of integers.

Let $X$ be a Markov chain. Which of the following are Markov chains?

Let $X$ be a Markov chain. Show that, for $1 < r < n$,

Let $\left\{ X_{n}: n \geq 1\right\}$ be independent identically distributed integer-valued random variables. Let $S_{n} = \sum_{r = 1}^{n} X_{r}$, with $S_{0} = 0, Y_{n} = X_{n}+X_{n-1}$ with $X_{0} = 0$, and $Z_{n} = \sum_{r = 0}^{n} S_{r}$. Which of the following constitute Markov chains:

A stochastic matrix $\mathbf{P}$ is called doubly stochastic if $\sum_{i} p_{i j} = 1$ for all $j$. It is called sub-stochastic if $\sum_{i} p_{i j} \leq 1$ for all $j$. Show that, if $\mathbf{P}$ is stochastic (respectively, doubly stochastic, sub-stochastic), then $\mathbf{P}^{n}$ is stochastic (respectively, doubly stochastic, sub-stochastic) for all $n$.

Let $X$ be a Markov chain on the finite state space $S$ with transition matrix $\mathbf{P}$, and let $\mathcal{C} = \left\{ C_{j}: j \in J\right\}$ be a partition of $S$. Let $Y_{n} = j$ if $X_{n} \in C_{j}$. The chain $X$ is called $\mathcal{C}$-lumpable if $Y$ is a Markov chain.

Show that $X$ is $\mathcal{C}$-lumpable if and only if, for $a, b \in J, \mathbb {P}\left(X_{n+1} \in C_{b} \mid X_{n} = i\right)$ is constant for $i \in C_{a}$.

Let $l_{i j}(n) = \mathbb {P}\left(X_{n} = j, X_{k} \neq i \text{ for } 1 \leq k < n \mid X_{0} = i\right)$, the probability that the chain passes from $i$ to $j$ in $n$ steps without revisiting $i$. Writing

show that $P_{i j}(s) = P_{i i}(s) L_{i j}(s)$ if $i \neq j$. Deduce that the first passage times and last exit times have the same distribution for any Markov chain for which $P_{i i}(s) = P_{j j}(s)$ for all $i$ and $j$. Give an example of such a chain.

Let $X$ be a Markov chain containing an absorbing state $s$ with which all other states $i$ communicate, in the sense that $p_{i s}(n) > 0$ for some $n = n(i)$. Show that all states other than $s$ are transient.

Show that a state $i$ is recurrent if and only if the mean number of visits of the chain to $i$, having started at $i$, is infinite. That is to say, $i$ is recurrent if and only if $\sum_{n} p_{i i}(n) = \infty$.

Let $V_{j} = \left|\left\{ n \geq 1: X_{n} = j\right\} \right|$ be the number of visits of the Markov chain $X$ to $j$, and define $\eta_{i j} = \mathbb {P}_{i}\left(V_{j} = \infty \right)$. Show that:

The distinct pair $i, j$ of states of a Markov chain is called symmetric if

where $T_{i} = \min \left\{ n \geq 1: X_{n} = i\right\}$. Show that, if $X_{0} = i$ and $i, j$ is symmetric, the expected number of visits to $j$ before the chain revisits $i$ is 1. [Cf. the quotation following Theorem (3.10.18).]

Let $X$ be a Markov chain, and let $T$ be a geometric random variable with $\mathbb {P}\left(T > n\right) = s^{n}$ for $n \geq 0$, which is independent of $X$. By considering the expected number of visits by $X$ to a given state before time $T$, prove Theorem (6.2.3).

Let $X$ be an ergodic Markov chain started from $a$, and assume $X$ is irreducible (in that, for states $i, j$, there exists $m \geq 0$ such that $p_{i j}(m) > 0$). Let $a, b, c$ be distinct states, and let $T(a, b, \neg c)$ be the time until $X$ first visits $b$, with no intermediate visit to $c$. That is, if $X$ visits $b$ before $c$, then $T(a, b, \neg c)$ is that time, and if $X$ visits $c$ before $b$ we set $T(a, b, \neg c) = \infty$. Let

Show that

where, for example, $F_{a b}(s)$ is the probability generating function of the first passage time $T_{a b}$ from $a$ to $b$ irrespective of intermediate visits to $c$. Show further that

where, for example, $\mu_{a b} = \mathbb {E}_{a}\left[T_{a b}\right]$.

Let $X$ be a Markov chain on $\left\{ 0,1,2, \ldots \right\}$ with transition matrix given by $p_{0 j} = a_{j}$ for $j \geq 0$, $p_{i i} = r$ and $p_{i, i-1} = 1-r$ for $i \geq 1$. Classify the states of the chain, and find their mean recurrence times.

Determine whether or not the random walk on the integers having transition probabilities $p_{i, i+2} = p, p_{i, i-1} = 1-p$, for all $i$, is recurrent.

Classify the states of the Markov chains with transition matrices

A particle performs a random walk on the vertices of a cube. At each step it remains where it is with probability $\frac{1}{4}$, or moves to one of its neighbouring vertices each having probability $\frac{1}{4}$. Let $v$ and $w$ be two diametrically opposite vertices. If the walk starts at $v$, find:

With the notation of Exercise (6.2.4), show that

Let $T_{A} = \min \left\{ n \geq 0: X_{n} \in A\right\}$, where $X$ is a Markov chain and $A$ is a subset of the state space $S$, and let $\eta_{j} = \mathbb {P}_{j}\left(T_{A} < \infty \right)$. Show that

Show further that if $\mathbf{x} = \left(x_{j}: j \in S\right)$ is any non-negative solution of these equations then $x_{j} \geq \eta_{j}$ for all $j$.

In the notation of Exercise (6.3.6), let $\rho_{j} = \mathbb {E}_{j}\left[T_{A}\right]$. Show that

and that if $\mathbf{x} = \left(x_{j}: j \in S\right)$ is any non-negative solution of these equations then $x_{j} \geq \rho_{j}$ for all $j$.

Let $X$ be an irreducible Markov chain and let $A$ be a subset of the state space. Let $S_{r}$ and $T_{r}$ be the successive times at which the chain enters $A$ and visits $A$ respectively. Are the sequences $\left\{ X_{S_{r}}: r \geq 1\right\} ,\left\{ X_{T_{r}}: r \geq 1\right\}$ Markov chains? What can be said about the times at which the chain exits $A$?

An urn initially contains $n$ green balls and $n+2$ red balls. A ball is picked at random: if it is green then a red ball is also removed and both are discarded; if it is red then it is replaced together with an extra red and an extra green ball. This is repeated until there are no green balls in the urn. Show that the probability the process terminates is $1 /(n+1)$.

Now reverse the rules: if the ball is green, it is replaced together with an extra green and an extra red ball; if it is red it is discarded along with a green ball. Show that the expected number of iterations until no green balls remain is $\sum_{j = 1}^{n}(2 j+1) = n(n+2)$. [Thus, a minor perturbation of a simple symmetric random walk can be positive recurrent, whereas the original is null recurrent.]

The proof copy of a book is read by an infinite sequence of editors checking for mistakes. Each mistake is detected with probability $p$ at each reading; between readings the printer corrects the detected mistakes but introduces a random number of new errors (errors may be introduced even if no mistakes were detected). Assuming as much independence as usual, and that the numbers of new errors after different readings are identically distributed, find an expression for the probability generating function of the stationary distribution of the number $X_{n}$ of errors after the $n$th editor-printer cycle, whenever this exists. Find it explicitly when the printer introduces a Poisson-distributed number of errors at each stage.

Do the appropriate parts of Exercises (6.3.1)-(6.3.4) again, making use of the new techniques at your disposal. In particular, for Exercise (6.3.3):

Let $X_{n}$ be the amount of water in a reservoir at noon on day $n$. During the 24 hour period beginning at this time, a quantity $Y_{n}$ of water flows into the reservoir, and just before noon on each day exactly one unit of water is removed (if this amount can be found). The maximum capacity of the reservoir is $K$, and excessive inflows are spilled and lost. Assume that the $Y_{n}$ are independent and identically distributed random variables and that, by rounding off to some laughably small unit of volume, all numbers in this exercise are non-negative integers. Show that $\left(X_{n}\right)$ is a Markov chain, and find its transition matrix and an expression for its stationary distribution in terms of the probability generating function $G$ of the $Y_{n}$.

Find the stationary distribution when $Y$ has probability generating function $G(s) = p(1-q s)^{-1}$.

Show by example that chains which are not irreducible may have many different stationary distributions.

Let $\left(x_{i}(n): i, n \geq 1\right)$ be a bounded collection of real numbers.

Random walk on a graph. A particle performs a random walk on the vertex set of a connected graph $G$, which for simplicity we assume to have neither loops nor multiple edges. At each stage it moves to a neighbour of its current position, each such neighbour being chosen with equal probability. If $G$ has $\eta ( < \infty )$ edges, show that the stationary distribution is given by $\pi_{v} = d_{v} /(2 \eta )$, where $d_{v}$ is the degree of vertex $v$.

Show that a random walk on the infinite binary tree is transient.

At each time $n = 0,1,2, \ldots$ a number $Y_{n}$ of particles enters a chamber, where $\left\{ Y_{n}: n \geq 0\right\}$ are independent and Poisson distributed with parameter $\lambda$. Lifetimes of particles are independent and geometrically distributed with parameter $p$. Let $X_{n}$ be the number of particles in the chamber at time $n$. Show that $X$ is a Markov chain, and find its stationary distribution.

A random sequence of convex polygons is generated by picking two edges of the current polygon at random, joining their midpoints, and picking one of the two resulting smaller polygons at random to be the next in the sequence. Let $X_{n}+3$ be the number of edges of the $n$th polygon thus constructed. Find $\mathbb {E}\left[X_{n}\right]$ in terms of $X_{0}$, and find the stationary distribution of the Markov chain $X$.

Let $s$ be a state of an irreducible Markov chain on the non-negative integers. Show that the chain is recurrent if there exists a solution $\mathbf{y}$ to the equations $y_{i} \geq \sum_{j: j \neq s} p_{i j} y_{j}, i \neq s$, satisfying $y_{i} \rightarrow \infty$.

A particle performs a random walk on a bow tie ABCDE drawn beneath on the left, where C is the knot. From any vertex its next step is equally likely to be to any neighbouring vertex. Initially it is at A. Find the expected value of:

A particle starts at A and executes a symmetric random walk on the graph drawn above on the right. Find the expected number of visits to $B$ before it returns to $A$.

A pack contains 52 cards labelled $1,2, \ldots , 52$, and initially they are in increasing order from top to bottom. At each stage of the shuffling process, the top card is moved to one of the 52 available places determined by the other 51 cards, this place being chosen uniformly at random, independently of all previous stages. Find the mean number of stages until card 52 is first on top.

Show that, after the moment at which the card labelled 52 is inserted at random from the top, the order of the pack is uniformly distributed over the 52! possibilities.

A pack contains 52 cards labelled $1,2, \ldots , 52$, and initially they are in increasing order from top to bottom. At each stage, a card is picked uniformly at random from the pack and placed on top, independently of all previous stages. Find the mean number of stages until every card has been selected at least once.

Show that, after the moment at which the final card to be selected at random is placed on top, the order of the pack is uniformly distributed over the 52! possibilities.

Dick and Jim are writing exercises in sequence for inclusion in a textbook. Dick writes them and Jim checks them. Each exercise is faulty with probability $p$, independently of other exercises. Jim has two modes of operation. In Mode A, he inspects every exercise as it is produced. In Mode B, he inspects each exercise with probability $1 / r$ where $r > 1$, independently of all other events.

Let $N \geq 1$. Jim operates in Mode A until he has found $N$ consecutive non-defective exercises, at which point he changes to Mode B. He operates in Mode B until the first defective exercise is found, and then he reverts to Mode A.

Let $X$ be the Markov chain which is in state $i$ if Jim is operating in Mode A and the last $i$ consecutive exercises since entering Mode A have been found to be non-defective, and is in state $N$ if Jim is in Mode B.

A particle performs a random walk on the non-negative integers as follows. When at position $k \geq 0$, its next position is uniformly distributed on the set $\left\{ 0,1, \ldots , k, k+1\right\}$. Show that the sequence of positions forms an aperiodic, positive recurrent Markov chain, and find its stationary distribution.

Find the mean number $\mu$ of steps required to reach position 0 for the first time from position 1.

Let $\left\{ X_{n}: n \geq 0\right\}$ be an irreducible Markov chain with state space $S$ and transition matrix $\mathbf{P}$ (the chain may be either transient or recurrent). Let $k \in S$ and let $\mathbf{x}$ be a stationary measure such that $x_{k} = 1$. Prove that $\mathbf{x} \geq \rho (k)$ where $\rho (k)$ is given in equation (6.4.5). If the chain is recurrent, show that $\mathbf{x} = \rho (k)$.

A random walk on the set $\left\{ 0,1,2, \ldots , b\right\}$ has transition matrix given by $p_{00} = 1-\lambda_{0}, p_{b b} = 1-\mu_{b}, p_{i, i+1} = \lambda_{i}$ and $p_{i+1, i} = \mu_{i+1}$ for $0 \leq i < b$, where $0 < \lambda_{i}, \mu_{i} < 1$ for all $i$, and $\lambda_{i}+\mu_{i} = 1$ for $1 \leq i < b$. Show that this process is reversible in equilibrium.

Let $X$ be an irreducible, positive recurrent, aperiodic Markov chain on the state space $S$.

Let $X$ be a reversible Markov chain, and let $C$ be a non-empty subset of the state space $S$. Define the Markov chain $Y$ on $S$ by the transition matrix $\mathbf{Q} = \left(q_{i j}\right)$ where

for $i \neq j$, and where $\beta$ is a constant satisfying $0 < \beta < 1$. The diagonal terms $q_{i i}$ are arranged so that $\mathbf{Q}$ is a stochastic matrix. Show that $Y$ is reversible in equilibrium, and find its stationary distribution. Describe the situation in the limit as $\beta \downarrow 0$.

Can a reversible chain be periodic?

The dog-flea model of Example (6.5.5) is a Markov chain $X$ on the state space $\left\{ 0,1, \ldots , m\right\}$ with transition probabilities

Show that, if $X_{0} = i$,

Which of the following (when stationary) are reversible Markov chains?

Let $X_{n}, Y_{n}$ be independent simple random walks. Let $Z_{n}$ be $(X_{n}, Y_{n})$ truncated to lie in the region $X_{n} \geq 0, Y_{n} \geq 0, X_{n}+Y_{n} \leq a$ where $a$ is integral. Find the stationary distribution of $Z_{n}$.

Show that an irreducible Markov chain with a finite state space and transition matrix $\mathbf{P}$ is reversible in equilibrium if and only if $\mathbf{P} = \mathbf{D S}$ for some symmetric matrix $\mathbf{S}$ and diagonal matrix $\mathbf{D}$ with strictly positive diagonal entries. Show further that for reversibility in equilibrium to hold, it is necessary but not sufficient that $\mathbf{P}$ has real eigenvalues.

Random walk on a graph. Let $G$ be a finite connected graph with neither loops nor multiple edges, and let $X$ be a random walk on $G$ as in Exercise (6.4.6). Show that $X$ is reversible in equilibrium.

Consider a random walk on the strictly positive integers with transition probabilities

and $p_{11} = \frac{3}{4}, p_{12} = \frac{1}{4}$. Show that the walk is positive recurrent and find the mean recurrence time of the state $i$.

An aleatory beetle performs a random walk on five vertices comprising the principal points (labelled $n, e, s, w$) and centre (labelled $c$) of a compass, with transition probabilities

Other moves have probability 0. Show that the mean recurrence time of the centre is $\mu_{c} = \frac{11}{2}$.

Let $X$ be an irreducible (but not necessarily aperiodic) Markov chain on the countable state space $S$ with transition matrix $\mathbf{P}$, with invariant distribution $\pi$. Let $a \in (0,1)$ and let $\mathbf{L} = a \mathbf{P}+(1-a) \mathbf{I}$ where $\mathbf{I}$ is the identity matrix.

The Markov-Kakutani theorem asserts that, for any convex compact subset $C$ of $\mathbb {R}^{n}$ and any linear continuous mapping $T$ of $C$ into $C, T$ has a fixed point (in the sense that $T(x) = x$ for some $x \in C$). Use this to prove that a finite stochastic matrix has a non-negative non-zero left eigenvector corresponding to the eigenvalue 1.

Let $\mathbf{T}$ be a $m \times n$ matrix and let $\mathbf{v} \in \mathbb {R}^{n}$. Farkas's theorem asserts that exactly one of the following holds:

(i) there exists $\mathbf{x} \in \mathbb {R}^{m}$ such that $\mathbf{x} \geq \mathbf{0}$ and $\mathbf{x} \mathbf{T} = \mathbf{v}$,

(ii) there exists $\mathbf{y} \in \mathbb {R}^{n}$ such that $\mathbf{y v}^{\prime } < 0$ and $\mathbf{T y}^{\prime } \geq \mathbf{0}$.

Use this to prove that a finite stochastic matrix has a non-negative non-zero left eigenvector corresponding to the eigenvalue 1.

Suppose you are betting on a race with $m$ possible outcomes. There are $n$ bookmakers, and a unit stake with the $i$ th bookmaker yields $t_{i j}$ if the $j$ th outcome of the race occurs. A vector $\mathbf{x} = \left(x_{1}, x_{2}, \ldots , x_{n}\right)$, where $x_{r} \in (-\infty , \infty )$ is your stake with the $r$ th bookmaker, is called a betting scheme. Show that exactly one of (a) and (b) holds:

(a) there exists a probability mass function $\mathbf{p} = \left(p_{1}, p_{2}, \ldots , p_{m}\right)$ such that $\sum_{j = 1}^{m} t_{i j} p_{j} = 0$ for all values of $i$,

(b) there exists a betting scheme $\mathbf{x}$ for which you surely win, that is, $\sum_{i = 1}^{n} x_{i} t_{i j} > 0$ for all $j$.

Let $X$ be a Markov chain with state space $S = \left\{ 1,2,3\right\}$ and transition matrix

where $0 < p < 1$. Prove that

where $a_{1 n}+\omega a_{2 n}+\omega^{2} a_{3 n} = (1-p+p \omega )^{n}, \omega$ being a complex cube root of 1.

Let $\mathbf{P}$ be the transition matrix of a Markov chain with finite state space. Let $\mathbf{I}$ be the identity matrix, $\mathbf{U}$ the $\left|S\right| \times \left|S\right|$ matrix with all entries unity, and $\mathbf{1}$ the row $\left|S\right|$-vector with all entries unity. Let $\mathbf{\pi }$ be a non-negative vector with $\sum_{i} \pi_{i} = 1$. Show that $\mathbf{\pi } \mathbf{P} = \mathbf{\pi }$ if and only if $\mathbf{\pi }(\mathbf{I}-\mathbf{P}+\mathbf{U}) = \mathbf{1}$. Deduce that if $\mathbf{P}$ is irreducible then $\mathbf{\pi } = \mathbf{1}(\mathbf{I}-\mathbf{P}+\mathbf{U})^{-1}$.

A chess piece performs a random walk on a chessboard; at each step it is equally likely to make any one of the available moves. What is the mean recurrence time of a corner square if the piece is a:

A rook and a bishop perform independent symmetric random walks with synchronous steps on a $4 \times 4$ chessboard (16 squares). If they start together at a corner, show that the expected number of steps until they meet again at the same corner is $448 / 3$.

Find the $n$-step transition probabilities $p_{i j}(n)$ for the chain $X$ having transition matrix

The pages on the worldwide web form a directed graph $W$ with $n$ vertices (representing pages) joined by directed edges (representing links). The existence of a link from $i$ to $j$ is denoted by $i \rightarrow j$, and the graph is specified by its adjacency matrix $L = \left(l_{i j}\right)$ where $l_{i j} = 1$ if $i \rightarrow j$ and $l_{i j} = 0$ otherwise. The out-degree $d_{i}$ (respectively, in-degree $c_{i}$) of vertex $i$ is the number of links pointing away from $i$ (respectively, towards $i$). Vertex $i$ is said to dangle if $d_{i} = 0$.