Criticality of the Exponential Rate of Decay for the Largest Nearest Neighbor Link in Random Geometric Graph

Abstract

Let n points be placed independently in d-dimensional space according to the densities $f(x)=A_d{e}^{-\lambda \Vert x{\Vert }^{\alpha }},\lambda >0,x\in {\Re }^d,d\ge 2.$ Let $d_n$ be the longest edge length for the nearest neighbor graph on these points. We show that $(\log (n){)}^{1-1/\alpha }{d}_n-b_n$ converges weakly to the Gumbel distribution where $b_n\sim \log \log n.$ We also show that the strong law result, % \lim_{n \to \infty} \frac{(λ^{-1}\log(n))^{1-1/α}d_n}{\sqrt{\log \log n}} \to \frac{d}{αλ}, a.s. % Thus, the exponential rate of decay i.e. $\alpha =1$ is critical, in the sense that for $\alpha >1,d_n\to 0,$ where as $\alpha <1,d_n\to \infty$ a.s. as $n\to \infty .$

Communicated to 'Stochastic Processes and Their Applications'. Sep. 11, 2006: replaced paper uploaded on Apr. 27, 2006 by a corrected version; errors/corrections found by the authors themselves