Limit theorems for the logarithm of the order of a random $A$-mapping

A. L. Yakymiv

Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 136-155.

Résumé

Let $\mathfrak S_n$ be a semigroup of mappings of a set $X$ with $n$ elements into itself, $A$ be some fixed subset of the set $N$ of natural numbers, and $V_n(A)$ be a set of mappings from $\mathfrak S_n$, with lengths of cycles belonging to $A$. The mappings from $V_n(A)$ are called $A$-mappings. We suppose that the set $A$ has an asymptotic density $\varrho>0$, and that $|k\colon k\leq n,\ k\in A,\ m-k\in A|/n\to\varrho^2$ as $n\to\infty$ uniformly over $m\in[n,Cn]$ for each constant $C>1$. A number $M(\alpha)$ of different elements in a set $\{\alpha,\ \alpha^2,\ \alpha^3,\dots\}$ is called an order of mapping $\alpha\in\mathfrak S_n$. Consider a random mapping $\sigma=\sigma_n(A)$ having uniform distribution on $V_n(A)$. In the present paper it is shown that random variable $\ln M(\sigma_n(A))$ is asymptotically normal with mean $l(n)=\sum_{k\in A(\sqrt{n})}\ln(k)/{k}$ and variance $\varrho\ln^3(n)/24$, where $A(t)=\{k\colon k\in A,\ k\leq t\},\ t>0$. For the case $A=N$ this result was proved by B. Harris in 1973.

Détail

Keywords: random $A$-mappings, order of $A$-mapping, cyclic points, contours, trees, height of random\linebreak$A$-mapping, random $A$-permutations.

Bibliographie

[1] Arratia R., Barbour A. D., Tavaré S., “Logarithmic combinatorial structures: a probabilistic approach”, Comb. Probab. Comput., 13:6 (2004), 916–917 | DOI | MR

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

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

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

[5] Bingham N. H., Goldie C. M., Teugels J. L., Regular Variation, Cambridge Univ. Press, Cambridge, 1989, 494 pp. | MR | Zbl

[6] Bogdanas K., Manstavicius E., “Stochastic processes on weakly logarithmic assemblies”, Analytic and Probabilistic Methods in Number Theory, Kubilius Memorial Volume, eds. A. Laurincikas et al., TEV, Vilnius, 2012, 69–80 | MR | Zbl

[7] Bolotnikov Yu. V., Sachkov V. N., Tarakanov V. E., “Asimptoticheskaya normalnost nekotorykh velichin, svyazannykh s tsiklovoi strukturoi sluchainykh podstanovok”, Matem. sb., 99(141):1 (1976), 121–133 | MR | Zbl

[8] Volynets L. M., “Primer nestandartnoi asimptotiki chisla podstanovok s ogranicheniyami na dliny tsiklov”, Veroyatnostnye protsessy i ikh prilozheniya, MIEM, M., 1989, 85–90 | MR

[9] Gnedin A., Iksanov A., Marynych A., “A generalization of the Erdos–Turán Law for the Order of Random Permutation”, Comb. Probab. Comput., 21:5 (2012), 715–733 | DOI | MR | Zbl

[10] Grusho A. A., “Properties of random permutations with constraints on the maximum cycle length”, Probab. Meth. Discrete Math., Proc. Third Int. Petrozavodsk Conf., VSP/TVP, Utrecht/Moscow, 1993, 459–469 | MR

[11] Dénes J., “On transformations, transformation-semigroups and graphs”, Theory of Graphs, Proc. Colloq. (Tihany, 1966), Academic Press, New York, 1968, 65–75 | MR

[12] Dénes J., “Connections between transformation semigroups and graphs”, Theory of Graphs, Internat. Sympos. (Rome, 1966), Gordon and Breach, New York, 1967, 93–101 | MR

[13] Dénes J., “Some combinatorial properties of transformations and their connections with the theory of graphs”, J. Comb. Theory, 9:2 (1970), 108–116 | DOI | MR | Zbl

[14] Erdos P., Turán P., “On some problems of a statistical group-theory. I”, Z. Wahrscheinlichkeitstheorie verw. Geb., 4 (1965), 175–186 | DOI | MR | Zbl

[15] Erdos P., Turán P., “On some problems of a statistical group-theory. II”, Acta Mathematica Academiae Scientiarum Hungaricae, 18:1–2 (1967), 151–163 | DOI | MR | Zbl

[16] Erdos P., Turán P., “On some problems of a statistical group-theory. III”, Acta Mathematica Academiae Scientiarum Hungaricae, 18:3–4 (1967), 309–320 | DOI | MR | Zbl

[17] Erdos P., Turán P., “On some problems of a statistical group-theory. IV”, Acta Mathematica Academiae Scientiarum Hungaricae, 19:3–4 (1968), 413–435 | DOI | MR | Zbl

[18] Ewens W. J., “The sampling theory of selectively neutral alleles”, Theor Popul Biol., 3:1 (1972), 87–112 | DOI | MR | Zbl

[19] Hansen J. C., Jaworski J., “Local properties of random mappings with exchangeable in-degrees”, Adv. Appl. Probab., 40:1 (2008), 183–205 | DOI | MR | Zbl

[20] Hansen J. C., Jaworski J., “Random mappings with exchangeable in-degrees”, Random Struct. Algor., 33:1 (2008), 105–126 | DOI | MR | Zbl

[21] Hansen J. C., Jaworski J., “A random mapping with preferential attachment”, Random Struct. Algor., 34:1 (2009), 87–111 | DOI | MR | Zbl

[22] Hansen J. C., Jaworski J., “Random mappings with a given number of cyclical points”, Ars Comb., 94 (2010), 341–359 | MR | Zbl

[23] Hansen J. C., Jaworski J., “Predecessors and successors in random mappings with exchangeable in-degrees”, J. Appl. Probab., 50:3 (2013), 721–740 | DOI | MR | Zbl

[24] Hansen J. C., Jaworski J., “Random mappings with Ewens cycle structure”, Ars Comb., 112 (2013), 307–322 | MR | Zbl

[25] Hansen J. C., Jaworski J., “Structural transition in random mappings”, Electron. J. Comb., 21:1 (2014), 1–18 | MR | Zbl

[26] Zakharovas V., “Skorost skhodimosti odnoi velichiny, opredelennoi na sluchainykh polinomakh, k normalnomu zakonu”, Liet. Mat. Rink., 42:1 (2002), 113–138 | MR

[27] Zakharovas V., “Raspredelenie logarifma poryadka sluchainoi podstanovki”, Liet. Mat. Rink., 44:3 (2004), 372–406 | MR

[28] Zubkov A. M., “Vychislenie raspredelenii kharakteristik chisel komponent i tsiklicheskikh tochek sluchainogo otobrazheniya”, Matem. vopr. kriptogr., 1:2 (2010), 5–18

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

[30] Ivchenko G. I., Medvedev Yu. I., “O sluchainykh podstanovkakh”, Tr. po diskr. matem., 5, Fizmatlit, M., 2002, 73–92

[31] Ivchenko G. I., Medvedev Yu. I., “Sluchainye kombinatornye ob'ekty”, Dokl. RAN, 396:2 (2004), 151–154 | MR | Zbl

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

[33] Ivchenko G. I., Soboleva M. V., “Nekotorye neravnoveroyatnye modeli sluchainykh podstanovok”, Diskretnaya matematika, 23:3 (2011), 23–31 | DOI | MR | Zbl

[34] Kalugin I. B., “Odin klass sluchainykh otobrazhenii”, Veroyatnostnye zadachi diskretnoi matematiki, Sbornik rabot, Tr. MIAN SSSR, 177, 1986, 75–104 ; Kalugin I. B., “A class of random mappings”, Proc. Steklov Inst. Math., 177:4 (1988), 79–110 | MR | Zbl

[35] Kolchin A. V., “Uravneniya, soderzhaschie neizvestnuyu podstanovku”, Diskretnaya matematika, 6:1 (1994), 100–115 | MR | Zbl

[36] Kolchin V. F., Sluchainye otobrazheniya, Nauka, M., 1984, 208 pp. ; Kolchin V. F., Random mappings, Optimization Software, 1986, 206 pp. | MR | MR | Zbl

[37] Kolchin V. F., “O chisle podstanovok s ogranicheniyami na dliny tsiklov”, Diskretnaya matematika, 1:2 (1989), 97–109 ; Kolchin V. F., “The number of permutations with restrictions on the lengths of cycles”, Discrete Math. Appl., 1:2 (1991), 179–193 | MR | Zbl | DOI

[38] Kolchin V. F., “The number of permutations with cycle lengths from a fixed set”, Random graphs, Fourth Int. Seminar on Random Graphs and Probab. Meth. in Comb. (Poznań, Poland, August 7–11, 1989), v. 2, Wiley, New York, 1992, 139–149 | MR | Zbl

[39] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2000, 256 pp. ; Kolchin V. F., Random Graphs, Cambridge Univ. Press, Cambridge, 1999, 256 pp. | MR | MR | Zbl

[40] Landau E., Handbuch der Lehre von der Verteilung der Primzahlen, Leipzig B. G. Teubner, Leipzig–Berlin, 1909, 596 pp.

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

[42] Manstavicius E., “On random permutations without cycles of some lenghts”, Periodica Mathematica Hungary, 42:1–2 (2001), 37–44 | DOI | MR | Zbl

[43] Manstavicius E., “A functional limit theorem on powers of random permutations”, Lithuanian Math. J., 49:3 (2009), 145–157 | DOI | MR

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

[45] Manstavicius E., “On total variation approximations for random assemblies”, DMTCS Proceedings, 23rd Int. Meet. Probab. Comb. and Asympt. Methods for the Anal. Alg. (AofA'12) (Montreal, Canada, June 18–22, 2012), eds. Broutin N., Devroye L., 2012, 97–108 | MR | Zbl

[46] Manstavicius E., Petuchovas R., “Permutations without long or short cycles”, Electr. Notes Discr. Math., 49 (2015), 153–158 | DOI | Zbl

[47] Manstavicius E., Petuchovas R., “Local probabilities for random permutations without long cycles”, Electr. J. Comb., 23:1 (2016), #P1.58, 25 pp. | MR | Zbl

[48] Manstavicius E., “A Turán–Kubilius inequality on mappings of a finite set”, From Arithmetic to Zeta-Functions, Number Theory in Memory of Wolfgang Schwarz, eds. J. Sander et al., Springer, 2016, 295–307 | DOI

[49] Mineev M. P., Pavlov A. I., “Ob odnom uravnenii v podstanovkakh”, Teoriya chisel, matematicheskii analiz i ikh prilozheniya, Sbornik statei. Posvyaschaetsya akademiku Ivanu Matveevichu Vinogradovu k ego vosmidesyatipyatiletiyu, Tr. MIAN SSSR, 142, 1976, 182–194 ; Mineev M. P., Pavlov A. I., “An equation in permutations”, Proc. Steklov Inst. Math., 142 (1979), 195–208 | MR | Zbl

[50] Mutafchiev L. R., “Sluchainye otobrazheniya s ogranichenyami nad sootvetstvuyuschimi grafami”, Serdica, 4:2–3 (1978), 105–110 | MR | Zbl

[51] Nicolas J.-L., “Distribution statistique de l'ordre d'un élément du groupe symétrique”, Acta Math. Hungar, 45 (1985), 69–84 | DOI | MR | Zbl

[52] Pavlov A. I., “O predelnom raspredelenii chisla tsiklov i logarifma poryadka odnogo klassa podstanovok”, Matem. sb., 114(156):4 (1981), 611–642 ; Pavlov A. I., “On the limit distribution of the number of cycles and the logarithm of the order of a class of permutations”, Math. USSR-Sb., 42:4 (1982), 539–567 | MR | Zbl | DOI | MR

[53] Pavlov A. I., “O nekotorykh klassakh podstanovok s teoretiko-chislovymi ogranicheniyami na dliny tsiklov”, Matem. sb., 129(171):2 (1986), 252–263 ; Pavlov A. I., “On some classes of permutations with number-theoretic restrictions on the lengths of cycles”, Math. USSR-Sb., 57:1 (1987), 263–275 | MR | Zbl | DOI | Zbl

[54] Pavlov A. I., “O chisle podstanovok s dlinami tsiklov iz zadannogo mnozhestva”, Diskretnaya matematika, 3:3 (1991), 109–123 ; Pavlov A. I., “On the number of permutations with cycle lengths in a given set”, Discrete Math. Appl., 2:4 (1992), 445–459 | MR | Zbl | DOI

[55] Pavlov A. I., “O teoreme Erdesha–Turana o logarifme poryadka sluchainoi podstanovki”, Doklady RAN, 350:2 (1996), 170–173 | MR | Zbl

[56] Pavlov A. I., “O dvukh klassakh podstanovok s teoretiko-chislovymi ogranicheniyami na dliny tsiklov”, Matem. zametki, 62:6 (1997), 881–891 | DOI | MR | Zbl

[57] Pavlov Yu. L., Sluchainye lesa, KarNTs RAN, Petrozavodsk, 1996, 259 pp.; Pavlov Yu L., Random Forests, VSP, 2000, 122 pp. | MR

[58] Pavlov Yu. L., “Predelnye teoremy dlya ob'emov derevev nepomechennogo grafa sluchainogo otobrazheniya”, Diskretnaya matematika, 16:3 (2004), 63–75 | DOI | MR | Zbl

[59] Pavlov Yu. L., Myullyari T. B., “Predelnye raspredeleniya chisla vershin zadannoi kratnosti v lese sluchainogo otobrazheniya s izvestnym chislom tsiklov”, Diskretnaya matematika, 24:1 (2012), 132–139 | DOI | MR | Zbl

[60] Postnikov A. G., Vvedenie v analiticheskuyu teoriyu chisel, Nauka, M., 1971, 416 pp. ; Postnikov A. G., Introduction to Analytic Number Theory, Am. Math. Soc., 1988, 320 pp. | MR | MR | Zbl

[61] Proskurin G. V., “Predelnye raspredeleniya chisla tsiklicheskikh tochek ustoichivogo sluchainogo otobrazheniya”, Diskretnaya matematika, 6:2 (1994), 74–87 | MR | Zbl

[62] Sachkov V. N., “Otobrazheniya konechnogo mnozhestva s ogranicheniyami na kontury i vysotu”, Teoriya veroyatn. i ee primen., 17:4 (1972), 679–694 ; Sachkov V. N., “Mappings of a finite set with constraints on contours and height”, Theory Probab. Appl., 17:4 (1973), 640–656 | MR | Zbl | DOI

[63] Sachkov V. N., “Sluchainye otobrazheniya ogranichennoi vysoty”, Teoriya veroyatn. i ee primen., 18:1 (1973), 122–132 | MR | Zbl

[64] Sachkov V. N., Kombinatornye metody diskretnoi matematiki, Nauka, M., 1977, 320 pp.; Sachkov V. N., Combinatorial methods in discrete mathematics, Cambridge Univ. Press, 1996, 306 pp. | MR

[65] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, M., 1978, 288 pp. ; Sachkov V. N., Probabilistic methods in combinatorial analysis, Cambridge Univ. Press, 1997, 246 pp. | MR | MR | Zbl

[66] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, MTsNMO, M., 2004, 424 pp.

[67] Sevastyanov B. A., “Skhodimost po raspredeleniyu sluchainykh otobrazhenii konechnykh mnozhestv k vetvyaschimsya protsessam”, Diskretnaya matematika, 17:1 (2005), 18–21 | DOI | MR | Zbl

[68] Seneta E., Pravilno menyayuschiesya funktsii, Nauka, M., 1985, 144 pp.; Seneta E., Regularly Varying Functions, Springer, 1976, 116 pp. | MR | Zbl

[69] Timashëv A. N., “Sluchainye otobrazheniya konechnykh mnozhestv s izvestnym chislom komponent”, Teoriya veroyatn. i ee primen., 48:4 (2003), 818–828 ; Timashev A. N., “Random mappings of finite sets with a known number of components”, Theory Probab. Appl., 48:4 (2004), 741–751 | DOI | MR | Zbl | DOI

[70] Timashëv A. N., “Predelnye teoremy v skhemakh razmeschenii chastits po razlichnym yacheikam s ogranicheniyami na zapolneniya yacheek”, Teoriya veroyatn. i ee primen., 49:4 (2004), 712–725 ; Timashev A. N., “Limit theorems in schemes for allocating particles to different cells with restrictions on the filling of cells”, Theory Probab. Appl., 49:4 (2005), 659–670 | DOI | MR | Zbl | DOI

[71] Timashëv A. N., Obobschennaya skhema razmescheniya v zadachakh veroyatnostnoi kombinatoriki, Akademiya, M., 2011, 267 pp.

[72] Timashëv A. N., Bolshie ukloneniya v veroyatnostnoi kombinatorike, Akademiya, M., 2011, 247 pp.

[73] Timashëv A. N., Asimptoticheskie razlozheniya v veroyatnostnoi kombinatorike, TVP, M., 2010, 312 pp.

[74] Timashëv A. N., Additivnye zadachi s ogranicheniyami na znacheniya slagaemykh, Akademiya, M., 2015, 183 pp.

[75] Timashëv A. N., “Sluchainye podstanovki s prostymi dlinami tsiklov”, Teoriya veroyatn. i ee primen., 61:2 (2016), 365–377 | DOI | MR

[76] Cheplyukova I. A., “Odin sluchai predelnogo raspredeleniya chisla tsiklicheskikh vershin v sluchainom otobrazhenii”, Diskretnaya matematika, 16:3 (2004), 76–84 | DOI | MR | Zbl

[77] Yakymiv A. L., Veroyatnostnye prilozheniya tauberovykh teorem, Fizmatlit, M., 2005, 256 pp.

[78] Yakymiv A. L., “Predelnaya teorema dlya logarifma poryadka sluchainoi $A$-podstanovki”, Diskretnaya matematika, 22:1 (2010), 126–149 | DOI | MR | Zbl

[79] Yakymiv A. L., “O chisle tsiklicheskikh tochek sluchainogo $A$-otobrazheniya”, Diskretnaya matematika, 25:3 (2013), 116–127 | DOI | MR

[80] Yakymiv A. L., “Distribution of the order in some classes of random mappings”, Proc. XVII Int. Summer Conf. Probab. Stat., ISCPS-2016 (Pomorie, Bulgaria, 25 June–1 July 2016), eds. Stoimenova E., Slavtchova-Bojkova M., Institute of Mathematics and Informatics Bulgarian Academy of Sciences, Sofia, 2016, 42–50