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.

Let ${\displaystyle U_{1},U_{2},\ldots }$ be independent uniform (0,1) random variables. Define a uniform empirical distribution function as

${\displaystyle F_{U,n}(t)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{U_{i}\leq t},\quad t\in [0,1].}$

Define a uniform empirical process as

${\displaystyle \alpha _{U,n}(t)={\sqrt {n}}(F_{U,n}(t)-t),\quad t\in [0,1].}$

The Donsker theorem (1952) shows that ${\displaystyle \alpha _{U,n}(t)}$ converges in law to a Brownian bridge ${\displaystyle 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. ${\displaystyle U_{1},U_{2}\ldots }$ the empirical process ${\displaystyle \{\alpha _{U,n}(t),0\leq t\leq 1\}}$ can be approximated by a sequence of Brownian bridges ${\displaystyle \{B_{n}(t),0\leq t\leq 1\}}$ such that

${\displaystyle P\left\{\sup _{0\leq t\leq 1}|\alpha _{U,n}(t)-B_{n}(t)|>{\frac {1}{\sqrt {n}}}(a\log n+x)\right\}\leq be^{-cx}}$

for all positive integers n and all ${\displaystyle x>0}$, where a, b, and c are positive constants.

A corollary of that theorem is that for any real iid r.v. ${\displaystyle X_{1},X_{2},\ldots ,}$ with cdf ${\displaystyle F(t),}$ it is possible to construct a probability space where independent^{[clarification needed]} sequences of empirical processes ${\displaystyle \alpha _{X,n}(t)={\sqrt {n}}(F_{X,n}(t)-F(t))}$ and Gaussian processes ${\displaystyle G_{F,n}(t)=B_{n}(F(t))}$ exist such that

${\displaystyle \limsup _{n\to \infty }{\frac {\sqrt {n}}{\ln n}}{\big \|}\alpha _{X,n}-G_{F,n}{\big \|}_{\infty }<\infty ,}$     almost surely.

• 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. doi:10.1007/BF00533093
• 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. doi:10.1007/BF00532688