Assignment 7

Assigned 2025-10-22, due 2025-10-29

Question 1

Let $(X_n)$ be a Markov chain with transition matrix $P$ and stationary distribution $\pi >0$. Let $(\hat X_n)$ be the time reversal, and $\hat P$ be the transition matrix of the time reversal.

  1. True or false: $\pi$ is a stationary distribution of $\hat P$. Prove it, or find a counter example.

  2. True or false: If $X_0 \sim \pi$, $\hat X_0 \sim \pi$, then for every $n \in \N$, and every $x_0, \dots, x_n \in \mathcal X$, we have \begin{equation} \P^\pi( X_0 = x_0, \dots, X_n = x_n) = \P^\pi( \hat X_0 = x_n, \hat X_{1} = x_{n-1}, \dots, \hat X_n = x_0) \,. \end{equation} Prove it, or find a counter example.

Question 2

Let $\pi_u$ be an unnormalized probability distribution, and $Q$ be a transition matrix. Let $P$ be the transition matrix of the Metropolis–Hastings chain designed to sample from the probability distribution $\pi \propto \pi_u$ using a proposal mechanism with transition matrix $Q$.

  1. True or false: $P = Q$ if and only if $Q$ is reversible with stationary distribution $\pi$. Prove it, or find a counter example.

  2. Suppose $\mathcal X = \set{x : V \to S}$ where $S, V$ are finite sets, and $\pi_u \colon X \to [0, \infty)$ is an unnormalized probability distribution. Does there exist a proposal mechanism so that the corresponding Metropolis–Hastings chain is exactly the Glauber dynamics? Prove or disprove.

Question 3

Implement a MCMC algorithm sampling from the Gibbs distribution in the Ising model. Assume $J = 1$ and $B = 0$. Download this notebook which generates all the figures on this page. The function implementing the MCMC algorithm has been removed from the notebook. Implement this function and run the notebook to get output that looks like this.

You only need to turn in a screenshot of your implementation of the missing functions logπu and mcmc and the first two graphs produced by the notebook. (You do not have to include the video.)

Question 4

Consider the symmetric lazy random walk on $\set{0, \dots, N-1}$ with transition probabilities given by \begin{equation} P(x, y) = \begin{cases} 1/4 & \text{if } \abs{x - y} \equiv 1 \pmod{N}\,,\\ 1/2 & \text{if } \abs{x = y} \,,\\ 0 & \text{otherwise.} \end{cases} \end{equation} Find all the eigenvalues of $P$, and an orthonormal basis of eigenvectors.

Hint: Try functions of the form $\varphi(k) \defeq \zeta^{k}$ for some correctly chosen value of $\zeta$. You don’t have to show how you arrived at your answer, but you do have to verify that what you find is an orthonormal basis of eigenvectors.

Question 5

Let $P$ be the transition matrix of a reversible chain.

  1. Must the absolute spectral gap $\gamma_*$ be strictly positive? Prove it, or find a counter example.

  2. Suppose now $P$ is irreducible. Must the absolute spectral gap $\gamma_*$ be strictly positive? Prove it, or find a counter example.

  3. Suppose now $P$ is irreducible and aperiodic. Must the absolute spectral gap $\gamma_*$ be strictly positive? Prove it, or find a counter example.