| course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
II |
36 |
|
A1.1 B1.1 |
2001 |
(i) Let $X=\left(X_{n}: 0 \leqslant n \leqslant N\right)$ be an irreducible Markov chain on the finite state space $S$ with transition matrix $P=\left(p_{i j}\right)$ and invariant distribution $\pi$. What does it mean to say that $X$ is reversible in equilibrium?
Show that $X$ is reversible in equilibrium if and only if $\pi_{i} p_{i j}=\pi_{j} p_{j i}$ for all $i, j \in S$.
(ii) A finite connected graph $G$ has vertex set $V$ and edge set $E$, and has neither loops nor multiple edges. A particle performs a random walk on $V$, moving at each step to a randomly chosen neighbour of the current position, each such neighbour being picked with equal probability, independently of all previous moves. Show that the unique invariant distribution is given by $\pi_{v}=d_{v} /(2|E|)$ where $d_{v}$ is the degree of vertex $v$.
A rook performs a random walk on a chessboard; at each step, it is equally likely to make any of the moves which are legal for a rook. What is the mean recurrence time of a corner square. (You should give a clear statement of any general theorem used.)
[A chessboard is an $8 \times 8$ square grid. A legal move is one of any length parallel to the axes.]