The generalized weighted probability measure on the symmetric group and the asymptotic behavior of the cycles

Nikeghbali, Ashkan; Zeindler, Dirk

Annales de l'I.H.P. Probabilités et statistiques, Tome 49 (2013) no. 4, pp. 961-981.

Dans cet article nous étudions le comportement asymptotique du nombre de cycles ainsi que du nombre total de cycles pour certains types de permutations aléatoires issues de modèles physiques et qui généralisent la mesure d'Ewens. En utilisant une analyse des singularités des fonctions génératrices nous démontrons que sous certaines conditions le processus du nombre de cycles converge en loi vers un vecteur de variables de Poisson indépendantes et que le nombre total de cycles satisfait un théorème central limite. En fait les méthodes employées nous permettent d'avoir une estimation asymptotique précise de la fonction caractéristique des différents vecteurs aléatoires étudiés avec un contrôle sur les termes d'erreur. Ainsi nous somme en mesure de prouver une convergence plus fine pour le nombre total de cyles, à savoir une convergence mod-Poisson, de laquelle nous déduisons des résultats d'approximation Poissonienne et de grandes déviations précises.

The goal of this paper is to analyse the asymptotic behaviour of the cycle process and the total number of cycles of weighted and generalized weighted random permutations which are relevant models in physics and which extend the Ewens measure. We combine tools from combinatorics and complex analysis (e.g. singularity analysis of generating functions) to prove that under some analytic conditions (on relevant generating functions) the cycle process converges to a vector of independent Poisson variables and to establish a central limit theorem for the total number of cycles. Our methods allow us to obtain an asymptotic estimate of the characteristic functions of the different random vectors of interest together with an error estimate, thus having a control on the speed of convergence. In fact we are able to prove a finer convergence for the total number of cycles, namely mod-Poisson convergence. From there we apply previous results on mod-Poisson convergence to obtain Poisson approximation for the total number of cycles as well as large deviations estimates.

Classification : 60K35, 05E99, 30B10
Mots clés : symmetric group, weighted probability measure, cycle counts, total number cycles, mod-Poisson convergence, Poisson approximation

[1] R. Arratia, A. Barbour and S. Tavaré. Logarithmic Combinatorial Structures: A Probabilistic Approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zürich, 2003. | MR

[2] A. Barbour, E. Kowalski and A. Nikeghbali. Mod-discrete expansions. Preprint, 2009.

[3] A. Barbour, A. Nikeghbali and M. Wahl. Mod-∗ convergence and large deviations. In preparation, 2011.

[4] V. Betz and D. Ueltschi. Spatial random permutations and infinite cycles. Comm. Math. Phys. 285 (2009) 465-501. | MR

[5] V. Betz and D. Ueltschi. Critical temperature of dilute Bose gases. Phys. Rev. A 81 (2010) 023611.

[6] V. Betz and D. Ueltschi. Spatial permutations with small cycle weights. Probab. Theory Related Fields 149 (2011) 191-222. | MR

[7] V. Betz and D. Ueltschi. Spatial random permutations and Poisson-Dirichlet law of cycle lengths. Preprint, 2011. | MR

[8] V. Betz, D. Ueltschi and Y. Velenik. Random permutations with cycle weights. Ann. Appl. Probab. 21 (1) (2011) 312-331. | MR

[9] D. Bump. Lie Groups. Graduate Texts in Mathematics 225. Springer, New York, 2004. | MR

[10] N. Ercolani and D. Ueltschi. Cycle structure of random permutations with cycle weights. Preprint, 2011.

[11] W. J. Ewens. The sampling theory of selectively neutral alleles. Theoret. Population Biology 3 (1972) 87-112. Erratum: Theoret. Population Biology 3 (1972) 240; Erratum: Theoret. Population Biology 3 (1972) 376. | MR

[12] P. Flajolet. Singularity analysis and asymptotics of Bernoulli sums. Theoret. Comput. Sci. 215 (1-2) (1999) 371-381. | MR

[13] P. Flajolet, S. Gerhold and B. Salvy. Lindelöf representations and (non-)holonomic sequences. Electron. J. Combin. 17 (1) (2010) Research Paper 3. | MR

[14] P. Flajolet, X. Gourdon and P. Dumas. Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 (1-2) (1995) 3-58. | MR

[15] P. Flajolet and A. M. Odlyzko. Singularity analysis of generating functions. SIAM J. Discrete Math. 3 (1990) 216-240. | MR

[16] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge Univ. Press, New York, 2009. | MR

[17] W. B. Ford. Studies on Divergent Series and Summability & The Asymptotic Developments of Functions Defined by Maclaurin Series. Chelsea, New York, 1960.

[18] V. Goncharov. Some facts from combinatorics. Izv. Akad. Nauk SSRS Ser. Mat. 8 (1944) 3-48.

[19] H. Hwang. Théorèmes limites pour les structures combinatories et les fonctions arithmétiques. Ph.D. thesis, École Polytechnique, 1994.

[20] H. Hwang. Asymptotic expansions for the stirling numbers of the first kind. J. Combin. Theory Ser. A 71 (1995) 343-351. | MR

[21] H. Hwang. Asymptotics of Poisson approximation to random discrete distributions: An analytic approach. Adv. in Appl. Probab. 31 (2) (1999) 448-491. | MR

[22] J. Jacod, E. Kowalski and A. Nikeghbali. Mod-Gaussian convergence: New limit theorems in probability and number theory. Forum Math. 23 (2011) 835-873. | MR

[23] J. F. C. Kingman. The population structure associated with the ewens sampling formula. Theoret. Population Biology 11 (1977) 274-283. | MR

[24] A. Kowalski and E. Nikeghbali. Mod-Poisson convergence in probability and number theory. Int. Math. Res. Not. 18 (2010) 3549-3587. | MR

[25] I. G. Macdonald. Symmetric Functions and Hall Polynomials, 2nd edition. Oxford Mathematical Monographs. The Clarendon Press Oxford Univ. Press, New York, 1995. | MR

[26] L. Shepp and S. P. Lloyd. Ordered cycle lengths in a random permutation. Trans. Amer. Math. Soc. 121 (1966) 340-357. | MR

[27] A. M. Vershik and A. A. Shmidt. Limit measures arising in the asymptotic theory of symmetric groups. I. Theory Probab. Appl. 22 (1977) 70-85.