A Stable Marriage of Poisson and Lebesgue

Given a point process M of intensity one in the plane, the well-known Voronoi tesselation assigns a polygon (of different area) to each point of M. The geometry of “fair” allocations (assigning unit area to each point of M) is richer and more mysterious: see http://www.math.ubc.ca/~holroyd/stable.html

There is a unique “fair” allocation that is “stable” in the sense of the Gale-Shapley stable marriage problem, every point of M is assigned a bounded region with finitely many components, but obtaining any(!) tail estimate for the diameter of these regions is open. These allocations arose from the continuum version of the “extra head” problem, studied by Thorisson and Liggett. The original problem is to find in a sequence of i.i.d. coins with heads probability p, one coin that landed heads so that all other coins are still i.i.d. with heads probability p. [This is possible without randomization only when 1/p is an integer].

Talk based on joint works with C. Hoffman and A. Holroyd.

Speaker Details

Yuval Peres is a Principal Researcher and manager of the Theory group at Microsoft Research. Before joining MSR in 2006, he was a Professor at UC Berkeley.
He has also taught at Yale and at the Hebrew University. Yuval has published more than 160 papers with 90 co-authors and has mentored 15 PhD theses. His research encompasses most areas of probability theory, including random walks, Brownian motion, percolation, and random graphs. He has recently co-authored books on Markov chains and mixing times, on zeros of Gaussian analytic functions, and on Brownian motion. Yuval is an IMS fellow and a recipient of the Rollo Davidson prize. In 2001 he received the Loeve prize, awarded once every two years to a leading probabilist under the age of 45. In 2002, Yuval was an invited speaker at the International Congress of Mathematicians in Beijing and in 2009, he delivered a plenary talk at SODA. His favorite quote is from his son Alon, who was overheard at age 6 asking a friend: “Leo, do you have a religion? You know, a religion, like Christian, or Jewish, or Mathematics….?”

Date:
Speakers:
Yuval Peres
Affiliation:
UC Berkeley, Visiting MSR

    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Yuval Peres

      Yuval Peres

      Principal Researcher