Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Probability Seminar

Matt Junge

PhD Student, University of Washington

Splitting hairs (with choice)

Abstract:

In the past decade computer science literature has studied the effect of introducing random choices to classical processes. For example, sequentially place n balls into n bins. For each ball, two bins are sampled uniformly and the ball is placed in the emptier of the two. This process does a much better job of evenly distributing the balls than the "choiceless" version where one places each ball uniformly. Consider the continuous version: Form a random sequence in the unit interval by having the n*th* term be whichever of two uniformly placed points falls in the larger gap between the previous n-1 points. I'll confirm the intuition that this sequence is a.s. equidistributed, solving an open problem from Itai Benjamini, Pascal Maillard and Elliot Paquette. The history goes back a century to Weyl and more recently to Kakutani. Several open problems will be discussed.

Host: Ruth Williams

April 2, 2015

10:00 AM

AP&M 7321

****************************