Mixing time of lazy random walk on the directed cycle $C_n$

Question

Briefly: A hint (if this is easy), reference or derivation would be of great help.

The question

Let $C_n$ be the directed cycle with loops in each of its $n$ vertices, and consider the random walk that at each step stays put with probability $\frac{1}{2}$ and moves clockwise with probability $\frac{1}{2}$.

Let $X_t$ be the state of the walk (i.e., the vertex visited) at time $t$, where $X_0=x$, for some vertex $x$ of $C_n$.

Given a parameter $\varepsilon$ and the vertex $x$, I am interested in bounding the value $t_0$ such that for all times $t$, with $t\geq t_0$ and all vertices $y$ of $C_n$

$$ \left|\Pr(X_t = y) - \frac{1}{n}\right| \leq \varepsilon. $$

Some context

Let $C_n$ be an $n$-vertex undirected cycle. If the random walk on $C_n$ is ergodic (i.e., if $n$ is odd), then the stationary distribution is uniform (since $C_n$ is 2-regular). Furthermore, if $t=O(c n^2\log n)$, then $$|\Pr(X_t=y)-n^{-1}|<\exp(-c).$$

What i need to incorporate is the fact that every vertex has a loop (I do not care wether $n$ is even or odd), and that the walk is directed. Does this ruin the mixing time?

Answer 1

Let $A_n$ be the adjacency matrix of the directed $n$-cycle without loops. That is for instance

$$A_4=\begin{bmatrix}0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\\ 1& 0 & 0 &0 \end{bmatrix}.$$ The transition matrix $P_n$ of your random walk is then given by $P_n=\frac{1}{2}A_n+\frac{1}{2}I_n$ where $I_n$ is the unit matrix. Let $\lambda(P_n)$ denote the second largest eigenvalue modulus of $P_n$, then the rate of convergence to the stationary distribution is for any starting vertex $i\in[n]$ (this is true for the undirected case and it should be true for the directed case as well):

$$\|P_n^t\cdot e_i-\left(\frac{1}{n},\dots,\frac{1}{n}\right)^T\|_2\le\lambda(P_n)^t.$$

(you are interessted in $\|\cdot\|_\infty$, but this can clearly be bounded from above in terms of $\|\cdot\|_2$). The eigenvalues of $P_n$ have precisely the form $\frac{1}{2}\mu+\frac{1}{2}$, where $\mu$ is an eigenvalue of $A_n$. The eigenvalues of $A_n$ are the unit roots, i.e. $\mu=\exp(\frac{2\pi ij}{n})$ for $j\in[n]$. Left to do is to figure out what

$$\lambda(P_n)=\max\left\{|\frac{1}{2}\exp(\frac{2\pi i j}{n})+\frac{1}{2}|: j\in[n-1]\right\}$$

is. Does that help?