Choices and Intervals (joint with Combinatorics Seminar)

Series
Stochastics Seminar
Time
Thursday, November 9, 2017 - 3:05pm for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Elliot Paquette – The Ohio State University – paquette.30@osu.edu
Organizer
Lutz Warnke
We study an online algorithm for making a well—equidistributed random set of points in an interval, in the spirit of "power of choice" methods. Suppose finitely many distinct points are placed on an interval in any arbitrary configuration. This configuration of points subdivides the circle into a finite number of intervals. At each time step, two points are sampled uniformly from the interval. Each of these points lands within some pair of intervals formed by the previous configuration. Add the point that falls in the larger interval to the existing configuration of points, discard the other, and then repeat this process. We then study this point configuration in the sense of its largest interval, and discuss other "power of choice" type modifications. Joint work with Pascal Maillard.