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.
Let C 1 denote the largest connected component of the critical Erdos-Renyi random graph G(n, 1 n). We show that, typically, the diameter of C 1 is of order n 1 3 and the mixing time of the lazy simple random walk on C 1 is of order n. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size n 2 3 of p-bond percolation on any d-regular n-vertex graph where such clusters exist, provided that p(d-1)≤ 1+O(n- 1 3 ). We study the cover time of a random walk on graphs G e Gn,p when @math . We prove that whp, the cover time, is asymptotic to @math . ©Wiley Periodicals, Inc. Random Struct. Alg., 2007 We study the cover time of a random walk on the largest component of the random graph Gn,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k-cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 Let @math be constant, and let @math denote the set of r-regular graphs with vertex set V = 1,2,...,n . Let G be chosen randomly from @math . We prove that with high probability ( ) the cover time of a random walk on G is asymptotic to @math . We show that the total variation mixing time of the simple random walk on the giant component of supercritical Gn,p and Gn,m is i¾?log2n. This statement was proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are "decorated expanders" - an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 383-407, 2014 In this article we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that slow down the random walk, when the average degree d is at most O( @math ), proving that the mixing time in this case is Θ((n-d)2) asymptotically almost surely. As the average degree grows these become negligible and it is the diameter of the largest component that takes over, yielding mixing time Θ(n-d) a.a.s.. We proved these results during the 2003–04 academic year. Similar results but for constant d were later proved independently by in [3]. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 Most of this work was completed while the author was a research fellow at the School of Computer Science, McGill University. Given a discrete random walk on a finite graph @math , the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step @math . These sets induce subgraphs of the underlying graph. Let @math be the subgraph of @math induced by the vacant set of the walk at step @math . Similarly, let @math be the subgraph of @math induced by the edges of the vacant net. For random @math -regular graphs @math , it was previously established that for a simple random walk, the graph @math of the vacant set undergoes a phase transition in the sense of the phase transition on Erd os -Renyi graphs @math . Thus, for @math there is an explicit value @math of the walk, such that for @math , @math has a unique giant component, plus components of size @math , whereas for @math all the components of @math are of size @math . We establish the threshold value @math for a phase transition in the graph @math of the vacant net of a simple random walk on a random @math -regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a non-backtracking random walk, and, for @math even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random @math -regular graphs. The main findings are the following: As @math increases the threshold for the vacant set converges to @math in all three walks. For the vacant net, the threshold converges to @math for both the simple random walk and non-backtracking random walk. When @math is even, the threshold for the vacant net of the unvisited edge process converges to @math , which is also the vertex cover time of the process. The preferential attachment graph G"m(n) is a random graph formed by adding a new vertex at each time step, with m edges which point to vertices selected at random with probability proportional to their degree. Thus at time n there are n vertices and mn edges. This process yields a graph which has been proposed as a simple model of the world wide web [A. Barabasi, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509-512]. In this paper we show that if m>=2 then whp the cover time of a simple random walk on G"m(n) is asymptotic to 2mm-1nlogn. Let @math be the largest component of the Erdős–Renyi random graph @math . The mixing time of random walk on @math in the strictly supercritical regime, p = c n with fixed c > 1, was shown to have order log2n by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, p = (1 + e) n where λ = e3n is bounded, Nachmias and Peres proved that the mixing time on @math is of order n. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of @math in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim. In this paper, we show that for p = (1 + e) n with λ = e3n → ∞ and λ = o(n), the mixing time on @math is with high probability of order (n λ)log2λ. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime [i.e., p = (1 − e) n with λ as above]. The aim of this article is to discuss some applications of random processes in searching and reaching consensus on finite graphs. The topics covered are: Why random walks?, Speeding up random walks, Random and deterministic walks, Interacting particles and voting, Searching changing graphs.