Improved mixing rates of directed cycles by added connection (Q1741874)

The theme of this paper is the effect that the addition of random edges and non-reversibility have on the mixing time of a random walk on a graph. This is studied on a cycle of \(n\) vertices. Thereon, \(k\) disjoint paths are selected randomly and they are directed in the clockwise direction. For any two of them, the edges between the end of one and the beginning of the other are added. So if the particle that performs this random walk is at the beginning of such a path and chooses to follow the path the next hub (in the clockwise direction), it follows it all the way until its end in the clockwise direction with probability 1. If it choose to jump it selects the beginning of another interval selected uniformly at random. The parameter \(k\) depends on \(n\) and, in particular, it is set to \(n^{\sigma}\) for some \(0< \sigma < 1\). The parameter that is considered here is the spectral gap of the transition matrix. The main result is that this is greater than \(k/n\), up to a polylogarithmic factor, with high probability over the random choice of the \(k\) paths. The proof relies on the analysis of the spectral gap for a random walk on a similar random graph, where \(k\) directed paths are formed which have length that is geometrically distributed and are joined as described above.