The mixing time of the Newman–Watts small world

Abstract. “Small worlds ” are large systems in which any given node has only a few con-nections to other points, but possessing the property that all pairs of points are connected by a short path, typically logarithmic in the number of nodes. The use of random walks for sampling a uniform element from a large state space is by now a classical technique; to prove that such a technique works for a given network, a bound on the mixing time is re-quired. However, little detailed information is known about the behaviour of random walks on small-world networks, though many predictions can be found in the physics literature. The principal contribution of this paper is to show that for a famous small-world random graph model known as the Newman–Watts small world, the mixing time is of order log2 n. This confirms a prediction of Richard Durrett, who proved a lower bound of order log2 n and an upper bound of order log3 n. 1