Hungarian Constructions from the Nonasymptotic Viewpoint

Let x₁, …, xₙ be independent random variables with uniform distribution over 0, 1, defined on a rich enough probability space Ω. Denoting by F̂ₙ the empirical distribution function associated with these observations and by αₙ the empirical Brownian bridge αₙ(t) = √ n(F̂ₙ(t) - t), Komlos, Major and Tusnady (KMT) showed in 1975 that a Brownian bridge B⁰ (depending on n) may be constructed on Ω in such a way that the uniform deviation \|αₙ - B⁰\|_∞ between αₙ and B⁰ is of order of log(n)/√ n in probability. In this paper, we prove that a Poisson bridge L⁰ₙ may be constructed on Ω (note that this construction is not the usual one) in such a way that the uniform deviations between any two of the three processes αₙ, L⁰ₙ and B⁰ are of order of log(n)/√ n in probability. Moreover, we give explicit exponential bounds for the error terms, intended for asymptotic as well as nonasymptotic use.