Dynamics seminar:Ohad Feldheim (Stanford): The power of two-choices in reducing discrepancy

Tue, 27/06/201714:00-15:00
Consider a process in which points are assigned uniformly and independently at random on the interval [0,1]. It is a classical observation that after N points were assigned, the typical discrepancy of the empirical distribution, i.e., the maximum difference between the proportion of points on any interval and the length of that interval, is of order 1/sqrt{N}. Now consider a similar online process in which at every step an overseer is allowed to choose between two independent, uniformly chosen points on [0,1].   -- By how much can the overseer reduce the discrepancy of the selected points?
We show that a significant improvement is possible, providing an explicit algorithm which obtains a discrepancy of O(log^3 N/N) for all $N$ with high probability. This deviates by merely a factor of log^2 N from the lowest discrepancy possible for any sequence of points on [0,1]. We generalise this result to high dimensions to obtain near optimal discrepancy of O(log^(2d+1) N/N) on [0,1]^d using a similar process. We further generalise the results
to settings where the overseer has even less control over the output sequence.
The methods used relate classical results on the "power of two choices" in computer science, observations regarding Haar wavelets in harmonic analysis and properties of stochastic processes drifting towards their means. However, no prior knowledge on these topics is assumed.
Based on joint works with Ori Gurel-Gurevisch for HUJI and with Aaditya Ramdas and Raz Dwivedi from Berkely.