A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse directed graphs, for which even the equilibrium measure is far from being understood. We work under the configuration model, allowing both the in-degrees and the out-degrees to be freely specified. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a universal shape. We also provide a detailed description of the equilibrium measure.
In contrast, very little is known about random walks on random directed graphs. The failure of the crucial property makes many of the ingredients used in the above works unavailable. Even understanding the equilibrium measure constitutes an important theoretical challenge, with applications to link-based ranking in large databases (see, e.g., @cite_7 and the references therein). In @cite_0 , Cooper and Frieze consider the random digraph on @math vertices formed by independently placing an arc between every pair of vertices with probability @math , where @math is fixed while @math . In this regime, they prove that the equilibrium measure is asymptotically close to the in-degree distribution. The recent work @cite_8 by Addario-Berry, Balle and Perarnau provides precise estimates on the extrema of the equilibrium measure in a sparse random digraph where all out-degrees are equal. To the best of our knowledge, the present paper provides the first proof of the cutoff phenomenon in the non-reversible setting of random directed graphs.
@cite_0 @cite_7 @cite_8
2158978530 2146999606
We study properties of a simple random walk on the random digraph D"n","p when np=dlogn, d>1. We prove that whp the value @p"v of the stationary distribution at vertex v is asymptotic to deg^-(v) m where deg^-(v) is the in-degree of v and m=n(n-1)p is the expected number of edges of D"n","p. If d=d(n)-> with n, the stationary distribution is asymptotically uniform whp. Using this result we prove that, for d>1, whp the cover time of D"n","p is asymptotic to dlog(d (d-1))nlogn. If d=d(n)-> with n, then the cover time is asymptotic to nlogn. Let D(n,r) be a random r-out regular directed multigraph on the set of vertices 1,...,n . In this work, we establish that for every r � 2, there existsr > 0 such that diam(D(n,r)) = (1 + �r + o(1))log r n. Our techniques also allow us to bound some extremal quantities related to the stationary distribution of a simple random walk on D(n,r). In particular, we determine the asymptotic behaviour ofmax andmin, the maximum and the minimum values of the stationary distribution. We show that with