Komlós–Major–Tusnády approximation explained

In probability theory, the Komlós–Major–Tusnády approximation (also known as the KMT approximation, the KMT embedding, or the Hungarian embedding) refers to one of the two strong embedding theorems: 1) approximation of random walk by a standard Brownian motion constructed on the same probability space, and 2) an approximation of the empirical process by a Brownian bridge constructed on the same probability space. It is named after Hungarian mathematicians János Komlós, Gábor Tusnády, and Péter Major, who proved it in 1975.

Theory

Let

U _{1,U} _{2,\ldots} be independent uniform (0,1) random variables. Define a uniform empirical distribution function asF _{U,n} (t) = (1)/(n) \sum ^{n} _{i =1} 1 _{U _{i\leq} t} , t\in [ 0 , 1 ]. Define a uniform empirical process as\alpha _{U,n} (t) = \sqrt{n}(F _{U,n} (t) - t), t\in [ 0 , 1 ]. The Donsker theorem (1952) shows that \alpha _{U,n} (t) converges in law to a Brownian bridge B(t). Komlós, Major and Tusnády established a sharp bound for the speed of this weak convergence.

Theorem (KMT, 1975) On a suitable probability space for independent uniform (0,1) r.v.

U _{1,U} _{2\ldots} the empirical process \{\alpha _{U,n} (t), 0 \leq t\leq 1 \} can be approximated by a sequence of Brownian bridges \{B _{n(t),0\leq} t\leq 1 \} such thatP\left\{\sup _{0\leq} |\alpha _{U,n} (t) - B _{n(t)|> (1)/(\sqrt{n)} }(a\log n+x)\right\}\leq b e^

for all positive integers n and all

x> 0 , where a, b, and c are positive constants.

Corollary

A corollary of that theorem is that for any real iid r.v.

X _{1,X} _{2,\ldots,} with cdf F(t), it is possible to construct a probability space where independent sequences of empirical processes \alpha _{X,n} (t) = \sqrt{n}(F _{X,n} (t) - F(t)) and Gaussian processes G _{F,n} (t) = B _{n(F(t))} exist such that\limsup _{n\toinfty} (\sqrt{n)/() } \big\| \alpha_ - G_ \big\|_\infty < \infty,     almost surely.

References

• Komlos, J., Major, P. and Tusnady, G. (1975) An approximation of partial sums of independent rv’s and the sample df. I, Wahrsch verw Gebiete/Probability Theory and Related Fields, 32, 111–131.
• Komlos, J., Major, P. and Tusnady, G. (1976) An approximation of partial sums of independent rv’s and the sample df. II, Wahrsch verw Gebiete/Probability Theory and Related Fields, 34, 33–58.