Komlós–Major–Tusnády approximation

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,\dots$ be independent uniform (0,1) random variables. Define a uniform empirical distribution function as

$F_{U,n}(t)=\frac{1}{n}\sum _{i=1}^n{\mathrm{𝟏}}_{U_i\le 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\dots$ the empirical process $\{{\alpha }_{U,n}(t),0\le t\le 1\}$ can be approximated by a sequence of Brownian bridges $\{B_n(t),0\le t\le 1\}$ such that

$P\{\underset{0\le t\le 1}{\sup }|{\alpha }_{U,n}(t)-B_n(t)|>\frac{1}{\sqrt{n}}(a\log n+x)\}\le b{e}^{-cx}$

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,\dots ,$ 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

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{\sqrt{n}}{\ln n}\Vert {\alpha }_{X,n}-G_{F,n}{\Vert }_{\mathrm{\infty }}<\mathrm{\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.