Stephen P. Boyd
Home
Teaching
Biography
Research
Books
Papers
Software
People
Classes
ENGR108
EE104
EE263
EE363
EE364a
EE364b
EE365
MOOC
CVX101

Mixing Times for Random Walks on Geometric Random Graphs

S. Boyd, A. Ghosh, B. Prabhakar, D. Shah (listed in alphabetical order)

SIAM Workshop on Analytic Algorithmics & Combinatorics (ANALCO), Vancouver, January 2005.

A geometric random graph, G^d(n,r), is formed as follows: place n nodes uniformly at random onto the surface of the d-dimensional unit torus and connect nodes which are within a distance r of each other. The G^d(n,r) has been of great interest due to its success as a model for ad-hoc wireless networks. It is well known that the connectivity of G^d(n,r) exhibits a threshold property: there exists a constant alpha_d such that for any epsilon >0, for r^d < alpha_d (1-epsilon)log n/n, the G^d(n,r) is not connected with high probability, and for r^d > alpha_d (1+epsilon)log n/n, the G^d(n,r) is connected w.h.p. In this paper, we study mixing properties of random walks on G^d(n,r) for r^d(n)=Omega(log n/n). Specifically, we study the scaling of mixing times of the fastest-mixing reversible random walk, and the natural random walk. We find that the mixing time of both of these random walks have the same scaling laws and scale proportional to r^{-2} (for all d). These results hold for G^d(n,r) when distance is defined using any L_p norm. Though the results of this paper are not so surprising, they are nontrivial and require new methods. To obtain the scaling law for the fastest-mixing reversible random walk, we first explicitly characterize the fastest-mixing reversible random walk on a regular (grid-type) graph in d dimensions. We subsequently use this to bound the mixing time of the fastest-mixing random walk on G^d(n,r). In the course of our analysis, we obtain a tight relation between the mixing time of the fastest-mixing symmetric random walk and the fastest-mixing reversible random walk with a specified equilibrium distribution on an arbitrary graph. To study the natural random walk, we first generalize a method of Diaconis and Stroock (1991) to bound eigenvalues based on Poincare's inequality and then apply it to the G^d(n,r) graph.