Tail Bounds for the Stable Marriage of Poisson and Lebesgue
| dc.creator | Hoffman, Christopher | |
| dc.creator | Holroyd, Alexander E. | |
| dc.creator | Peres, Yuval | |
| dc.date | 2005-07-18 | |
| dc.date.accessioned | 2026-07-07T05:21:45Z | |
| dc.date.available | 2026-07-07T05:21:45Z | |
| dc.description | 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. 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 α. In the critical case α=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 α<1 and α>1 we prove exponential upper bounds on X. | |
| dc.description | 30 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/math/0507324 | |
| dc.identifier | http://arxiv.org/abs/math/0507324 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/75801 | |
| dc.subject | Probability | |
| dc.subject | 60D05 | |
| dc.title | Tail Bounds for the Stable Marriage of Poisson and Lebesgue | |
| dc.type | text |