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.