I would like to know the mixing time of a discrete random walk on an N-cycle which moves to the right or left with probability $\frac{1}{2}$. I read in a paper that this mixing time is $$M_\epsilon \sim N^2 log(1/\epsilon).$$ Is this correct?
The mixing time is defined as $$M_{\varepsilon} = min\{T \mid \forall t \geq T: ||P_t-\pi|| \leq \varepsilon\},$$ where $||{A-B}||\equiv \sum_{i}\mid A(i)-B(i) \mid$ is the total variational distance between distributions A and B.
The paper did not include any explanation/derivation/reference for this result, and I haven't been able to find anything online. So, I was wondering if anyone knows a good reference that discusses the mixing time for a random walk on a cycle?
The estimate you quote holds if $N$ is odd, but not if $N$ is even, when the cycle is bipartite. To obtain the estimate for all $N$, we consider the lazy random walk (which stays in place with probability $1/2$) instead.
The upper bound is in [1], section 5.3.2 (page 63), together with the general estimate (4.34) page 54.
For the lower bound, you can apply eq. (12.14) page 164 in [1], together with the fact that $t_{rel}$ is of order $N^2$, see the discussion after (12.18).
[1] https://www.yuval-peres-books.com/markov-chains-and-mixing-times/