I am working on the following problem from Levin–Peres–Wilmer, "Markov Chains and Mixing Times," chapter 13:
Exercise 13.2. Show that for the lazy simple random walk on the box $\{1,\dots,n\}^d$, the absolute spectral gap $\gamma_\star$ satisfies $\gamma_\star^{-1}\in O(n^2)$.
Based on the chapter, it would make sense that this would be an application of:
Theorem 13.1. Let $(\Omega,d)$ be a finite metric space, and consider a Markov chain on $X$ with transition matrix $P$. Let $\mu_x=P(x,\cdot)$ be the distribution of the one-step walk beginning at $x\in\Omega$. Suppose there is $a<1$ such that, for all $x,y\in\Omega$, there exists a coupling $(X,Y)$ of $(\mu_x,\mu_y)$ satisfying $\mathbb{E}_{x,y}[d(X,Y)]\le a\cdot d(x,y)$. Then, $\gamma_\star(P)\ge1-a$.
Here are the difficulties I have found so far with this problem.
- The chain is not a product chain so it does not reduce to analysis of the $d=1$ case (which is studied earlier in the text, and does promisingly feature eigenvalues of the form $\cos(2\pi/n)\in1-O(n^{-2})$).
- It is not clear which metric makes the most sense to place on $B=\{1,\dots,n\}^d$. The $1$-, $2$-, and $\infty$-norms all have their own issues.
- The constant $a$ is uniform over all states, so it must hold for "worst-case" states which here appear to be "interior" states (i.e. $(m_1,\dots,m_d)\in B$ where $m_i\not\in\{1,n\}$). $\ell^1$ is especially bad here, as I think all couplings will leave the $1$-norm unchanged (i.e. $a=1$).
- $\ell^2$ seems far too difficult to compute with, though does come with the advantage of being "$\cos$-ish" in the sense that if $x,y\in B$ have $\|x-y\|_2^2=L$ and conditioned on $y$ moving on the first component, the new expected $2$-norm takes the form $\frac{1}{2}(\sqrt{L-2d+1}+\sqrt{L+2d+1})$ where $d=\lvert x_1-y_1\rvert$ which should have a favorable Taylor expansion when divided out by $\sqrt{L}$. This appears far too messy, though, and likely to break down for small $L$.
- $\ell^\infty$ seems to be too insensitive: it only changes when precisely the right coordinate is chosen (in the generic case that $x-y$ has a unique largest coordinate), and even then seems that it may suffer from the same issues as with $\ell^1$.
Any advice on how to approach this or even where to get started would be fantastic. Thanks in advance.