Normal approximations for descents and inversions of permutations of multisets

DOI10.1007/S10959-007-0070-5MaRDI QIDQ2641429zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 20 August 2007

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0508242

zbMATH Keywords

descentsinversionsmultisetsStein's method

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05)

Abstract: Normal approximations for descents and inversions of permutations of the set $1,2,\mathrm{...},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),\mathrm{...},pi(n)$ of a multiset with $n$ elements, which is the number of pairs $(i,j)$ with $1leqi<jleqn$ and $pi(i)>pi(j)$. The number of descents is the number of $i$ in the range $1leqi<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 $noinfty$, provided that the permutation is equally likely to be any possible permutation of the multiset and no element occurs more than $alphan$ 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.

Recommendations

• Bounds on normal approximations for the number of descents and inversions
• Exponential bounds for normal approximation of the number of descents and inversions
• Generalized descents and normality
• A central limit theorem for descents of a Mallows permutation and its inverse
• The numbers of ascending segments in a random permutation and in the inverse to it are asymptotically independent

Cites work

• Asymptotic Distribution of Runs Up and Down
• Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing
• scientific article; zbMATH DE number 6007664 (Why is no real title available?)
• scientific article; zbMATH DE number 4155658 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 50805 (Why is no real title available?)
• scientific article; zbMATH DE number 3559582 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 3438144 (Why is no real title available?)
• Multivariate normal approximations by Stein's method and size bias couplings
• On coupling constructions and rates in the CLT for dependent summands with applications to the antivoter model and weighted U-statistics
• Riffle shuffles of decks with repeated cards
• Some Aspects of the Random Sequence
• The Covariance Matrix of Runs Up and Down

Cited in

(20)

• Generalized descents and normality
• Signatures of strings
• A central limit theorem for descents of a Mallows permutation and its inverse
• An asymptotic distribution theory for Eulerian recurrences with applications
• On meteors, earthworms and wimps
• Hopf algebras and Markov chains: two examples and a theory
• Exponential bounds for normal approximation of the number of descents and inversions
• On an alternative sequence comparison statistic of Steele
• Bounds on normal approximations for the number of descents and inversions
• scientific article; zbMATH DE number 3933077 (Why is no real title available?)
• scientific article; zbMATH DE number 3950540 (Why is no real title available?)
• Descent-inversion statistics in riffle shuffles
• The Mahonian probability distribution on words is asymptotically normal
• A rule of thumb for riffle shuffling
• An equipartition property for the distribution of multiset permutation inversions
• Extreme values of permutation statistics
• Discretized normal approximation for the number of descents
• A central limit theorem on two-sided descents of Mallows distributed elements of finite Coxeter groups
• Joint extremes of inversions and descents of random permutations
• Minimum maximal matchings in permutahedra

This page was built for publication: Normal approximations for descents and inversions of permutations of multisets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641429)