Math Problems Vault

Problem 6.5.1

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.

?

Problem 6.5.2

(a)(b)(c)(d)

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

?

(a)

Kolmogorov's reversibility criterion. Show that $X$ is reversible in equilibrium if and only if

p_{j_{1}, j_{2}} p_{j_{2}, j_{3}} \cdots p_{j_{n-1}, j_{n}} p_{j_{n}, j_{1}} = p_{j_{1}, j_{n}} p_{j_{n}, j_{n-1}} \cdots p_{j_{2}, j_{1}}

for all $n$ and all finite sequences $j_{1}, j_{2}, \ldots , j_{n}$ of states.

(b)

Kelly's reversibility condition. Show that $X$ is reversible in equilibrium if, for all distinct triples $i, j, k \in S$ ,

p_{i j} p_{j k} p_{k i} = p_{i k} p_{k j} p_{j i}

and in addition there exists $c \in S$ such that $p_{i c} > 0$ for all $i \neq c$ .

(c)

Consider a chain with $n \geq 3$ states. Show that Kolmogorov's criterion, as expressed above, may require the verification of up to $\frac{1}{2} \sum_{r = 3}^{n}\binom {n}{r}(r-1)$ ! equations, whereas Kelly's condition, if appropriate, requires no more than $\binom {n-1}{3}$ .

(d)

Show that a random walk on a finite tree is reversible in equilibrium.

Problem 6.5.3

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

q_{i j} = \begin{cases} \beta p_{i j} & \text{ if } i \in C \text{ and } j \notin C, \\ p_{i j} & \text{ otherwise, }\end{cases}

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$ .

?

Problem 6.5.4

Can a reversible chain be periodic?

?

Problem 6.5.5

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

p_{i, i+1} = 1-\frac{i}{m}, \quad p_{i, i-1} = \frac{i}{m}, \quad \text{ for } \quad 0 \leq i \leq m

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

\mathbb {E}\left[X_{n}-\frac{m}{2}\right] = \left(i-\frac{m}{2}\right)\left(1-\frac{2}{m}\right)^{n} \rightarrow 0 \quad \text{ as } n \rightarrow \infty

?

Problem 6.5.6

(a)(b)(c)

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

?

(a)

The chain $X = \left\{ X_{n}\right\}$ having transition matrix $\mathbf{P} = \left(\begin{array}{cc}1-\alpha & \alpha \\ \beta & 1-\beta \end{array}\right)$ where $\alpha +\beta > 0$ .

(b)

The chain $Y = \left\{ Y_{n}\right\}$ having transition matrix $\mathbf{P} = \left(\begin{array}{ccc}0 & p & 1-p \\ 1-p & 0 & p \\ p & 1-p & 0\end{array}\right)$ where $0 < p < 1$ .

(c)

$Z_{n} = \left(X_{n}, Y_{n}\right)$ , where $X_{n}$ and $Y_{n}$ are independent and satisfy (a) and (b).

Problem 6.5.7

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}$ .

?

Problem 6.5.8

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.

?

Problem 6.5.9

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.

?

Problem 6.5.10

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

p_{i, i-1} = \frac{1}{2} \cdot \frac{i+2}{i+1}, \quad p_{i, i+1} = \frac{1}{2} \cdot \frac{i}{i+1}, \quad i \geq 2

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$ .

?

Problem 6.5.11

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

\begin{aligned} p_{e n} & = p_{w s} = \frac{1}{4}, \\ p_{c n} = p_{n e} = p_{e c} & = p_{c e} = p_{s w} = p_{w n} = \frac{1}{8}, \\ p_{n c} = p_{e s} = p_{s c} & = p_{c s} = p_{s e} = p_{w c} = \frac{1}{16}, \\ p_{c w} & = p_{n w} = \frac{1}{32}. \end{aligned}

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

?

Problem 6.5.12

(a)(b)

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.

?

(a)

Show that $\mathbf{L}$ is the transition matrix of an irreducible, aperiodic Markov chain $Y$ with invariant distribution $\pi$ .

(b)

Show that, if $X$ is reversible in equilibrium, then so is $Y$ .