Spring 2018, Math 171

Week 5

1. Reversibility/Detailed Balance Condition

   1. Show that Ehrenfest’s chain is reversible. \[P(x,y)= \begin{cases}\frac{N-x}{N}, & \mathrm{if\ } y=x+1 \cr \frac{x}{N}, & \mathrm{if\ } y=x-1 \cr 0, & \mathrm{otherwise}\end{cases}\]

      • (Answer) Show KCC on simple cycles: All simple cycles are length 2, and cycles of length 2 always satisfy KCC.

   2. Consider the Markov chain \(\{X_n:n \ge 0\}\) on \(\mathcal{S} = \{1, 2, \dots, N\}\) with a transition matrix of the form \[P(x,x-1)=q(x), \; P(x,x)=r(x), \; P(x,x+1)=p(x)\]

      1. Find conditions on \(q, r, p\) which guarantee the chain will be irreducible.

         • (Answer) \(q(x) \neq 0\) and \(p(x) \neq 0\) \(\forall x\)

      2. Show the chain is reversible

         • (Answer) Show KCC on simple cycles: All simple cycles are length 2, and cycles of length 2 always satisfy KCC.

      3. Find the stationary distribution, assuming the chain is irreducible

   3. (Discussed) Consider the Markov chain \(\{X_n:n \ge 0\}\) on \(\mathcal{S} = \{1, 2, \dots, N\}\) with a transition matrix of the form \[P(x,y)= \begin{cases}q(x) & \mathrm{if\ } x \neq y \cr 1-(N-1)q(x) & \mathrm{if\ } x = y \end{cases}\] Verify that such chains are reversible

   4. Suppose \(P\) is the transition matrix for a reversible Markov chain. Fix \(i_0, j_0 \in \mathcal{S}\) Define a new transition matrix \[P'(x,y)= \begin{cases}aP(i_0, j_0) & \mathrm{if\ } x=i_0, y=j_0 \cr aP(j_0, i_0) & \mathrm{if\ } x=j_0, y=i_0 \cr P(i_0, i_0) + (1-a)P(i_0, j_0) & \mathrm{if\ } x=y=i_0 \cr P(j_0, j_0) + (1-a)P(j_0, i_0) & \mathrm{if\ } x=y=j_0 \cr P(x,y) & \mathrm{otherwise} \end{cases}\]

      1. Verify that the Markov chain defined by the new transition matrix will be reversible

      2. How will the stationary distribution of the new Markov chain relate to the stationary distribution of the original?

2. Limiting Behavior

   1. (Discussed) Consider Ehrenfest’s chain \(\{X_n:n \ge 0\}\) subject to the transition probabilities. \[P(x,y)= \begin{cases}\frac{N-x}{N}, & \mathrm{if\ } y=x+1 \cr \frac{x}{N}, & \mathrm{if\ } y=x-1 \cr 0, & \mathrm{otherwise}\end{cases}\]

      1. Compute the period of \(\{X_n:n \ge 0\}\)

         • (Answer) 2

      2. Show that \(Y_n=X_{2n}\) is a Markov chain. Is it irreducible?

         • (Answer) No. The state space has been split into two parts which don’t communicate with each other.

      3. Consider \(Y_n=X_{2n}\) under the restriction \(X_0 \in \{0,\ 2,\ \dots,\ 2\lfloor\frac{N}{2}\rfloor\}\). Compute its stationary distribution. Explain why \(Y_n\) converges in distribution to the stationary distribution as \(n \to \infty\).

   2. (Discussed) Consider the Markov chain \(\{X_n:n \ge 0\}\) on \(\mathcal{S} = \{1, 2, \dots, N\}\) with a transition matrix of the form \[P(x,x-1)=q(x), \; P(x,x)=r(x), \; P(x,x+1)=p(x)\]

      1. Find conditions on \(q, r, p\) which lead to a period of 2

         • (Answer) \(r(x) = 0\)

      2. Suppose \(q(x)=0\). Find a formula for \(\mathbb{E}_x[N(y)]\) for \(x < y\)

   3. Consider the Markov chain \(\{X_n:n \ge 0\}\) on \(\mathcal{S} = \{1, 2, \dots, N\}\) with a transition matrix of the form \[P(x,y)= \begin{cases}p, & \mathrm{if\ } y=x+1, \; x<N \cr 1-p, & \mathrm{if\ } x=0, \; y=0 \cr r & \mathrm{if\ } y = x, \; 0<y<N \cr q, & \mathrm{if\ } y=x-1, \; x>0 \cr 1-q, & \mathrm{if\ } x=N, \; y=N \cr 0, & \mathrm{otherwise}\end{cases}\]

      1. Find a system of equations which could be solved to find \(\mathbb{E}_x[T_N]\) for any \(x\).

      2. Compute \(\mathbb{E}_x[T_N]\) when \(r=0\) and \(q=1-p\)