3
$\begingroup$

Consider 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 decays polynomially in terms of $n$ (rather than exponentially)?

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 15, 2019 at 2:13

1 Answer 1

4
$\begingroup$

$\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 \begin{equation} |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, \end{equation} and so, $|z-p|\ge q+c/n^2$. Thus, \begin{equation} |z|^{n-1}=\frac q{|z-p|}\le\frac q{q+c/n^2}=\frac1{1+c/n^2}=1-c/n^2, \end{equation} which yields the theorem. $\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.