×
Féray, Valentin

Central limit theorems for patterns in multiset permutations and set partitions. (English) Zbl 1434.60040

Ann. Appl. Probab. 30, No. 1, 287-323 (2020).
Summary: We use the recently developed method of weighted dependency graphs to prove central limit theorems for the number of occurrences of any fixed pattern in multiset permutations and in set partitions. This generalizes results for patterns of size 2 in both settings, obtained by E. R. Canfield et al. [Adv. Appl. Math. 46, No. 1–4, 109–124 (2011; Zbl 1227.05009)] and B. Chern et al. [Adv. Appl. Math. 70, 92–105 (2015; Zbl 1327.60030)], respectively.

Cited in 3 Documents

MSC:

60C05 Combinatorial probability
60F05 Central limit and other weak theorems
05A05 Permutations, words, matrices
05A18 Partitions of sets

Keywords:

combinatorial probability; central limit theorem; dependency graphs; patterns; multiset permutations; set partitions

Citations:

Zbl 1227.05009; Zbl 1327.60030

Software:

MahonianStat
PDF BibTeX XML Cite
\textit{V. Féray}, Ann. Appl. Probab. 30, No. 1, 287--323 (2020; Zbl 1434.60040)
Full Text: DOI arXiv Euclid
  • logo of hbz
  • logo of WorldCat

References:

[1] Albert, M. H., Aldred, R. E. L., Atkinson, M. D., Handley, C. and Holton, D. (2001). Permutations of a multiset avoiding permutations of length 3. European J. Combin. 22 1021-1031. · Zbl 0988.05005
[2] Bóna, M. (2010). On three different notions of monotone subsequences. In Permutation Patterns. London Mathematical Society Lecture Note Series 376 89-114. Cambridge Univ. Press, Cambridge. · Zbl 1217.05007
[3] Brillinger, D. (1969). The calculation of cumulants via conditioning. Ann. Inst. Statist. Math. 21 215-218. · Zbl 0181.46103
[4] Canfield, E. R. (1995). Engel’s inequality for Bell numbers. J. Combin. Theory Ser. A 72 184-187. · Zbl 0830.11010
[5] Canfield, E. R., Janson, S. and Zeilberger, D. (2011). The Mahonian probability distribution on words is asymptotically normal. Adv. in Appl. Math. 46 109-124. · Zbl 1227.05009
[6] Chatterjee, S. (2008). A new method of normal approximation. Ann. Probab. 36 1584-1610. · Zbl 1159.62009
[7] Chern, B., Diaconis, P., Kane, D. M. and Rhoades, R. C. (2014). Closed expressions for averages of set partition statistics. Res. Math. Sci. 1 Art. 2, 32. · Zbl 1339.15019
[8] Chern, B., Diaconis, P., Kane, D. M. and Rhoades, R. C. (2015). Central limit theorems for some set partition statistics. Adv. in Appl. Math. 70 92-105. · Zbl 1327.60030
[9] Crane, H., DeSalvo, S. and Elizalde, S. (2018). The probability of avoiding consecutive patterns in the Mallows distribution. Random Structures Algorithms 53 417-447. · Zbl 1401.05010
[10] Féray, V. (2013). Asymptotic behavior of some statistics in Ewens random permutations. Electron. J. Probab. 18 no. 76, 32. · Zbl 1314.05016
[11] Féray, V. (2018). Weighted dependency graphs. Electron. J. Probab. 23 Paper No. 93, 65. · Zbl 1414.60014
[12] Féray, V., Méliot, P.-L. and Nikeghbali, A. (2016). Mod-\( \varphi\) Convergence: Normality Zones and Precise Deviations. SpringerBriefs in Probability and Mathematical Statistics. Springer, Cham. · Zbl 1387.60003
[13] Flajolet, P., Szpankowski, W. and Vallée, B. (2006). Hidden word statistics. J. ACM 53 147-183. · Zbl 1316.68111
[14] Fulman, J. (2004). Stein’s method and non-reversible Markov chains. In Stein’s Method: Expository Lectures and Applications. Institute of Mathematical Statistics Lecture Notes—Monograph Series 46 69-77. IMS, Beachwood, OH.
[15] Goldstein, L. (2005). Berry-Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing. J. Appl. Probab. 42 661-683. · Zbl 1087.60021
[16] Harper, L. H. (1967). Stirling behavior is asymptotically normal. Ann. Math. Stat. 38 410-414. · Zbl 0154.43703
[17] Hoeffding, W. (1948). A class of statistics with asymptotically normal distribution. Ann. Math. Stat. 19 293-325. · Zbl 0032.04101
[18] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 13-30. · Zbl 0127.10602
[19] Hofer, L. (2017). A central limit theorem for vincular permutation patterns. Discrete Math. Theor. Comput. Sci. 19 Paper No. 9, 26. · Zbl 1401.05013
[20] Janson, S. (1988). Normal convergence by higher semi-invariants with applications to sums of dependent random variables and random graphs. Ann. Probab. 16 305-312. · Zbl 0639.60029
[21] Janson, S. (1994). Orthogonal decompositions and functional limit theorems for random graph statistics. Mem. Amer. Math. Soc. 111 vi+78. · Zbl 0810.05001
[22] Janson, S. (1997). Gaussian Hilbert Spaces. Cambridge Tracts in Mathematics 129. Cambridge Univ. Press, Cambridge.
[23] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley Interscience, New York.
[24] Janson, S., Nakamura, B. and Zeilberger, D. (2015). On the asymptotic statistics of the number of occurrences of multiple permutation patterns. J. Comb. 6 117-143. · Zbl 1312.05011
[25] Leonov, V. P. and Sirjaev, A. N. (1959). On a method of calculation of semi-invariants. Theory Probab. Appl. 4 319-329. · Zbl 0087.33701
[26] Mikhaĭlov, V. G. (1991). On a theorem of Janson. Theory Probab. Appl. 36 173-176. · Zbl 0751.60021
[27] Mitzenmacher, M. and Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univ. Press, Cambridge. · Zbl 1092.60001
[28] Rota, G.-C. (1964). The number of partitions of a set. Amer. Math. Monthly 71 498-504. · Zbl 0121.01803
[29] Ruciński, A. (1988). When are small subgraphs of a random graph normally distributed? Probab. Theory Related Fields 78 1-10. · Zbl 0627.60045
[30] Schutzenberger, M.-P. (1947). Sur certains paramètres caractéristiques des systèmes d’événements compatibles et dépendants et leur application au calcul des cumulants de la répétition. C. R. Math. Acad. Sci. Paris 225 277-278. · Zbl 0029.36901
[31] Stam, A. J. (1983). Generation of a random partition of a finite set by an urn model. J. Combin. Theory Ser. A 35 231-240. · Zbl 0513.05007
[32] Thiel, M. (2016). The inversion number and the major index are asymptotically jointly normally distributed on words. Combin. Probab. Comput. 25 470-483. · Zbl 1372.05005
[33] Ursell, H. D. (1927). The evaluation of Gibbs’ phase-integral for imperfect gases. Math. Proc. Cambridge Philos. Soc. 23 685-697. · JFM 53.0868.01
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.