Assignment 8

Assigned 2025-10-29, due 2025-11-12

Question 1

Let $d \in \N$ and $\mathcal X = \set{\pm 1}^d$ denote the binary hypercube.

  1. Two points $x = (x_1, \dots, x_d)$ and $y = (y_1, \dots, y_d) \in \mathcal X$ are connected by an edge if and only if there exists a unique $i \in \set{1, \dots, d}$ such that $x_i \neq y_i$. Let $P$ be the transition matrix of the nearest neighbor random walk on $\mathcal X$. Find all the eigenvalues of $P$, and an orthonormal basis of eigenfunctions. Also find the absolute spectral gap $\gamma_*$.

    Hint. For $S \subseteq \set{1, \dots, d}$ try choosing $\varphi_S(x) = \prod_{i \in S} x_i$.

  2. Let $\pi$ be the uniform distribution on the binary hypercube $\mathcal X$, and consider the associated Glauber chain. Find all the eigenvalues of the transition matrix. Also find an orthonormal basis of eigenfunctions, and the absolute spectral gap.

Question 2

Let $d \in \N$, $N_1$, …, $N_d \geq 2$ and $\mathcal X = \set{0, \dots, N_1 -1} \times \cdots \times \set{0, \dots, N_d -1}$. Let $(X_n)$ be the lazy symmetric random walk on $\mathcal X$, which wraps around on the boundaries. That is, given $X_n = x = (x_1, \dots, x_d)$, we choose $i \in \set{1, \dots, d}$, $a, b \in \set{\pm 1}$ independently and uniformly at random. If $a = -1$ we set $X_{n+1} = x$. If $a = 1$, we replace the $i$-th coordinate of $x$ with $x_i + b \pmod{N_i}$. Find the absolute spectral gap.

Question 3

Consider the setting of the $\ell^2$ convergence theorem. Does there exist an probability distribution $\mu_0$ such that \begin{equation} \norm[\Big]{ \frac{\mu_n}{\pi} - 1}_{\ell^2(\pi)} = (1 - \gamma_*)^n \norm[\Big]{ \frac{\mu_0}{\pi} - 1}_{\ell^2(\pi)} \,. \end{equation} Prove it, or find a counter example.

Question 4

Let $P$ be the transition matrix of a reversible, irreducible chain with stationary distribution $\pi$. Let $\lambda_1$, …, $\lambda_{\abs{\mathcal X}}$ be the eigenvalues of $P$ and $\varphi_1$, …, $\varphi_{\mathcal X}$ be the corresponding eigenfunctions.

  1. Find $\sum_{k = 1}^{\abs{\mathcal X}} |\varphi_k(x)|^2$ in terms of $\pi$.

    Hint: Let $\delta_x(y) = 1$ if $x = y$ and $0$ otherwise. Express $\delta_x$ as a linear combination of $\set{\varphi_k}$, and compute $\norm{\delta_x}_{\ell^2(\pi)}$.

  2. Find a formula for $P^n(x, y)$ in terms of $x$, $y$, $n$, the eigenvalues $\set{\lambda_k}$ and the eigenfunctions $\set{\varphi_k}$.

  3. Show that for every $x \in \mathcal X$, we have \begin{equation} \sum_y |P^n(x, y) - \pi(y)| \leq \frac{(1 - \gamma_*)^n}{\sqrt{\pi_{\min}}} \end{equation} where $\pi_{\min} = \min \pi$.

    Note: This can be used to improve the bound in the TV convergence theorem by an unimportant factor of $1/\sqrt{2}$.