Normal approximations for descents and inversions of permutations of multisets

Abstract

Normal approximations for descents and inversions of permutations of the set $\{1,2,...,n\}$ are well known. A number of sequences that occur in practice, such as the human genome and other genomes, contain many repeated elements. Motivated by such examples, we consider the number of inversions of a permutation $\pi (1),\pi (2),...,\pi (n)$ of a multiset with $n$ elements, which is the number of pairs $(i,j)$ with $1\le i<j\le n$ and $\pi (i)>\pi (j)$. The number of descents is the number of $i$ in the range $1\le i<n$ such that $\pi (i)>\pi (i+1)$. We prove that, appropriately normalized, the distribution of both inversions and descents of a random permutation of the multiset approaches the normal distribution as $n\to \infty$, provided that the permutation is equally likely to be any possible permutation of the multiset and no element occurs more than $\alpha n$ times in the multiset for a fixed $\alpha$ with $0<\alpha <1$. Both normal approximation theorems are proved using the size biased version of Stein's method of auxiliary randomization and are accompanied by error bounds.

References in corpus (1)

• Berry Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing