Poisson Matching

Details Poisson Matching Poisson Matching

2007-12-12

arxiv.org/abs/0712.1867v3

Mathematics

Probability

37 pages; to appear in Annales de l'institut Henri Poincare (B)

Scientific paper

Suppose that red and blue points occur as independent homogeneous Poisson processes in R^d. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For any such scheme in dimensions d=1,2, the matching distance X from a typical point to its partner must have infinite d/2-th moment, while in dimensions d>=3 there exist schemes where X has finite exponential moments. The Gale-Shapley stable marriage is one natural matching scheme, obtained by iteratively matching mutually closest pairs. A principal result of this paper is a power law upper bound on the matching distance X for this scheme. A power law lower bound holds also. In particular, stable marriage is close to optimal (in tail behavior) in d=1, but far from optimal in d>=3. For the problem of matching Poisson points of a single color to each other, in d=1 there exist schemes where X has finite exponential moments, but if we insist that the matching is a deterministic factor of the point process then X must have infinite mean.

Affiliated with

Also associated with

No associations

Rating

Poisson Matching 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 Poisson Matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Poisson Matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660971