The power of two-choices in reducing discrepancy

The power of two-choices in reducing discrepancy

Probability Seminar
Sep 7, 2016, 03:10 PM - 04:00 PM | 1011 Evans Hall | Happening As Scheduled
Ohad Feldheim, Stanford University
A classical computation tells us that the empirical measure of $N$ points uniformly tossed on the interval [0,1] has interval variation of 1/N^{0.5}. Compare this with an online process in which at every step an overseer is allowed to choose between two uniformly tossed points on [0,1]. How much can the overseer regulate the interval variation of the empirical distribution of the selected...