Concentration for Poisson U-statistics: Subgraph counts in random geometric graphs

Abstract

Concentration bounds for the probabilities P(N >= M r) and P(N <= M - r) are proved, where M is a median or the expectation of a subgraph count N associated with a random geometric graph built over a Poisson process. The lower tail bounds have a Gaussian decay and the upper tail inequalities satisfy an optimality condition. A remarkable feature is that the underlying Poisson process can have a.s. infinitely many points. The estimates for subgraph counts follow from tail inequalities for more general local Poisson U-statistics. These bounds are proved using recent general concentration results for Poisson U-statistics and techniques involving the convex distance for Poisson processes. (C) 2017 Elsevier B.V. All rights reserved.