The power of online thinning in reducing discrepancy

DOI10.1007/s00440-018-0860-yzbMath1421.68246arXiv1608.02895OpenAlexW2963541004WikidataQ129643582 ScholiaQ129643582MaRDI QIDQ2416548

Ori Gurel-Gurevich, Aaditya Ramdas, Raaz Dwivedi, Ohad Noy Feldheim

Publication date: 23 May 2019

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.02895

zbMATH Keywords

thinningdiscrepancyonline algorithmHaar waveletsubsamplingtwo-choices

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Online algorithms; streaming algorithms (68W27) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Choices, intervals and equidistribution
• On the small ball inequality in all dimensions
• The asymptotic behavior of spacings under Kakutani's model for interval subdivision
• A proof of Kakutani's conjecture on random subdivision of longest intervals
• Davenport's theorem in the theory of irregularities of point distribution
• Weak convergence results for the Kakutani interval splitting procedure.
• The power of thinning in balanced allocation
• Choices and intervals
• Explicit constructions in the classical mean squares problem in irregularities of point distribution
• Harmonic analysis on totally disconnected groups and irregularities of point distributions
• Graphical balanced allocations and the (1 + β)-choice process
• Balanced Allocations
• Balanced Allocations: A Simple Proof for the Heavily Loaded Case
• Roth’s Orthogonal Function Method in Discrepancy Theory and Some New Connections
• Discrepancy Theory and Quasi-Monte Carlo Integration
• High-dimensional integration: The quasi-Monte Carlo way
• Balanced Allocations: The Heavily Loaded Case
• Justification and Extension of Doob's Heuristic Approach to the Kolmogorov- Smirnov Theorems
• On irregularities of distribution

This page was built for publication: The power of online thinning in reducing discrepancy