Manjunath Krishnapur

A proof of the KMT theorem

The Komlós-Major-Tusnády theorem for simple symmetric random walk on integers asserts that up to n steps, its path can be coupled to stay within distance log(n) of a Brownian motion run for time n. A second KMT theorem says that the empirical distribution function of n i.i.d. uniform random variables on [0,1] can be coupled to stay within log(n)/√n distance of a Brownian bridge.

Adding the simple idea of Cauchy criterion to existing proof architectures, we obtain (perhaps) simpler proofs of the above theorems. The first proof compares two Binomial distributions by combinatorial methods. The second proof compares Binomial and hypergeometric distributions among themselves by coupling Markov chains on integers that have these as stationary distributions. This is based on Chatterjee's proof via a form of Stein's method.

We shall give an overview of the result and elaborate on the second proof.