probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...

, 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 In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb ...

by a standard

Brownian motion Brownian motion, or pedesis (from grc, πήδησις "leaping"), is the random motion of particles suspended in a medium (a liquid or a gas). This pattern of motion typically consists of random fluctuations in a particle's position insi ...

constructed on the same

probability space In probability theory, a probability space or a probability triple (\Omega, \mathcal, P) is a mathematical construct that provides a formal model of a random process or "experiment". For example, one can define a probability space which models t ...

, and 2) an approximation of the

empirical process In probability theory, an empirical process is a stochastic process that describes the proportion of objects in a system in a given state. For a process in a discrete state space a population continuous time Markov chain or Markov population model ...

by a Brownian bridge constructed on the same

. 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 A uniform is a variety of clothing worn by members of an organization while participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency services, se ...

(0,1)

random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the p ...

s. Define a uniform

empirical distribution function In statistics, an empirical distribution function (commonly also called an empirical Cumulative Distribution Function, eCDF) is the distribution function associated with the empirical measure of a sample. This cumulative distribution function ...

as :

F_(t)=\frac\sum_^n \mathbf_,\quad t\in,1

Define a uniform

as :

\alpha_(t)=\sqrt(F_(t)-t),\quad t\in,1

The

Donsker theorem In probability theory, Donsker's theorem (also known as Donsker's invariance principle, or the functional central limit theorem), named after Monroe D. Donsker, is a functional extension of the central limit theorem. Let X_1, X_2, X_3, \ldots be ...

(1952) shows that

\alpha_(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

for independent uniform (0,1) r.v.

U_1,U_2\ldots

the empirical process

\

can be approximated by a sequence of Brownian bridges

\

such that ::

P\left\\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_(t)=\sqrt(F_(t)-F(t))

and

Gaussian process In probability theory and statistics, a Gaussian process is a stochastic process (a collection of random variables indexed by time or space), such that every finite collection of those random variables has a multivariate normal distribution, i.e. ...

G_(t)=B_n(F(t))

exist such that :

\limsup_ \frac \big\,  \alpha_ - G_ \big\, _\infty < \infty,

almost surely In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0 ...

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. {{DEFAULTSORT:Komlos-Major-Tusnady Approximation Empirical process