| course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
IB |
45 |
|
Paper 1, Section II, H |
2011 |
Let $P=\left(p_{i j}\right)_{i, j \in S}$ be the transition matrix for an irreducible Markov chain on the finite state space $S$.
(i) What does it mean to say $\pi$ is the invariant distribution for the chain?
(ii) What does it mean to say the chain is in detailed balance with respect to $\pi$ ?
(iii) A symmetric random walk on a connected finite graph is the Markov chain whose state space is the set of vertices of the graph and whose transition probabilities are
$$p_{i j}= \begin{cases}1 / D_{i} & \text { if } j \text { is adjacent to } i \ 0 & \text { otherwise }\end{cases}$$
where $D_{i}$ is the number of vertices adjacent to vertex $i$. Show that the random walk is in detailed balance with respect to its invariant distribution.
(iv) Let $\pi$ be the invariant distribution for the transition matrix $P$, and define an inner product for vectors $x, y \in \mathbb{R}^{S}$ by the formula
$$\langle x, y\rangle=\sum_{i \in S} x_{i} \pi_{i} y_{i}$$
Show that the equation
$$\langle x, P y\rangle=\langle P x, y\rangle$$
holds for all vectors $x, y \in \mathbb{R}^{S}$ if and only if the chain is in detailed balance with respect to $\pi$. [Here $z \in \mathbb{R}^{S}$ means $z=\left(z_{i}\right)_{i \in S}$.]