Tail Bounds for the Stable Marriage of Poisson and Lebesgue

Christopher Hoffman, Alexander E. Holroyd, Yuval Peres

Published 2005-07-18Version 1

Let \Xi be a discrete set in R^d. Call the elements of \Xi 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 \Xi in which each center attempts to claim a region of equal volume \alpha. We focus on the case where \Xi arises from a Poisson process of unit intensity. It was proved in math.PR/0505668 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 \alpha. In the critical case \alpha=1 we prove a power law upper bound on X in dimension d=1. It is an open problem to prove any upper bound in d\geq 2. (Power law lower bounds were proved in math.PR/0505668 for all d). In the non-critical cases \alpha<1 and \alpha>1 we prove exponential upper bounds on X.