Tusnády's problem and online two-sample thinning

Yuhao Lei

AI summary · arXiv: 2611.08455v1 · math.CO

Tusnády's problem and online two-sample thinning

Yuhao Lei

How to read this summary? Illustrated guide

The essentials

The paper establishes sharp discrepancy bounds for Tusnády’s problem and online thinning, including a separation between prefix and terminal objectives.

Based on the abstract only: check the details in the original paper.

Question

What is the sharp order of combinatorial discrepancy for axis-parallel boxes in fixed dimensions, including after a small fraction of points is deleted? What discrepancy can online thinning achieve for two samples from an unknown common distribution?

Method

The paper studies the largest combinatorial discrepancy of point sets in fixed-dimensional Euclidean space and the minimax expected discrepancy when observations from two independent samples of size n are kept or discarded on arrival, under expected deletion budget ρn. Its lower bounds use Gaussian small-ball estimates for box-incidence matrices; upper bounds use stationary Metropolis thinning and, in one dimension, a terminal cancellation procedure.

Findings

Result For fixed d ≥ 2, the largest combinatorial discrepancy for N points in R^d with respect to axis-parallel boxes is Θ_d((log N)^{d−1/2}).
See the passage in the paper
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.
Result With high probability, the stated lower bound holds simultaneously for every subset obtained by deleting at most a sufficiently small fixed fraction of a uniform sample.
See the passage in the paper
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.
Result For every fixed k ≥ 1 and 0 < ρ < 2, the minimax expected prefix discrepancy in online thinning is Θ_{k,ρ}((log n)^{k+1/2}).
See the passage in the paper
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})$.
Result In one dimension, the optimal terminal discrepancy is Θ_ρ((log log n)^{3/2}), sharply differing from the prefix objective.
See the passage in the paper
In dimension one, the optimal terminal discrepancy is instead $Θ_ρ((\log\log n)^{3/2})$, giving a sharp separation between the prefix and terminal objectives.
Result For k ≥ 2, the paper establishes terminal bounds whose orders differ by a factor of log n.
See the passage in the paper
For $k\ge 2$, we obtain terminal bounds differing by a factor of $\log n$.

Limitations

For dimensions k ≥ 2, the terminal discrepancy bounds are not sharp to within a constant factor.
See the passage in the paper
For $k\ge 2$, we obtain terminal bounds differing by a factor of $\log n$.
The Tusnády discrepancy result is stated for fixed dimensions d ≥ 2, so the abstract does not establish the claimed order for dimension one.
See the passage in the paper
We determine the sharp order of discrepancy in Tusnády's problem in every fixed dimension $d\ge 2$.

Why it matters

The authors resolve the sharp order of Tusnády’s problem in every fixed dimension at least two, extending the planar result and matching a known upper bound. They also show that online prefix control and terminal discrepancy can have sharply different optimal orders, particularly in one dimension.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Tusnády’s problem; combinatorial discrepancy; online thinning; prefix discrepancy; terminal discrepancy

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

The paper studies two related discrepancy problems. The first, Tusnády’s problem, asks how large the imbalance can be when points in Euclidean space are assigned signs and tested against all axis-parallel boxes. The second concerns online thinning: two independent samples from the same unknown distribution arrive over time, and each observation must be kept or discarded as it appears. The goal is to control the difference between the retained samples over every initial segment, or prefix, of the stream. For the geometric problem, the paper determines the sharp order of the largest combinatorial discrepancy for $N$ points in fixed dimension $d \ge 2$. It proves that this discrepancy is of order $(\log N)^{d-1/2}$, with constants depending on $d$. This extends Wei’s planar result to every fixed dimension and matches an upper bound previously obtained by Nikolov. The paper also establishes a robust lower bound: with high probability, for a uniform sample of $N$ points, the bound continues to hold after deleting any set containing at most a sufficiently small fixed fraction of the points. This robustness is important when applying the geometric result to thinning, which itself removes observations. For online thinning in fixed dimension $k$, the paper considers two independent samples of size $n$ from an unknown common distribution, with an expected deletion budget of $\rho n$, where $0 \le \rho \le 2$. It proves that the minimax expected discrepancy over lower orthants, uniformly across prefixes, is of order $(\log n)^{k+1/2}$. Thus, the worst achievable scale grows with dimension, and the paper establishes matching upper and lower bounds for the prefix objective. The paper also distinguishes prefix discrepancy from terminal discrepancy, which measures imbalance only at the end of the stream. In dimension one, the optimal terminal discrepancy is of order $(\log\log n)^{3/2}$, substantially smaller than the optimal prefix discrepancy, which is of order $(\log n)^{3/2}$. This gives a sharp separation between the two objectives. For dimensions $k \ge 2$, the terminal upper and lower bounds differ by a factor of $\log n$, so the results do not fully determine the sharp terminal order in those dimensions. The lower-bound arguments use Gaussian small-ball estimates for matrices that describe which points lie in which boxes. The upper bounds rely on stationary Metropolis thinning; for the one-dimensional terminal result, the authors also use a cancellation procedure. Taken together, the results settle the order of Tusnády’s discrepancy in every fixed dimension $d \ge 2$ and establish sharp prefix bounds for online thinning, while showing that terminal balancing can be substantially better in one dimension. This summary is based only on the supplied abstract; the full text was not available. Accordingly, details such as the precise algorithmic setup, constants, probability estimates, and proofs cannot be assessed.

Tusnády’s Problem and Online Two-Sample Thinning

How uneven can a set of points look when measured through every axis-parallel box? And can two samples arriving over time be balanced without knowing the distribution that produced them? Yuhao Lei’s paper, “Tusnády’s problem and online two-sample thinning,” studies these questions through the shared language of discrepancy: the size of the imbalance between objects assigned to two sides or groups.

The paper establishes a sharp answer to a long-standing geometric question in every fixed dimension of at least two. It also proves matching bounds for a related online task, where observations must be kept or discarded as they arrive. Along the way, it highlights an important distinction: balancing every stage of a process can be much harder than balancing only its final outcome.

Measuring imbalance with boxes

In Tusnády’s problem, each of $N$ points in Euclidean space is assigned a sign, either positive or negative. For any axis-parallel box, one can add the signs of the points inside it. The discrepancy is the largest absolute sum over all such boxes. A good assignment keeps these sums small, even for the box that reveals the greatest imbalance.

For fixed dimension $d \ge 2$, the paper shows that the largest possible discrepancy among sets of $N$ points has order $(\log N)^{d-1/2}$, with constants that may depend on the dimension. This settles the order of the problem in every fixed dimension covered by the result. It extends an earlier planar result to higher dimensions and matches a previously known upper bound.

The result also has a robust form. For a uniform random sample of $N$ points, the lower bound holds with high probability even after deleting any set containing up to a sufficiently small fixed fraction of the points. In other words, the difficult-to-balance structure does not disappear just because a modest number of observations are removed.

Balancing two streams online

The second problem applies discrepancy ideas to online thinning. Two independent samples of size $n$ come from the same unknown distribution. As each observation arrives, it must be either retained or discarded. The aim is to make the retained samples resemble one another across sets called lower orthants—geometric regions defined by coordinate-wise upper limits.

Crucially, the comparison is made at every initial segment, or prefix, of the stream. The algorithm must control imbalance as it goes, not just after all observations have arrived. For fixed dimension $k$, and an expected deletion budget of $\rho n$ for $0 \le \rho \le 2$, the paper proves that the minimax expected prefix discrepancy is of order $(\log n)^{k+1/2}$. This is a sharp result: the upper and lower bounds agree in their dependence on $n$, and the scale grows with dimension.

The geometric result supports the thinning lower bound because thinning itself removes observations. A discrepancy lower bound that survives a small fraction of deletions can therefore still reveal unavoidable imbalance after observations have been discarded. For the upper bounds, the paper uses stationary Metropolis thinning.

Why the endpoint can be easier

Keeping imbalance controlled throughout a stream is not the same as controlling it only at the end. The latter objective, called terminal discrepancy, ignores what happens at earlier prefixes. The paper makes this contrast especially clear in one dimension.

For prefix discrepancy in dimension one, the optimal scale is $(\log n)^{3/2}$.
For terminal discrepancy in dimension one, the optimal scale is only $(\log\log n)^{3/2}$.

This is a sharp separation: balancing the final result is substantially easier than maintaining balance continuously. The terminal upper bound uses a cancellation procedure in addition to the paper’s other methods. In dimensions $k \ge 2$, however, the terminal upper and lower bounds still differ by a factor of $\log n$. The sharp terminal order in those dimensions therefore remains unresolved by these results.

What the results establish

Taken together, the findings settle the order of Tusnády’s discrepancy in every fixed dimension $d \ge 2$, and give matching minimax bounds for online prefix thinning in fixed dimension. They also show that the choice of objective matters: in one dimension, a method can achieve far better balance at the endpoint than it can guarantee at every moment along the way.

The lower-bound arguments use Gaussian small-ball estimates for matrices encoding which points fall inside which boxes. This provides a route from geometric structure to unavoidable imbalance. The available summary does not provide enough information to assess the precise algorithmic setup, constants, probability estimates, or proofs. Still, the broad picture is clear: robust geometric discrepancy gives insight into online selection, while the gap between prefix and terminal goals exposes a fundamental cost of staying balanced over time.

Created on 09 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

⚠The license of the paper does not allow us to build upon its content and the AI assistant only knows about the paper metadata rather than the full article.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Mathematics and statistics this week" of 9 November 2026. Mathematics and statistics this week: Where geometry sets the limits

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

Tusnády's problem and online two-sample thinning

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

Tusnády’s Problem and Online Two-Sample Thinning

Measuring imbalance with boxes

Balancing two streams online

Why the endpoint can be easier

What the results establish

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Prior work it builds on

Go further

Cite this paper (BibTeX)