Tusnády's problem and online two-sample thinning
Authors: Yuhao Lei
Abstract
We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension $d\ge 2$. The largest combinatorial discrepancy of $N$ points in $\mathbb{R}^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\ge 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 $Θ_ρ((\log\log n)^{3/2})$, giving a sharp separation between the prefix and terminal objectives. For $k\ge 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.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Resolving Tusn\'ady's ProblemNicola Wengiel · 2026 · Not summarized yet
Resolving Tusn'ady's Problem proves the sharp fixed-dimensional discrepancy order for anchored boxes, the geometric question this paper also settles.
Abstract
We prove a lower bound of $\Omega_d((\log N)^{d-1/2})$ for the worst-case combinatorial discrepancy of $N$-point sets with respect to anchored boxes in every fixed dimension $d\ge3$. Together with Nikolov's upper bound of the same order and Wei's planar lower bound, this settles Tusn\'ady's problem: the discrepancy of axis-parallel boxes is $\Theta_d((\log N)^{d-1/2})$ in every fixed dimension $d\ge2$. The proof combines smoothed product test functions, sampling discretization, and an entropy argument for conditioned Gaussian vectors.
-
Thinning to Improve Two‐Sample DiscrepancyGleb Smirnov, Roman Vershynin · 2025 · Random Structures & Algorithms · cited 4 times · Not summarized yet
Thinning to Improve Two-Sample Discrepancy gives an online algorithm that discards points to reduce two-sample discrepancy, a problem this paper sharpens.
Abstract
The discrepancy between two independent samples X1,…,Xn$$ {X}_1,\dots, {X}_n $$ and Y1,…,Yn$$ {Y}_1,\dots, {Y}_n $$ drawn from the same distribution on ℝd$$ {\mathbb{R}}^d $$ typically has order O(n)$$ O\left(\sqrt{n}\right) $$ even in one dimension. We give a simple online algorithm that reduces the discrepancy to O(log2dn)$$ O\left({\log}^{2d}n\right) $$ by discarding a small fraction of the points.
-
The power of online thinning in reducing discrepancyRaaz Dwivedi, O. Feldheim, O. Gurel-Gurevich et al. · 2016 · Probability theory and related fields · cited 28 times · Not summarized yet
The power of online thinning studies online rejection of uniform points to control discrepancy, rather than thinning two samples from an unknown common distribution.
Abstract
Consider an infinite sequence of independent, uniformly chosen points from [0,1]d\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[0,1]^d$$\end{document}. 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 c…
-
Optimal Online Discrepancy MinimizationJanardhan Kulkarni, Victor Reis, T. Rothvoss · 2023 · Symposium on the Theory of Computing · cited 31 times · Not summarized yet
Optimal Online Discrepancy Minimization balances arriving vectors on every prefix, an online balancing problem adjacent to this paper's prefix discrepancy objective.
Abstract
We prove that there exists an online algorithm that for any sequence of vectors v1,…,vT ∈ ℝn with ||vi||2 ≤ 1, arriving one at a time, decides random signs x1,…,xT ∈ { −1,1} so that for every t ≤ T, the prefix sum ∑i=1t xivi is 10-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums O(√log(nT))-subgaussian, and gives a O(√logT) bound on the discrepancy maxt ∈ T ||∑i=1t xi vi||∞. Our proof combines a generalization of Banaszczyk’s prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching Ω(√logT) strategy for an oblivious adversary.
-
Tight Bounds for Tusn\'ady's Problem in the PlaneZhe-Wei Wei · 2026 · cited 2 times · Not summarized yet
Tight Bounds for Tusn'ady's Problem in the Plane proves the planar lower bound that the paper extends to higher fixed dimensions.
Abstract
We show that the worst-case combinatorial discrepancy of $n$ points in the plane with respect to axis-parallel rectangles is $\Theta(\log^{3/2}n)$. The known bounds were $\Omega(\log n)$ and $O(\log^{3/2}n)$; we prove the matching lower bound. It holds for random point sets: for every $A>0$, there is a constant $c_A>0$ such that, with probability at least $1-e^{-An}$, every coloring of $n$ independent uniform points in the unit square has an anchored rectangle with imbalance at least $c_A(\log_2n)^{3/2}$. The proof is surprisingly simple and elementary. It reveals one coordinate digit by digit. With overwhelming probability over the points, the conditional gains of an oscillation potential a…
-
Tusnády's problem, the transference principle, and non-uniform QMC samplingC. Aistleitner, D. Bilyk, Aleksandar Nikolov · 2016 · arXiv.org · preprint, not peer reviewed · cited 27 times · Not summarized yet
Tusnády's problem, the transference principle, and non-uniform QMC sampling studies point-set discrepancy for general measures, rather than the paper's sharp lower bounds and online thinning.
Abstract
It is well-known that for every \(N \ge 1\) and \(d \ge 1\) there exist point sets \(x_1, \dots , x_N \in [0,1]^d\) whose discrepancy with respect to the Lebesgue measure is of order at most \((\log N)^{d-1} N^{-1}\). In a more general setting, the first author proved together with Josef Dick that for any normalized measure \(\mu \) on \([0,1]^d\) there exist points \(x_1, \dots , x_N\) whose discrepancy with respect to \(\mu \) is of order at most \((\log N)^{(3d+1)/2} N^{-1}\). The proof used methods from combinatorial mathematics, and in particular a result of Banaszczyk on balancings of vectors. In the present note we use a version of the so-called transference principle together with re…
-
Discrepancy theory, Tverberg's theorem, and regression depthA. Lopez, Pablo Soberón · 2026 · Not summarized yet
Discrepancy theory, Tverberg's theorem, and regression depth uses discrepancy-related ideas to study partitions resilient to point or hyperplane deletion.
Abstract
We prove new bounds for Tverberg's theorem with tolerance. We show that $N = rt+\Theta_{d,r}(t^{1/2-1/(2d)})$, where $N$ is the smallest number such that any set of $N$ points in $\mathbb{R}^d$ has a partition into $r$ parts such that the convex hulls of the parts intersect even if we remove any $t$ of the points. We extend Tverberg's theorem with tolerance to families of hyperplanes in $\mathbb{R}^d$, and show that for any set of $rt + O_{d,r}(t^{1/2-1/(2d)}\sqrt{\log (t+1)})$ hyperplanes in $\mathbb{R}^d$ there exists a partition of them into $r$ parts such that the regression hulls of the parts intersect even if any $t$ hyperplanes are removed. Our bounds follow from establishing a connec…
-
Tighter Bounds for the Discrepancy of Boxes and PolytopesAleksandar Nikolov · 2017 · arXiv.org · preprint, not peer reviewed · cited 32 times · Not summarized yet
Tighter Bounds for the Discrepancy of Boxes and Polytopes studies combinatorial discrepancy for geometric set systems, including boxes.
Abstract
Combinatorial discrepancy is a complexity measure of a collection of sets which quantifies how well the sets in the collection can be simultaneously balanced. More precisely, we are given an n-point set $P$, and a collection $\mathcal{F} = \{F_1, ..., F_m\}$ of subsets of $P$, and our goal is color $P$ with two colors, red and blue, so that the largest absolute difference between the number of red elements and the number of blue elements (i.e. the discrepancy) in any $F_i$ is minimized. Combinatorial discrepancy has many applications in mathematics and computer science, including constructions of uniformly distributed point sets, and lower bounds for data structures and private data analysis…
Prior work it builds on
-
Surveys in Combinatorics, 1989: On the method of bounded differencesC. McDiarmid · 1989 · cited 2,247 times · Not summarized yet
On the method of bounded differences provides a generic probabilistic method cited by this paper, not results about box discrepancy or thinning.
-
Discrepancy minimization via a self-balancing walkRyan Alweiss, Yang P. Liu, Mehtaab Sawhney · 2020 · Symposium on the Theory of Computing · cited 87 times · Not summarized yet
Discrepancy minimization via a self-balancing walk analyzes online vector balancing, a broader online discrepancy problem than two-sample thinning.
Abstract
We study discrepancy minimization for vectors in ℝn under various settings. The main result is the analysis of a new simple random process in high dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for online vector balancing against oblivious adversaries, resolving several questions posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as a linear time algorithm for logarithmic bounds for the Komlós conjecture.
-
Discrepancy and Fisher informationGleb Smirnov, Roman Vershynin · 2026 · cited 6 times · Not summarized yet
Discrepancy and Fisher information controls a random walk by discarding steps, sharing the online deletion strategy but not the box-discrepancy objective.
Abstract
We give an online algorithm that keeps a symmetric random walk inside a convex body by discarding some of its steps. The expected number of discarded steps is controlled by a Fisher-information-type quantity associated with the body. For the cube, this gives a dimension-free bound: a walk with unit Euclidean steps can be kept bounded in all coordinates while discarding only a small constant fraction of the steps on average.
-
Regularizing Random Points by Deleting a FewD. Bilyk, Stefan Steinerberger · 2025 · Journal of Geometric Analysis · cited 4 times · Not summarized yet
Regularizing Random Points by Deleting a Few studies improving the discrepancy of random points through deletion, as this paper does for box discrepancy.
Abstract
It is well understood that if one is given a set X⊂[0,1]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X \subset [0,1]$$\end{document} of n independent uniformly distributed random variables, then sup0≤x≤1#X∩[0,x]#X-x≲lognnwithhighprobability.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \sup _{0 \le x \le 1} \left|…
-
A Gaussian small deviation inequality for convex functionsG. Paouris, P. Valettas · 2016 · arXiv: Probability · preprint, not peer reviewed · cited 42 times · Not summarized yet
A Gaussian small deviation inequality for convex functions supplies Gaussian small-ball estimates used by this paper's lower-bound arguments.
Abstract
Let $Z$ be an $n$-dimensional Gaussian vector and let $f: \mathbb R^n \to \mathbb R$ be a convex function. We show that: $$\mathbb P \left( f(Z) \leq \mathbb E f(Z) -t\sqrt{ {\rm Var} f(Z)} \right) \leq \exp(-ct^2),$$ for all $t>1$, where $c>0$ is an absolute constant. As an application we derive variance-sensitive small ball probabilities for Gaussian processes.
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 9 November 2026.