Tail Bounds for the Stable Marriage of Poisson and Lebesgue

Details Tail Bounds for the Stable Marriage of Poisson and Lebesgue Tail Bounds for the Stable Marriage of Poisson and Lebesgue

2005-07-18

arxiv.org/abs/math/0507324v1

Mathematics

Probability

30 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Tail Bounds for the Stable Marriage of Poisson and Lebesgue does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tail Bounds for the Stable Marriage of Poisson and Lebesgue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tail Bounds for the Stable Marriage of Poisson and Lebesgue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-188249