Assignment 4

Assigned 2024-09-17, due 2024-09-24.

For all questions on Markov Chains, we will implicitly assume that the state space $\mathcal X$ is finite, and the chain is time homogeneous.

Question 1

Did you fill out the early course feedback? (Simple, anonymous, and only takes a minute; you get one point for doing it.)

Question 2

Let $P$ be the transition matrix for an irreducible Markov chain on a state space $\mathcal X$, and $\pi$ be the (unique) stationary distribution.

  1. Let $v \colon \mathcal X \to \R$ be any function such that $v P = v$. Show that there exists $\lambda \in \R$ such that $v = \lambda \pi$.

    Note: Here $v = \lambda \mu$ means that for every $x \in \mathcal X$, $v(x) = \lambda \mu(x)$.

  2. Find all functions $f \colon \mathcal X \to \R$ such that $Pf = f$. (Here $Pf \colon \mathcal X \to \R$ is the function defined by $Pf(x) = \sum_{y \in \mathcal X} P(x, y) f(y)$.)

    Hint: It’s fair game to use standard theorems from Linear Algebra without proof. In this case you might need the relation between the dimension of the kernel of a matrix, and the dimension of the kernel of the transpose.

Question 3

Let $X$ be an Markov chain with transition kernel $P$. For every $x \in \mathcal X$, define \begin{equation} \mathcal T(x) = \set{ n \in \N \st P^n(x, x) > 0 } \,. \end{equation} If $X$ is irreducible, then show that for every $x, y \in \mathcal X$, we must have $\gcd(T(x)) = \gcd(T(y))$. (The number $\gcd(T(x))$ is then called the period of the chain.)

Question 4

Consider the Metropolis Hastings chain used to sample from the Gibbs measure in the Ising model on a $N \times N$ lattice.

  1. Is the chain irreducible? Prove or disprove it.

  2. Is the chain aperiodic? Prove or disprove it.

Question 5

Let $X$ be an irreducible, aperiodic Markov chain with $X_0 \sim \mu$, and fix $\epsilon \in (0, 1/2)$.

  1. Let $f \colon \mathcal X \to \R$ be any function. Show that \begin{equation} \sum_{k=0}^\infty \cov( f(X_n), f(X_{n+k} ) ) \leq \frac{8 (\max \abs{f})^2 \tmix(\epsilon)}{1 - 2\epsilon} \end{equation}

  2. Let $\bar f_n = \E f(X_n)$, $\mathcal I_\pi(f) = \sum_x f(x) \pi(x)$ and $N = \tmix(\epsilon)$. Show that \begin{equation} \abs{\bar f_n - \mathcal I_\pi(f)} \leq 2 (2\epsilon)^{\floor{n / N}} \max \abs{f} \end{equation}

  3. For any $N \in \N$ show that \begin{equation} \E \paren[\Big]{ \frac{1}{N} \sum_{n = 0}^{N-1} f(X_n) - \mathcal I_\pi(f) }^2 \leq \frac{8 (\max \abs{f})^2 \tmix(\epsilon)}{N(1 - 2\epsilon)} +4 \paren[\Big]{ \frac{ (\max \abs{f}) \tmix(\epsilon) }{N (1 - 2\epsilon)} }^2 \end{equation} Note: When performing Monte Carlo simulations to compute $\mathcal I_\pi(f)$, this problem tells you how large your error is. To get a good estimate you need $N \gg \tmix(\epsilon)$. There is a better bound involving the $\var(f)$, but this involves estimating the $L^2$ mixing time.