Mixing time and spectral gap for a special stochastic matrix 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)?
 A: $\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$ 
