Assignment 10

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

Question 1

Consider the lazy random walk on the torus as described here. Prove the following special case of this proposition: For $d = 2$ show that there exists a constant $C$ such that for all $N$ we have $\tmix \leq C N^2$.

Question 2

Prove the mixing time bound for the binary hypercube stated in this proposition.

Question 3

Let $P$ be a transition matrix. We say $(X_n, Y_n)$ is a coupling of $P$ if both $(X_n)$ is a Markov chain with transition matrix $P$, and $(Y_n)$ is a Markov chain with transition matrix $P$. (Note that this is different from the definition of a Markovian coupling, which we what we have been using so far.)

  1. If $(X_n, Y_n)$ is a Markovian coupling of $P$, must $(X_n, Y_n)$ be a coupling of $P$? Prove it, or find a counter example.

  2. If $(X_n, Y_n)$ is a coupling of $P$, must $(X_n, Y_n)$ be a Markovian coupling of $P$? Prove it, or find a counter example.

  3. Is the distance to stationary bound in this theorem still true if $(X_n, Y_n)$ is just a coupling, and not a Markovian coupling? Prove or disprove it.

Question 4

Prove this proposition showing there exists a coupling $(X, Y)$ of the pair of probability distributions ($\mu$, $\nu$) such that $\norm{\mu - \nu}_\TV = \P(X \neq Y)$.

Question 5

  1. Let $(X_n)$ be an irreducible Markov chain on a finite state space $\mathcal X$, and $S \subseteq X$ be non-empty. Let $\tau_S = \min\set{ n \geq 0 \st X_n \in S}$. Show that $\P( \tau_S > n) \to 0$ as $n \to \infty$.

  2. Solve this optional question showing that in fact $\P(\tau_S > n) \to 0$ exponentially in $n$ and hence $\E \tau_S < \infty$.

  3. Provide an alternate proof of the convergence theorem using the following coupling argument: Let $(X_n, Y_n)$ be the Markovian coupling of $P$ defined as follows. Suppose $X_n = x$, $Y_n = y$. If $x = y$, then choose $X_{n+1} \sim P(x, \cdot)$, and $Y_{n+1} = X_{n+1}$. If $x \neq y$, then choose $X_{n+1} \sim P(x, \cdot)$ and $Y_{n+1} \sim P(y, \cdot)$ independently. Let $\tau_\cpl = \min \set{n \st X_n = Y_n}$. Show that for any $x, y \in \mathcal X$, we have $\P^{x, y}( \tau_\cpl > n ) \to 0$ as $n \to \infty$, and use this to prove the convergence theorem.

  4. Prove the following generalization of the Harris lemma. Let $(X_n, Y_n)$ to be the same coupling from the previous part (and as before assume the transition matrix $P$ is irreducible and aperiodic). Suppose there exists $\delta > 0$, a probability distribution $\gamma$ and a non-empty set $S \subseteq \mathcal X$ such that for every $x \in S$ and $x’ \in \mathcal X$, we have $P(x, x’) \geq \delta \gamma(x’)$. Let $\tau = \min \set{ n \st (X_n, Y_n) \in S \times S }$. Show that for any probability distribution $\mu_0$, if $X_0 \sim \mu_0$, then \begin{equation} \norm{\dist(X_n) - \pi}_\TV \leq \paren[\Big]{ 1 - \frac{\delta}{2}}^{\floor{n / (2 N)}} \quad\text{where}\quad N = \max_{x, y \in \mathcal X} \E^{x, y} \tau \,. \end{equation}

    Note: There was an error in the original problem that put $\E \tau$ in the exponent without taking the max over $x, y$, which was corrected later.

Question 6

Here are a few anonymous feedback questions that are not included in the FCE’s. Please fill them out and include a screenshot of the confirmation you get on completion. (Please don’t fill it out twice – if you lost your confirmation screenshot just say so.)