View source for 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 (mathematician)|János Komlós]], [[Gábor Tusnády]], and [[Péter Major]], who proved it in 1975.

==Theory==

Let <math>U_1,U_2,\ldots</math> be independent [[Uniform distribution (continuous)|uniform]] (0,1) [[random variable]]s. Define a uniform [[empirical distribution function]] as
:<math>F_{U,n}(t)=\frac{1}{n}\sum_{i=1}^n \mathbf{1}_{U_i\leq t},\quad t\in [0,1].</math>
Define a uniform [[empirical process]] as
:<math>\alpha_{U,n}(t)=\sqrt{n}(F_{U,n}(t)-t),\quad t\in [0,1].</math>
The [[Donsker theorem]] (1952) shows that <math>\alpha_{U,n}(t)</math> [[convergence of random variables|converges in law]] to a [[Brownian bridge]] <math>B(t).</math> 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. <math>U_1,U_2\ldots</math> the empirical process <math>\{\alpha_{U,n}(t), 0\leq t\leq 1\}</math> can be approximated by a sequence of Brownian bridges <math>\{B_n(t),0\leq t\leq 1\}</math> such that
::<math>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 b e^{-cx}</math>
:for all positive integers ''n'' and all <math>x>0</math>, where ''a'', ''b'', and ''c'' are positive constants.

===Corollary===
A corollary of that theorem is that for any real [[iid]] r.v. <math>X_1,X_2,\ldots,</math> with [[Cumulative distribution function|cdf]] <math>F(t),</math> it is possible to construct a probability space where independent{{Clarify|reason=surely alpha and B can't be independent, so what is independent of what?|date=January 2012}} sequences of empirical processes <math>\alpha_{X,n}(t)=\sqrt{n}(F_{X,n}(t)-F(t))</math> and [[Gaussian process]]es <math>G_{F,n}(t)=B_n(F(t))</math> exist such that
: <math>
    \limsup_{n\to\infty} \frac{\sqrt{n}}{\ln n} \big\| \alpha_{X,n} - G_{F,n} \big\|_\infty < \infty, 
  </math> &nbsp;&nbsp;&nbsp;&nbsp;[[almost surely]].

{{No footnotes|date=November 2010}}

==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. {{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 }}

{{DEFAULTSORT:Komlos-Major-Tusnady Approximation}}
[[Category:Empirical process]]