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?



Mixing time of lazy random walk on the directed cycle $C_n$
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?


