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

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 Rᵈ 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.