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 (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 (n) / n in probability. Moreover, we give explicit exponential bounds for the error terms, intended for asymptotic as well as nonasymptotic use.