×

Central limit theorem for peaks of a random permutation in a fixed conjugacy class of \(S_n\). (English) Zbl 1487.60052

Fundamental results of important past mathematicians had applied the strategy of adopting the modified Curtiss’ theorem, and algebraic combinatorial computations had been used to calculate sampling probabilities through numerical simulations of expected joint distribution of random variables in inferential statistics. Different methods of calculation of limits and bounds for estimating functional operators were discovered by Pitman, David and Barton, Tanny, Fulman and many others during the observance of Stein’s discrepancy phenomena reflected among measure sets.
The two main results of this paper concern the convergence in distribution of random variables to the pointwise convergence of their moment generating functions on an open set where a partition of the sampling dimension \(n\) with \(n_i\) parts of size \(i\) relates the density of fixed points, providing the uniform estimate of the discrepancy between a continuous probability distribution and a discrete set of states selected from its domain which authors split in two regions, roughly speaking the small and large range points or regions. These results generalize to a broader class of sequences \((\mathcal{C}_n)\) such that it is a conjugacy-invariant subset of \(S_{n}\) and every element of \(\mathcal{C}_n\) has the same number of fixed points. Finally, various lemmata are proved incorporating the exponentially decaying terms into the deranged and repressed error term completing the proofs. Mean and variance of peaks in the symmetric group are computed to establish the asymptotic normality in \(S_{n}\).
Editorial supplement: The authors’ abstract reads, “The number of peaks of a random permutation is known to be asymptotically normal. We give a new proof of this and prove a central limit theorem for the distribution of peaks in a fixed conjugacy class of the symmetric group. Our technique is to apply analytic combinatorics to study a complicated but exact generating function for peaks in a given conjugacy class.”

MSC:

60F05 Central limit and other weak theorems
05A15 Exact enumeration problems, generating functions
05E05 Symmetric functions and generalizations
60C05 Combinatorial probability
05A05 Permutations, words, matrices
05A10 Factorials, binomial coefficients, combinatorial functions

References:

[1] Bayer, D.; Diaconis, P., Trailing the dovetail shuffle to its lair, Ann. Appl. Probab., 2, 294-313 (1992) · Zbl 0757.60003 · doi:10.1214/aoap/1177005705
[2] Billey, S., Burdzy, K. and Sagan, B., Permutations with given peak set, J. Integer Seq.16 (2013), Article 13.6.1. · Zbl 1295.05008
[3] David, F. and Barton, D., Combinatorial chance, Hafner Publishing Co., 1962.
[4] Diaconis, P., Group representations in probability and statistics (1988), Hayward, CA: Institute of Mathematical Statistics, Hayward, CA · Zbl 0695.60012
[5] Diaconis, P.; Fulman, J.; Holmes, S., Analysis of casino shelf shuffling machines, Annals Appl. Probab., 23, 1692-1720 (2013) · Zbl 1283.60013 · doi:10.1214/12-AAP884
[6] Diaconis, P. and Graham, R., Magical mathematics. The mathematical ideas that animate great magic tricks, Princeton University Press, 2012. · Zbl 1230.00009
[7] Diaconis, P.; McGrath, M.; Pitman, J., Riffle shuffles, cycles, and descents, Combinatorica, 15, 11-29 (1995) · Zbl 0828.05003 · doi:10.1007/BF01294457
[8] Fulman, J., Stein’s method and non-reversible Markov chains, in: Stein’s method: expository lectures and applications, 69-77, IMS Lecture Notes Monogr. Ser., 46, Inst. Math. Statist., 2004.
[9] Fulman, J., The distribution of descents in fixed conjugacy classes of the symmetric groups, J. Combin. Theory Ser. A, 84, 171-180 (1998) · Zbl 0917.05006 · doi:10.1006/jcta.1998.2893
[10] Fulman, J., Neumann, P. and Praeger, C., A generating function approach to the enumeration of matrices in classical groups over finite fields, Mem. Amer. Math. Soc.176 (2005), no. 830. · Zbl 1082.05097
[11] Gessel, I.; Reutenauer, C., Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A, 64, 189-215 (1993) · Zbl 0793.05004 · doi:10.1016/0097-3165(93)90095-P
[12] Graham, R.L., Knuth, D.E., Patashnik, O., Concrete mathematics: a foundation for computer science, 2nd ed. Addison-Wesley, Reading, Mass. (1994). · Zbl 0836.00001
[13] Harper, L., Stirling behavior is asymptotically normal, Ann. Math. Stat., 38, 410-414 (1966) · Zbl 0154.43703 · doi:10.1214/aoms/1177698956
[14] Kim, G., Distribution of descents in matchings, Annals Combin., 23, 73-87 (2019) · Zbl 1419.05027 · doi:10.1007/s00026-019-00414-1
[15] Kim, G.; Lee, S., Central limit theorems for descents in conjugacy classes of \(S_n\), J. Combin. Theory Ser. A, 169, 105123 (2020) · Zbl 1428.05019 · doi:10.1016/j.jcta.2019.105123
[16] Knuth, D., The art of computer programming, Volume 3. Sorting and searching, Addison-Wesley, 1973. · Zbl 0302.68010
[17] Nyman, K., The peak algebra of the symmetric group, J. Algebraic Combin., 17, 309-322 (2003) · Zbl 1021.06003 · doi:10.1023/A:1025000905826
[18] Petersen, K., Eulerian numbers, Birkhauser, 2015. · Zbl 1337.05001
[19] Petersen, K., Enriched \(P\)-partitions and peak algebras, Adv. Math., 209, 561-610 (2007) · Zbl 1111.05097 · doi:10.1016/j.aim.2006.05.016
[20] Pitman, J., Probabilistic bounds on the coefficients of polynomials with only real zeros, J. Combin. Theory Ser. A, 77, 279-303 (1997) · Zbl 0866.60016 · doi:10.1006/jcta.1997.2747
[21] Reiner, V., Signed permutation statistics and cycle type, Europ. J. Combin., 14, 569-579 (1993) · Zbl 0793.05006 · doi:10.1006/eujc.1993.1059
[22] Robbins, H., A Remark on Stirling’s Formula, The American Mathematical Monthly, 62, 1, 26-29 (1955) · Zbl 0068.05404
[23] Schocker, M., The peak algebra of the symmetric group revisited, Adv. Math., 192, 259-309 (2005) · Zbl 1132.20009 · doi:10.1016/j.aim.2004.04.007
[24] Stembridge, J., Enriched \(P\)-partitions, Trans. Amer. Math. Soc., 349, 763-788 (1997) · Zbl 0863.06005 · doi:10.1090/S0002-9947-97-01804-7
[25] Tanny, S., A probabilistic interpretation of Eulerian numbers, Duke Math. J., 40, 717-722 (1973) · Zbl 0284.05006 · doi:10.1215/S0012-7094-73-04065-9
[26] Vershynin, R., High-Dimensional Probability. Cambridge University Press, 2018. · Zbl 1430.60005
[27] Warren, D.; Seneta, E., Peaks and Eulerian numbers in a random sequence, J. Appl. Probab., 33, 101-114 (1996) · Zbl 0845.60035 · doi:10.2307/3215267
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.