# Mixing time and spectral gap for a special stochastic matrix

Conisder the following dimension stochastic matrix, $$\begin{bmatrix} p & q & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix}$$ with $$p,q>0$$ and $$p+q=1$$.

To control mixing time, I am interested in its spectral gap. Let $$n$$ be the number of rows (e.g., $$n=5$$ in the example above). The characteristic polynomial is $$x^n - px^{n-1} - q.$$ How to argue that the spectral gap decay polynomially in terms of $$n$$ (rather than of exponentially)?

• Imagine $p=q=1/2$. Every $n$ steps, you get a chance to jump ahead by 1. After $n^2$ steps, you have had $n$ chances, so you have jumped ahead by $n/2\pm \sqrt(n/4)$. It takes around $n^3$ steps before you would expect to mix. – Anthony Quas Mar 15 at 2:13

$$\newcommand{\thh}{\theta} \newcommand{\ep}{\varepsilon}$$ Let us show that the spectral gap is on the order of at least $$1/n^3$$.

In what follows, $$z$$ always denotes a root of the equation $$\begin{equation*} f(z):=z^n-pz^{n-1}-q=0, \end{equation*}$$ so that $$|z|\le1$$, since the matrix is stochastic.

Let $$c$$, possibly with indices, denote various positive expressions (possibly different even within one formula) which stay away from both $$0$$ and $$\infty$$ as $$n\to\infty$$.

Lemma 1. $$|z|\ge1-c/n$$.

Proof. We have $$q\le|z|^n+p|z|^{n-1}\le2|z|^{n-1}$$, whence $$|z|\ge(\frac q2)^{1/(n-1)}=1-c/n$$. $$\Box$$

Lemma 2. Suppose that $$z=|z|e^{i\thh}$$ and $$0<|\thh|\le\pi$$. Then $$|\thh|\ge1/n$$ eventually (for large enough $$n$$).

Proof. Let $$\ep:=(1-p)/2>0$$. If $$\cos\thh\le p+\ep[<1]$$, then $$|\thh|\ge c\ge1/n$$ eventually, as desired. So, without loss of generality (wlog) $$\cos\thh>p+\ep$$. So, eventually $$\cos\thh-p/|z|>p+\ep-p/|z|>\ep/2$$ by Lemma 1, and hence $$\begin{equation*} e^{i\thh}-p/|z|=\cos\thh-p/|z|+i\sin\thh=re^{i\phi} \tag{0} \end{equation*}$$ for some $$r>0$$ and $$\phi\in(-\pi/2,\pi/2)$$ such that $$\begin{equation*} \tan\phi=\frac{\sin\thh}{\cos\thh-p/|z|}=c\sin\thh\quad\text{and hence}\quad\phi=c\thh. \end{equation*}$$ Note that $$\begin{equation*} q=z^n-pz^{n-1}=|z|^n e^{i(n-1)\thh}(e^{i\thh}-p/|z|) =|z|^n re^{i[(n-1)\thh+\phi]} \end{equation*}$$ by (0), whence for some integer $$k$$ we have $$\begin{equation*} 2\pi k=(n-1)\thh+\phi=(n-1+c)\thh. \tag{1} \end{equation*}$$ If $$k=0$$, then it would follow from (1) that $$\thh=0$$, which would contradict the condition $$0<|\thh|\le\pi$$ of Lemma 2. So, $$|k|\ge1$$, and Lemma 2 follows from (1). $$\Box$$

Lemma 3. $$z\notin[0,1)$$.

Proof. We have $$f'(x)=nx^{n-2}(x-x_*)$$, where $$x_*:=\frac{n-1}n\,p$$. So, $$f$$ is decreasing on $$[0,x_*]$$ and increasing on $$[x_*,1]$$. Also, $$f(0)=-q<0$$ and $$f(1)=0$$. Now Lemma 3 follows. $$\Box$$

So, Lemma 2 allows us to relax the condition $$0<|\thh|$$ in Lemma 3 to $$z\ne1$$ and thus immediately get

Lemma 2a. Suppose that $$z=|z|e^{i\thh}\ne1$$ and $$|\thh|\le\pi$$. Then $$|\thh|\ge1/n$$ eventually.

Now we are ready to prove the final result:

Theorem. If $$z\ne1$$, then $$|z|\le1-c/n^3$$.

Proof. Wlog $$|z|>1-c/n^3$$. Let $$x:=\Re z$$. By Lemma 2a, $$x\le\cos\thh=1-c/n^2$$ and hence $$$$|z-p|^2=|z|^2+p^2-2px\ge(1-c/n^3)^2+p^2-2p(1-c/n^2)=q^2+c/n^2,$$$$ and so, $$|z-p|\ge q+c/n^2$$. Thus, $$$$|z|^{n-1}=\frac q{|z-p|}\le\frac q{q+c/n^2}=\frac1{1+c/n^2}=1-c/n^2,$$$$ which yields the theorem. $$\Box$$