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

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?

• For $n$ odd, the distribution is just a rotation of a relabeled non-lazy undirected random walk, so you can use those estimates. – Douglas Zare Jan 27 '16 at 17:15
• What is a rotation? Take an undirected chain and a lazy directed chain. I flip a coin: either (a) both chains go clockwise, or (b) one goes counterclockwise and the other stays put? Oh... that's right! Now on to the even case... – Tássio Jan 27 '16 at 17:27
• Does anybody know why the question was voted down? Is it too simple (should rather be posted on math.stackexchange)? Or never be posted? – Tássio Jan 28 '16 at 8:33

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?

• Thanks for the answer. I am still processing it. When you say the unit roots, you mean $\exp(2\pi i j/n)$, for $j\in[n]$ and where $i$ is the imaginary unit, right? – Tássio Jan 27 '16 at 18:14
• @Tássio: Oh yes, you are totally right. Thank you for the hint. I will fix that. I hope that is not too confusing since $i$ is also the index of the vertex in the inequality. – Tobias Windisch Jan 27 '16 at 18:17