course |
course_year |
question_number |
tags |
title |
year |
Markov Chains |
IB |
44 |
|
Paper 4, Section I, H |
2018 |
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$.
(a) What does it mean to say that a distribution $\pi$ is the invariant distribution for the chain?
(b) What does it mean to say that the chain is in detailed balance with respect to a distribution $\pi$ ? Show that if the chain is in detailed balance with respect to a distribution $\pi$ then $\pi$ is the invariant distribution for the chain.
(c) 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.