Tusnády's problem and online two-sample thinning
Abstract
We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension d≥ 2. The largest combinatorial discrepancy of N points in ℝd with respect to axis-parallel boxes is Θd((log N)d−1/2), extending Wei's planar result and matching Nikolov's upper bound. More strongly, with high probability, this lower bound holds simultaneously for every subset obtained by deleting at most a sufficiently small fixed fraction of a uniform N-point sample. We apply this geometric estimate to online thinning of two independent samples of size n from an unknown common distribution, where observations must be kept or discarded upon arrival. For every fixed dimension k≥ 1 and expected deletion budget ρn, with 0<ρ<2, we prove that the minimax expected prefix discrepancy over lower orthants is Θk,ρ((log n)k+1/2). In dimension one, the optimal terminal discrepancy is instead Θρ((loglog n)3/2), giving a sharp separation between the prefix and terminal objectives. For k≥ 2, we obtain terminal bounds differing by a factor of log n. The lower bounds are based on Gaussian small-ball estimates for box-incidence matrices, while the upper bounds use stationary Metropolis thinning and, in one dimension, a terminal cancellation procedure.
Related
- Resolving Tusnády's Problem
- A Note on a Result of Chen Li: the Thinning Problem via the Kernel Method
- Finite-Sample Distribution Theory and Efficient Large-Scale Inference for Online Quantile Regression
- On the sample complexity of the generalized hidden shift problem over arbitrary finite groups
- The Online Steinitz Problem
BibTeX
@misc{lei2026tusnádys,
title = {{Tusnády's problem and online two-sample thinning}},
author = {Yuhao Lei},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08455},
eprint = {2611.08455},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08455},
}
RIS
TY - UNPB
TI - Tusnády's problem and online two-sample thinning
AU - Yuhao Lei
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08455
UR - https://arxiv.org/abs/2611.08455
AB - We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension d≥ 2. The largest combinatorial discrepancy of N points in ℝ^d with respect to axis-parallel boxes is Θ_d((log N)^d−1/2), extending Wei's planar result and matching Nikolov's upper bound. More strongly, with high probability, this lower bound holds simultaneously for every subset obtained by deleting at most a sufficiently small fixed fraction of a uniform N-point sample. We apply this geometric estimate to online thinning of two independent samples of size n from an unknown common distribution, where observations must be kept or discarded upon arrival. For every fixed dimension k≥ 1 and expected deletion budget ρn, with 0<ρ<2, we prove that the minimax expected prefix discrepancy over lower orthants is Θ_k,ρ((log n)^k+1/2). In dimension one, the optimal terminal discrepancy is instead Θ_ρ((loglog n)^3/2), giving a sharp separation between the prefix and terminal objectives. For k≥ 2, we obtain terminal bounds differing by a factor of log n. The lower bounds are based on Gaussian small-ball estimates for box-incidence matrices, while the upper bounds use stationary Metropolis thinning and, in one dimension, a terminal cancellation procedure.
ER -