Mixing Times of Random Walks on Geometric Random Graphs

URL:

http://www.stanford.edu/~boyd/gnr_mix.html

Abstract:

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.