A Coupling Proof of the Asymptotic Normality of the Permutation Oscillation
John E. Angus · Probability in the Engineering and Informational Sciences · 1995
For eachn≥ 1, let Πn= (π1, π2, …, πn) be a random permutation of the integers 1,2, …,n. The quantityBn= Σ measures the degree of oscillation of Πnand is an important measure in the study of sorting algorithms. In this work the asymptotic normality ofBnis derived under the assumption that, for eachn≥ 1, Πnis uniformly distributed over then! permutations of 1,2, …,n. The proof relies on coupling (π1, π2, …, πn) with a sequence of independent and identically distributedU(0,1) random variables and offers a more probabilistic and computationally simpler alternative to the method of moments proof of Chao, Bai, and Liang (1993,Probability in the Engineering and Informational Sciences7: 227–235).