(Kolmogorov cycle condition). Consider an irreducible Markov chain with state space S. We say that the cycle condition is satisfied if given a cycle of states x0; x1; : : : ; xn D x0 with q.xi[1]1; xi/ > 0 for 1 i n, we have n Y iD1 q.xi[1]1; xi / D n Y iD1 q.xi; xi[1]1/

(a) Show that if q has a stationary distribution that satisfies the detailed balance condition, then the cycle condition holds.

(b) To prove the converse, suppose that the cycle condition holds. Let a 2 S and set .a/ D

c. For b ¤ a in S let x0 D a; x1 : : :xk D b be a path froma to b with q.xi[1]1; xi/ > 0 for 1 i k let .b/ D k Y jD1 q.xi[1]1; xi /

q.xi; xi[1]1/

Show that .b/ is well defined, i.e., is independent of the path chosen. Then conclude that  satisfies the detailed balance condition.

Hitting Times and Exit Distributions