Normal Approximations for Descents and Inversions of Permutations of Multisets |
| |
Authors: | Mark Conger D. Viswanath |
| |
Affiliation: | (1) Department of Mathematics, University of Michigan, 530 Church Street, Ann Arbor, MI 48109, USA |
| |
Abstract: | Normal approximations for descents and inversions of permutations of the set {1,2,…,n} are well known. We consider the number of inversions of a permutation π(1),π(2),…,π(n) of a multiset with n elements, which is the number of pairs (i,j) with 1≤i<j≤n and π(i)>π(j). The number of descents is the number of i in the range 1≤i<n such that π(i)>π(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→∞, provided that the permutation is equally likely to be any possible permutation of the multiset and no element occurs more than α n times in the multiset for a fixed α with 0<α<1. Both normal approximation theorems are proved using the size bias version of Stein’s method of auxiliary randomization and are accompanied by error bounds. This work was supported by a research fellowship from the Sloan Foundation. |
| |
Keywords: | Descents Inversions Multisets Stein’ s method |
本文献已被 SpringerLink 等数据库收录! |
|