On the order of random permutation with cycle weights

A. L. Yakymiv

Teoriâ veroâtnostej i ee primeneniâ, Tome 63 (2018) no. 2, pp. 260-283

Résumé

Let $\operatorname{Ord}(\tau)$ be the order of an element $\tau$ in the group $S_n$ of permutations of an $n$-element set $X$. The present paper is concerned with the so-called general parametric model of a random permutation; according to this model an arbitrary fixed permutation $\tau$ from $S_n$ is observed with the probability $\theta_1^{u_1}\dotsb\theta_n^{u_n}/H(n)$, where $u_i$ is the number of cycles of length $i$ of the permutation $\tau$, $\{\theta_i,\ i\in \mathbf{N}\}$ are some nonnegative parameters (the weights of cycles of length $i$ of the permutation $\tau$), and $H(n)$ is the corresponding normalizing factor. We assume that an arbitrary permutation $\tau_n$ has such a distribution. The function $p(n)=H(n)/n!$ is assumed to be $\mathrm{RO}$-varying at infinity with the lower index exceeding $-1$ (in particular, it can vary regularly), and the sequence $\{\theta_i,\ i\in \mathbf N\}$ is bounded. Under these assumptions it is shown that the random variable $\ln\operatorname{Ord}(\tau_n)$ is asymptotically normal with mean $\sum_{k=1}^n\theta_k\ln (k)/k$ and variance $\sum_{k=1}^n\theta_k\ln^2(k)/k$. In particular, this scheme subsumes the class of random $A$-permutations (i.e., when $\theta_i=\chi\{i\in A\}$), where $A$ is an arbitrary fixed subset of the positive integers. This scheme also includes the Ewens model of random permutation, where $\theta_i\equiv\theta>0$ for any $i\in\mathbf N$. The limit theorem we prove here extends some previous results for these schemes. In particular, with $\theta_i\equiv1$ for any $i\in\mathbf N$, the result just mentioned implies the well-known Erdős–Turán limit theorem.

Détail

Keywords: random permutation with cycle weights, random $A$-permutation, random permutation in the Ewens mode, order of random permutation, regularly varying function, $\mathrm{RO}$-varying function.

Bibliographie

[1] R. Arratia, A. D. Barbour, S. Tavaré, Logarithmic combinatorial structures: a probabilistic approach, EMS Monogr. Math., Eur. Math. Soc., Zürich, 2003, xii+363 pp. | DOI | MR | Zbl

[2] R. Arratia, S. Tavaré, “Limit theorems for combinatorial structures via discrete process approximations”, Random Structures Algorithms, 3:3 (1992), 321–345 | DOI | MR | Zbl

[3] A. D. Barbour, S. Tavaré, “A rate for the Erdős–Turán law”, Combin. Probab. Comput., 3:2 (1994), 167–176 | DOI | MR | Zbl

[4] E. A. Bender, “Asymptotic methods in enumeration”, SIAM Rev., 16:4 (1974), 485–515 | DOI | MR | Zbl

[5] V. Betz, D. Ueltschi, Y. Velenik, “Random permutations with cycle weights”, Ann. Appl. Probab., 21:1 (2011), 312–331 | DOI | MR | Zbl

[6] N. H. Bingham, Ch. M. Goldie, J. L. Teugels, Regular variation, Encyclopedia Math. Appl., 27, Cambridge Univ. Press, Cambridge, 1987, xx+491 pp. | DOI | MR | Zbl

[7] K. Bogdanas, E. Manstavic̆ius, “Stochastic processes on weakly logarithmic assemblies”, Analytic and probabilistic methods in number theory, TEV, Vilnius, 2012, 69–80 | MR | Zbl

[8] N. M. Ercolani, D. Ueltschi, “Cycle structure of random permutations with cycle weights”, Random Structures Algorithms, 44:1 (2014), 109–133 | DOI | MR | Zbl

[9] P. Erdős, P. Turán, “On some problems of a statistical group-theory. I”, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 4:2 (1965), 175–186 ; II, Acta Math. Acad. Sci. Hungar., 18:1-2 (1967), 151–163 ; III, 18:3-4 (1967), 309–320 ; IV, 19:3-4 (1968), 413–435 | DOI | MR | Zbl | DOI | MR | Zbl | DOI | MR | Zbl | DOI | MR | Zbl

[10] W. J. Ewens, “The sampling theory of selectively neutral alleles”, Theoret. Population Biology, 3 (1972), 87–112 | DOI | MR | Zbl

[11] B. Harris, “The asymptotic distribution of the order of elements in symmetric semigroups”, J. Combinatorial Theory Ser. A, 15 (1973), 66–74 | DOI | MR | Zbl

[12] G. I. Ivchenko, Yu. I. Medvedev, “Goncharov's method and its development in the analysis of different models of random permutations”, Theory Probab. Appl., 47:3 (2003), 518–526 | DOI | DOI | MR | Zbl

[13] G. I. Ivchenko, Yu. I. Medvedev, “Neravnoveroyatnye mery na mnozhestvakh razlozhimykh kombinatornykh ob'ektov”, Obozrenie prikladnoi i promyshlennoi matematiki, 10:2 (2003), 348–349

[14] G. I. Ivchenko, Yu. I. Medvedev, V. N. Sachkov, “Nekotorye problemy veroyatnostnoi kombinatoriki”, Matematika i bezopasnost informatsionnykh tekhnologii, Materialy konferentsii v MGU 23.10.2003, MTsNMO, M., 2004, 45–52

[15] G. I. Ivchenko, Yu. I. Medvedev, “Statistika parametricheskoi modeli sluchainykh podstanovok”, Tr. po diskr. matem., 8, Fizmatlit, M., 2004, 116–127

[16] G. I. Ivchenko, Yu. I. Medvedev, “Random combinatorial objects”, Dokl. Math., 69:3 (2004), 344–347 | MR | Zbl

[17] G. I. Ivchenko, Yu. I. Medvedev, “Random permutations: the general parametric model”, Discrete Math. Appl., 16:5 (2006), 471–478 | DOI | DOI | MR | Zbl

[18] G. I. Ivchenko, Yu. I. Medvedev, “Sluchainye kombinatornye ob'ekty v obschei parametricheskoi modeli”, Tr. po diskr. matem., 10, Fizmatlit, M., 2007, 73–86

[19] G. I. Ivchenko, M. V. Soboleva, “Some nonequiprobable models of random permutations”, Discrete Math. Appl., 21:4 (2011), 397–406 | DOI | DOI | MR | Zbl

[20] V. F. Kolchin, Random mappings, Transl. Ser. Math. Engrg., Optimization Software, Inc., Publications Division, New York, 1986, xiv+207 pp. | MR | MR | Zbl | Zbl

[21] V. F. Kolchin, Random graphs, Encyclopedia Math. Appl., 53, Cambridge Univ. Press, Cambridge, 1999, xii+252 pp. | MR | MR | Zbl | Zbl

[22] J. M. DeLaurentis, B. G. Pittel, “Random permutations and Brownian motion”, Pacific J. Math., 119:2 (1985), 287–301 | DOI | MR | Zbl

[23] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, 2 Bände, B. G. Teubner, Leipzig–Berlin, 1909, x+ix+961 pp. | MR | Zbl

[24] E. Manstavic̆ius, “Total variation approximation for random assemblies and a functional limit theorem”, Monatsh. Math., 161:3 (2010), 313–334 | DOI | MR | Zbl

[25] E. Manstavic̆ius, “A limit theorem for additive functions defined on the symmetric group”, Lith. Math. J., 51:2 (2011), 220–232 | DOI | MR | Zbl

[26] E. Manstavic̆ius, “On total variation approximations for random assemblies”, 23rd international meeting on probabilistic, combinatorial, and asymptotic methods for the analysis of algorithms (AofA'12) (Montreal, Canada, June 18–22, 2012), Discrete Math. Theor. Comput. Sci. Proc., AQ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012, 97–108 | MR | Zbl

[27] A. I. Pavlov, “On some classes of permutations with number-theoretic restrictions on the lengths of cycles”, Math. USSR-Sb., 57:1 (1987), 263–275 | DOI | MR | Zbl

[28] A. I. Pavlov, “On the number of substitutions with cycle lengths from a given set”, Discrete Math. Appl., 2:4 (1992), 445–459 | DOI | MR | Zbl

[29] V. N. Sachkov, “Mappings of a finite set with limitations on contours and height”, Theory Probab. Appl., 17:4 (1972), 640–656 | DOI | MR | Zbl

[30] V. N. Sachkov, “Random mappings with bounded height”, Theory Probab. Appl., 18:1 (1973), 120–130 | DOI | MR | Zbl

[31] V. N. Sachkov, Combinatorial methods in discrete mathematics, Encyclopedia Math. Appl., 55, Cambridge Univ. Press, Cambridge, 1996, xiv+306 pp. | DOI | MR | Zbl

[32] V. N. Sachkov, Probabilistic methods in combinatorial analysis, Encyclopedia Math. Appl., 56, Cambridge Univ. Press, Cambridge, 1997, x+246 pp. | DOI | MR | MR | Zbl | Zbl

[33] V. N. Sachkov, Vvedenie v kombinatornye metody diskretnoi matematiki, 2-e izd., ispr. i dop., MTsNMO, M., 2004, 424 pp. | MR | Zbl

[34] E. Seneta, Regularly varying functions, Lecture Notes in Math., 508, Springer-Verlag, Berlin–New York, 1976, v+112 pp. | DOI | MR | MR | Zbl | Zbl

[35] M. V. Soboleva, “The asymptotic normality of the number of congruent cycles in a random permutation”, Discrete Math. Appl., 22:1 (2012), 91–100 | DOI | DOI | MR | Zbl

[36] J. Storm, D. Zeindler, “Total variation distance and the Erdős–Turán law for random permutations with polynomially growing cycle weights”, Ann. Inst. Henri Poincaré Probab. Stat., 52:4 (2016), 1614–1640 | DOI | MR | Zbl

[37] J. Storm, D. Zeindler, “The order of large random permutations with cycle weights”, Electron. J. Probab., 20 (2015), 126, 34 pp. | DOI | MR | Zbl

[38] A. N. Timashev, Obobschennaya skhema razmescheniya v zadachakh veroyatnostnoi kombinatoriki, Izd. dom «Akademiya», M., 2011, 268 pp.

[39] A. N. Timashev, Bolshie ukloneniya v veroyatnostnoi kombinatorike, Izd. dom «Akademiya», M., 2011, 248 pp.

[40] A. N. Timashev, Asimptoticheskie razlozheniya v veroyatnostnoi kombinatorike, TVP, M., 2011, 312 pp.

[41] A. N. Timashev, Additivnye zadachi s ogranicheniyami na znacheniya slagaemykh, Akademiya, M., 2015, 184 pp.

[42] A. N. Timashev, Raspredeleniya tipa stepennogo ryada i obobschennaya skhema razmescheniya, Akademiya, M., 2016

[43] A. N. Timashev, “Random permutations with prime lengths of cycles”, Theory Probab. Appl., 61:2 (2017), 309–320 | DOI | DOI | MR | Zbl

[44] A. L. Yakymiv, “On the distribution of the $m$th maximal cycle lengths of random $A$-permutations”, Discrete Math. Appl., 15:5 (2005), 527–546 | DOI | DOI | MR | Zbl

[45] A. L. Yakimiv, Probabilistic applications of Tauberian theorems, Mod. Probab. Stat., VSP, Leiden, 2005, viii+225 pp. | DOI | MR | Zbl | Zbl

[46] A. L. Yakymiv, “A limit theorem for the logarithm of the order of a random $A$-permutation”, Discrete Math. Appl., 20:3 (2010), 247–275 | DOI | DOI | MR | Zbl

[47] A. L. Yakymiv, “On a number of components in a random $A$-mapping”, Theory Probab. Appl., 59:1 (2015), 114–127 | DOI | DOI | MR | Zbl

[48] A. L. Yakymiv, “Limit theorems for the logarithm of the order of a random $A$-mapping”, Discrete Math. Appl., 27:5 (2017), 325–338 | DOI | DOI

[49] A. L. Yakymiv, “Tauberian theorem for generating functions of multiple series”, Theory Probab. Appl., 60:2 (2016), 343–347 | DOI | DOI | MR | Zbl

[50] A. L. Yakymiv, “A Tauberian theorem for multiple power series”, Sb. Math., 207:2 (2016), 286–313 | DOI | DOI | MR | Zbl

[51] A. L. Yakymiv, “O raspredelenii tipa kratnogo stepennogo ryada, pravilno menyayuschegosya v granichnoi tochke”, Diskret. matem., 30 (2018) (to appear)

[52] A. L. Yakymiv, “Distribution of the order in some classes of random mappings”, XVII-th international summer conference on probability and statistics (ISCPS-2016). Conference proceedings and abstracts (Pomorie, Bulgaria, 25 June–1 July 2016), Inst. Math. Inform. BAS, Sofia, 2016, 42–50 http://www.math.bas.bg/~statlab/ISCPS2016/