Tail bounds for the stable marriage of Poisson and lebesgue

摘要

Let Ξ be a discrete set in R~d. Call the elements of Ξ centers. The well-known Voronoi tessellation partitions R~d into polyhedral regions (of varying volumes) by allocating each site of R~d to the closest center. Here we study allocations of R~d to Ξ in which each center attempts to claim a region of equal volume α. We focus on the case where Ξ arises from a Poisson process of unit intensity. In an earlier paper by the authors it was proved that there is a unique allocation which is stable in the sense of the Gale-Shapley marriage problem. We study the distance X from a typical site to its allocated center in the stable allocation. The model exhibits a phase transition in the appetite a. In the critical case α = 1 we prove a power law upper bound on X in dimension d = 1. (Power law lower bounds were proved earlier for all d). In the non-critical cases α < 1 and α > 1 we prove exponential upper bounds on X.