Mixing Times for Random Walks on Geometric Random Graphs

A geometric random graph, Gd (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 Gd (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 Gd (n, r) exhibits a threshold property: there exists a constant αd such that for any ² > 0, for r d < αd(1 − ²)log n/n the Gd (n, r) is not connected with high probability 1 and for r d > αd(1 + ²)log n/n the Gd (n, r) is connected w.h.p.. In this paper, we study mixing properties of random walks on Gd (n, r) for r d (n) = ω(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 Gd (n, r) when distance is defined using any Lp 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 Gd (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 [DS91] to bound eigenvalues based on Poincare’s inequality and then apply it to the Gd (n, r) graph.

We note that the methods utilized in this paper are novel and general enough to be useful in the context of other graphs.