Abstract
Consider an infinite sequence of independent, uniformly chosen points from \([0,1]^d\). After looking at each point in the sequence, an overseer is allowed to either keep it or reject it, and this choice may depend on the locations of all previously kept points. However, the overseer must keep at least one of every two consecutive points. We call a sequence generated in this fashion a two-thinning sequence. Here, the purpose of the overseer is to control the discrepancy of the empirical distribution of points, that is, after selecting n points, to reduce the maximal deviation of the number of points inside any axis-parallel hyper-rectangle of volume A from nA. Our main result is an explicit low complexity two-thinning strategy which guarantees discrepancy of \(O(\log ^{2d+1} n)\) for all n with high probability [compare with \(\Theta (\sqrt{n\log \log n})\) without thinning]. The case \(d=1\) of this result answers a question of Benjamini. We also extend the construction to achieve the same asymptotic bound for (\(1+\beta \))-thinning, a set-up in which rejecting is only allowed with probability \(\beta \) independently for each point. In addition, we suggest an improved and simplified strategy which we conjecture to guarantee discrepancy of \(O(\log ^{d+1} n)\) [compare with \(\theta (\log ^d n)\), the best known construction of a low discrepancy sequence]. Finally, we provide theoretical and empirical evidence for our conjecture, and provide simulations supporting the viability of our construction for applications.
Similar content being viewed by others
References
Bilyk, D.: Roths orthogonal function method in discrepancy theory and some new connections. In: Chen, W., Srivastav, A., Travaglini, G. (eds.) A Panorama of Discrepancy Theory, pp. 71–158. Springer. Berlin (2014)
Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced allocations. SIAM J. Comput. 29(1), 180–200 (1999)
Peres, Y., Talwar, K., Wieder, U.: Graphical balanced allocations and the (\(1+\beta \))-choices process. Random Struct. Algorithms 47(4), 760–775 (2015)
Berenbrink, P., Czumaj, A., Steger, A., Vöcking, B.: Balanced allocations: the heavily loaded case. SIAM J. Comput. 35(6), 1350–1385 (2006)
Talwar, K., Wieder, U.: Balanced Allocations: A Simple Proof for the Heavily Loaded Case. International Colloquium on Automata, Languages, and Programming. Springer, Berlin (2014)
Mitzenmacher, M.: The power of two choices in randomized load balancing. Ph.D. thesis, University of California, Berkeley, CA (1996)
Feldheim, O.N., Gurel-Gurevich, O.: The power of thinning in ballanced allocation (2018) Preprint. arXiv:1807.01132 [math.PR]
Kakutani, S.: A problem of equidistribution on the unit interval \([0,1]\). In: Proceedings of Oberwolfach Conference on Measure Theory. Lecture Notes in Mathematics, vol. 541, pp. 367–376 (1975)
van Zwet, W.R.: A proof of Kakutanis conjecture on random subdivision of longest intervals. Annals Probab. 6(1), 133–137 (1978)
Lootgieter, J.C.: Sur la répartition des suites de Kakutani. Annales l’Inst. Henri Poincaré (B) Probab. Stat. 13(4), 385–410 (1977)
Donsker, M.: Justification and extension of Doobs heuristic approach to the Kolmogorov–Smirnov theorems. Annals Math. Stat. 23, 277–281 (1952)
Pyke, R.: The asymptotic behavior of spacings under Kakutani’s model for interval subdivision. Annals Probab. 8(1), 157–163 (1980)
Pyke, R., van Zwet, W.R.: Weak convergence results for the Kakutani interval splitting procedure. Annals Probab. 32(1), 380–423 (2004)
Maillard, P., Paquette, E.: Choices and intervals. Isr. J. Math. 212(1), 337–384 (2016)
Junge, M.: Choices, intervals and equidistribution. Electron. J. Probab. 20, 1 (2015)
Bilyk, D., Lacey, M.T., Vagharshakyan, A.: On the small ball inequality in all dimensions. J. Funct. Anal. 254(9), 2470–2502 (2008)
Roth, K.F.: On irregularities of distribution. Mathematika 1(02), 73–79 (1954)
Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge (2000)
Chen, W.W.L., Skriganov, M.M.: Explicit constructions in the classical mean squares problem in irregularities of point distribution. J. Reine Angew. Math. 545, 67–95 (2002)
Chen, W.W.L., Skriganov, M.M.: Davenport’s theorem in the theory of irregularities of point distribution. J. Math. Sci. 115(1), 2076–2084 (2003)
Skriganov, M.M.: Harmonic analysis on totally disconnected groups and irregularities of point distributions. J. Reine Angew. 600, 25–49 (2006)
Owen, A.B.: Statistically efficient thinning of a Markov chain sampler. J. Comput. Graph. Stat. 26(3), 738–744 (2017). https://doi.org/10.1080/10618600.2017.1336446
Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010)
Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied mathematics, Philadelphia (1992)
Dick, J., Kuo, F.Y., Sloan, I.H.: High-dimensional integration: the quasi-Monte Carlo way. Acta Numer. 22, 133–288 (2013)
Dick, J., Pillichshammer, F.: Discrepancy theory and quasi-Monte Carlo integration. In: Chen, W., Srivastav, A., Travaglini, G. (eds.) A Panorama of Discrepancy Theory, pp. 539–619. Springer, Berlin (2014)
Acknowledgements
The authors wish to thank Itai Benjamini for suggesting the model of the power of two choices on interval partitions, to Yuval Peres for introducing to us related recent litrature, to Art Owen and Asaf Nachmias for insightful discussions and to a anonymous referee for useful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Raaz Dwivedi: Research was supported by the Berkeley Fellowship. Ohad N. Feldheim: Research conducted in Stanford University and supported in part by NSF Grant DMS 1613091. Ori Gurel-Gurevich: Research was supported by the Israel Science Foundation (Grant No. 1707/16).
Rights and permissions
About this article
Cite this article
Dwivedi, R., Feldheim, O.N., Gurel-Gurevich, O. et al. The power of online thinning in reducing discrepancy. Probab. Theory Relat. Fields 174, 103–131 (2019). https://doi.org/10.1007/s00440-018-0860-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00440-018-0860-y