Random permutations and Brownian motion

Abstract

Consider the cycles of the random permutation of length n. Let X n (t) be the number of cycles with length not exceeding n', t e [0,1]. The random process Y n () = (X n (t) -tin n)/\rl /2 n is shown to converge weakly to the standard Brownian motion W(t),t e [0,1]. It follows that, as a process, the empirical distribution function of "loglengths" of the cycles weakly converges to the Brownian Bridge process. As another application, an alternative proof is given for the Erds-Turan Theorem: it states that the group-order of random permutation is asymptotically e, where ^is Gaussian with mean In 2 n/2 and variance In 3 n/3.