Asymptotic behavior of some statistics in Ewens random permutations

Valentin Féray (CNRS & Université de Bordeaux)

Abstract


The purpose of this article is to present a general method to find limiting laws for some renormalized statistics on random permutations. The model of random permutations considered here is Ewens sampling model, which generalizes uniform random permutations. Under this model, we describe the asymptotic behavior of some statistics, including the number of occurrences of any dashed pattern. Our approach is based on the method of moments and relies on the following intuition: two events involving the images of different integers are almost independent.


Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-32

Publication Date: August 13, 2013

DOI: 10.1214/EJP.v18-2496

References

  • Arratia, Richard; Barbour, A. D.; Tavaré, Simon. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, 2003. xii+363 pp. ISBN: 3-03719-000-0 MR2032426
  • Aval, Jean-Christophe; Boussicault, Adrien; Nadeau, Philippe. Tree-like tableaux. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 63--74, Discrete Math. Theor. Comput. Sci. Proc., AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011. MR2820698
  • Babson, Eric; Steingrímsson, Einar. Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin. 44 (2000), Art. B44b, 18 pp. (electronic). MR1758852
  • Barbour, A. D.; Holst, Lars; Janson, Svante. Poisson approximation. Oxford Studies in Probability, 2. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992. x+277 pp. ISBN: 0-19-852235-5 MR1163825
  • Barbour, A. D.; Janson, S. A functional combinatorial central limit theorem. Electron. J. Probab. 14 (2009), no. 81, 2352--2370. MR2556014
  • Billingsley, Patrick. Probability and measure. Third edition. Wiley Series in Probability and Mathematical Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1995. xiv+593 pp. ISBN: 0-471-00710-2 MR1324786
  • Billingsley, Patrick. Convergence of probability measures. Second edition. Wiley Series in Probability and Statistics: Probability and Statistics. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1999. x+277 pp. ISBN: 0-471-19745-9 MR1700749
  • Bóna, Miklós. Generalized descents and normality. Electron. J. Combin. 15 (2008), no. 1, Note 21, 8 pp. MR2426166
  • Bóna, Miklós. On three different notions of monotone subsequences. Permutation patterns, 89--114, London Math. Soc. Lecture Note Ser., 376, Cambridge Univ. Press, Cambridge, 2010. MR2732825
  • Bousquet-Mélou, Mireille; Claesson, Anders; Dukes, Mark; Kitaev, Sergey. $(2+2)$-free posets, ascent sequences and pattern avoiding permutations. J. Combin. Theory Ser. A 117 (2010), no. 7, 884--909. MR2652101
  • Bouvel, Mathilde; Chauve, Cedric; Mishna, Marni; Rossin, Dominique. Average-case analysis of perfect sorting by reversals. Discrete Math. Algorithms Appl. 3 (2011), no. 3, 369--392. MR2855213
  • Corteel, Sylvie; Nadeau, Philippe. Bijections for permutation tableaux. European J. Combin. 30 (2009), no. 1, 295--310. MR2460235
  • Corteel, Sylvie; Williams, Lauren K. Tableaux combinatorics for the asymmetric exclusion process. Adv. in Appl. Math. 39 (2007), no. 3, 293--310. MR2352041
  • Derrida, Bernard. Matrix ansatz large deviations of the density in exclusion processes. International Congress of Mathematicians. Vol. III, 367--382, Eur. Math. Soc., Zürich, 2006. MR2275686
  • Derrida, B.; Lebowitz, J. L.; Speer, E. R. Entropy of open lattice systems. J. Stat. Phys. 126 (2007), no. 4-5, 1083--1108. MR2311899
  • Ewens, W. J. The sampling theory of selectively neutral alleles. Theoret. Population Biology 3 (1972), 87--112; erratum, ibid. 3 (1972), 240; erratum, ibid. 3 (1972), 376. MR0325177
  • V. Goncharov. Some facts from combinatorics. Izvestia Akad. Nauk. SSSR, Ser. Mat, 8:3--48, 1944.
  • Hitczenko, Paweł; Janson, Svante. Asymptotic normality of statistics on permutation tableaux. Algorithmic probability and combinatorics, 83--104, Contemp. Math., 520, Amer. Math. Soc., Providence, RI, 2010. MR2681856
  • Hoeffding, Wassily. A combinatorial central limit theorem. Ann. Math. Statistics 22, (1951). 558--566. MR0044058
  • Janson, Svante; Łuczak, Tomasz; Rucinski, Andrzej. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. xii+333 pp. ISBN: 0-471-17541-2 MR1782847
  • Kaplansky, Irving. The asymptotic distribution of runs of consecutive elements. Ann. Math. Statistics 16, (1945). 200--203. MR0013847
  • V. Kolchin. A problem of the allocation of particles in cells and cycles of random permutations. Theory of Probability and its Applications, 16:74--90, 1971.
  • Leonov, V. P.; Sirjaev, A. N. On a method of semi-invariants. Theor. Probability Appl. 4 1959 319--329. MR0123345
  • Lothaire, M. Combinatorics on words. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon. With a foreword by Roger Lyndon. Edited and with a preface by Perrin. Encyclopedia of Mathematics and its Applications, 17. Addison-Wesley Publishing Co., Reading, Mass., 1983. xix+238 pp. ISBN: 0-201-13516-7 MR0675953
  • Marckert, Jean-François. One more approach to the convergence of the empirical process to the Brownian bridge. Electron. J. Stat. 2 (2008), 118--126. MR2386089
  • A. Postnikov. Total positivity, Grassmannians, and networks. arXiv preprint math/0609764v1, 2006.
  • Rota, G.-C.; Taylor, B. D. The classical umbral calculus. SIAM J. Math. Anal. 25 (1994), no. 2, 694--711. MR1266584
  • Śniady, Piotr. Gaussian fluctuations of characters of symmetric groups and of Young diagrams. Probab. Theory Related Fields 136 (2006), no. 2, 263--297. MR2240789
  • Steingrímsson, Einar; Williams, Lauren K. Permutation tableaux and permutation patterns. J. Combin. Theory Ser. A 114 (2007), no. 2, 211--234. MR2293088
  • Watterson, G. A. The sampling theory of selectively neutral alleles. Advances in Appl. Probability 6 (1974), 463--488. MR0351504
  • Williams, Lauren K. Enumeration of totally positive Grassmann cells. Adv. Math. 190 (2005), no. 2, 319--342. MR2102660
  • Wolfowitz, J. Note on runs of consecutive elements. Ann. Math. Statistics 15, (1944). 97--98. MR0010341
  • W. Xu, B. Alain, and D. Sankoff. Poisson adjacency distributions in genome comparison: multichromosomal, circular, signed and unsigned cases. Bioinformatics, 24(16):i146, 2008.
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.