Assignment 9

Assigned 2025-11-12, due 2025-11-19

Question 1

Prove this proposition relating $\tmix(\epsilon)$ and $\tmix(\delta)$.

For a reversible chain, prove a lower bound of the mixing time in terms of the relaxation time as stated in this proposition.

Prove this proposition showing $d^{(2)}$ is sub-multiplicative.

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

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}
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}
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.