A Coupling Proof of the Asymptotic Normality of the Permutation Oscillation
Author:
- 1 October 1995
- journal article
- research article
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 9 (4) , 615-621
Abstract
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).Keywords
This publication has 4 references indexed in Scilit:
- Asymptotic Normality for Oscillation of PermutationProbability in the Engineering and Informational Sciences, 1993
- Spearman's Footrule as a Measure of DisarrayJournal of the Royal Statistical Society Series B: Statistical Methodology, 1977
- Some Extensions of the Wald-Wolfowitz-Noether TheoremThe Annals of Mathematical Statistics, 1961
- A Combinatorial Central Limit TheoremThe Annals of Mathematical Statistics, 1951