0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For $n$ odd, the distribution is just a rotation of a relabeled non-lazy undirected random walk, so you can use those estimates. $\endgroup$ – Douglas Zare Jan 27 '16 at 17:15
  • $\begingroup$ 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... $\endgroup$ – Tássio Jan 27 '16 at 17:27
  • $\begingroup$ Does anybody know why the question was voted down? Is it too simple (should rather be posted on math.stackexchange)? Or never be posted? $\endgroup$ – Tássio Jan 28 '16 at 8:33
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tássio Jan 27 '16 at 18:14
  • $\begingroup$ @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. $\endgroup$ – Tobias Windisch Jan 27 '16 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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