Il est naturel de s’attendre à ce que la marche aléatoire sans rebroussement mélange plus vite que la marche aléatoire simple, mais jusqu’ici, cela n’était prouvé que dans le cas des graphes réguliers. Pour analyser le cas de graphes irréguliers typiques, soit $G$ un graphe aléatoire à $n$ sommets de degrés au moins $3$ et distribués selon une loi à queue exponentielle. On détermine le temps de mélange partant du pire point de départ pour la marche aléatoire simple sur $G$, et l’on montre qu’avec grande probabilité, cette marche présente le phénomène de cutoff au temps ${\mathbf{h}}^{-1}\log n$, où ${\mathbf{h}}$ est l’entropie asymptotique de la marche aléatoire simple sur un arbre de Galton–Watson qui est une approximation locale de $G$. (Précédemment, cela n’était connu que pour des points de départ typiques.) De plus, on montre que ce temps de mélange est strictement plus grand que celui de la marche aléatoire sans rebroussement, via une comparison délicate des entropies sur l’arbre de Galton–Watson.

In this paper we discuss the problem of estimating graph parameters from a random walk with restarts. In this setting, an algorithm observes the trajectory of a random walk over an unknown graph G, starting from a vertex x. The algorithm also sees the degrees along the trajectory. The only other power that the algorithm has is to request that the random walk be reset to its initial state at any given time, based on what it has seen so far. Our main results are as follows. For regular graphs G, one can estimate the number of vertices nG and the ℓ2 mixing time of G from x in steps, where is the uniform mixing time of the random walk on G. The algorithm is based on the number of intersections of random walk paths X, Y, ie. the number of times (t, s) such that Xt = Ys. Our method improves on previous methods by various authors which only consider collisions (ie. times t with Xt = Yt). We also show that the time complexity of our algorithm is optimal (up to log factors) for 3-regular graphs with prescribed mixing times. For general graphs, we adapt the intersections algorithm to compute the number of edges mG and the ℓ2 mixing time from the starting vertex x in steps. Under mild additional assumptions (which hold e.g. for sparse graphs) the number of vertices can also be estimated by this time. Finally, we show that these algorithms, which may take sublinear time, have a fundamental limitation: it is not possible to devise a sublinear stopping time at which one can be reasonably sure that our parameters are well estimated. On the other hand, we show that, given either ma or the mixing time of G, we can compute the “other parameter” with a self-stopping algorithm.

We consider the random walk on the hypercube which moves by picking an ordered pair (i,j) of distinct coordinates uniformly at random and adding the bit at location i to the bit at location j, modulo 2. We show that this Markov chain has cutoff at time (3/2)n*log(n) with window of size n, solving a question posed by Chung and Graham (1997).