Midterm Classwork (Retake)

\[\newcommand{\st}{\, : \:} \newcommand{\ind}[1]{\mathbf{1}_{#1}} \newcommand{\dd}{\mathrm{d}}\]

Exercises

Exercise 1 Let \(\mathbf{X}=(X_t)_{t\ge 0}\) be a Markov chain on the two-state space \(S=\{1,2\}\) with transition matrix: \[ P = \begin{pmatrix} 1-\alpha & \alpha \\ \beta & 1-\beta \end{pmatrix} \] where \(\alpha, \beta \in (0,1)\).

  1. Find the unique invariant distribution \(m\) of this chain.

  2. Fix \(T>1\). Let \(Y_t = X_{T-t}\) be the time-reversed chain starting from the stationary distribution. Determine the transition matrix of \(\mathbf{Y}\).

  3. If \(\mu_t\) is the law of \(X_t\) when starting with initial measure \(\mu_0\neq m\). Determine \[ \lim_{t\to \infty} \frac{1}{t}\log \|\mu_t-m\|_{TV} \]

  1. \(m_1 = \frac{\beta}{\alpha+\beta}\), \(m_2 = \frac{\alpha}{\alpha+\beta}\).

  2. The chain is reversible, so it has the same transition probabilities.

  3. \(P\) has eigenvalues \(1\) and \(1-\alpha -\beta\). The limit is therefore \(-\log(1-\alpha-\beta)\) (which is \(-\infty\) if \(\alpha+\beta=1\), since \(X_t\) becomes i.i.d. in this case, for \(t\ge 1\)).

Exercise 2 A bug moves on a line segment with sites \(S=\{a, b, c\}\). Site \(a\) is a “reflecting wall”: if the bug is at \(a\), it moves to \(b\) with probability \(1\) at the next step. Site \(c\) is a “sticky trap” (absorbing state): if the bug is at \(c\), it stays at \(c\) forever. At site \(b\), the bug moves to \(c\) with probability \(p \in (0,1)\) and moves back to \(a\) with probability \(1-p\). Find the expected number of steps needed for the bug to reach the trap when starting at \(a\).

Let \(\tau_c\) be the hitting time of \(c\), which is finite a.s., and let \(u(x):=\mathbb{E}[\tau_c]\). \(u\) satisfies \(u(c)=0\) and \((I-P)u=1\). Namely \(u(b)= 1+(1-p)u(a)\), \(u(a)=u(b)+1\). Thus \(u(a)=2/p\).

Exercise 3 Let \(S=\mathbb{Z}\times \mathbb{Z}_N\), where \(\mathbb{Z}_N:= \{0,1,\ldots,N\}\) and \(i,j \in \mathbb{Z}_N\) are neighbors if \(i=j \pm 1 \pmod N\).

  1. Determine whether the simple random walk on \(S\) is recurrent or transient.
  2. For \(N=2\), determine the (positive, finite at each point) invariant measures for such a random walk.
  1. Let \(X_t=(Y_t,Z_t)\) be the random walk. \(\mathbf{X}\) is irreducible, therefore each point have the same transient/recurrent property. \(\mathbf{Y}=(Y_t)\) is a random walk on \(\mathbb{Z}\), with transition probabilities \(q_{y,y}=1/2\), \(q_{y,y\pm 1}=1/4\). Thus \(\mathbf{Y}\) is recurrent and it visits each point, e.g. \(0\), infinitely many times with probability \(1\). Each time \(Y_t\) visits \(0\), \(X_t\) has strictly positive probability of visiting \((0,0)\), therefore \(\{t \st X_t=(0,0)\}\) is infinite with probability \(1\). Namely \(\mathbf{X}\) is recurrent.
  2. Uniform measures \(m_x=c\) are the only invariant ones.