A limit theorem for the logarithm of the order of a~random $A$-permutation

A. L. Yakymiv

Diskretnaya Matematika, Tome 22 (2010) no. 1, pp. 126-149.

Résumé

In this article, a random permutation $\tau_n$ is considered which is uniformly distributed on the set of all permutations of degree $n$ whose cycle lengths lie in a fixed set $A$ (the so-called $A$-permutations). It is assumed that the set $A$ has an asymptotic density $\sigma>0$, and $|k\colon k\leq n,\ k\in A,\ m-k\in A|/n\to\sigma^2$ as $n\to\infty$ uniformly in $m\in[n,Cn]$ for an arbitrary constant $C>1$. The minimum degree of a permutation such that it becomes equal to the identity permutation is called the order of permutation. Let $Z_n$ be the order of a random permutation $\tau_n$. In this article, it is shown that the random variable $\ln Z_n$ is asymptotically normal with mean $l(n)=\sum_{k\in A(n)}\ln(k)/k$ and variance $\sigma\ln^3(n)/3$, where $A(n)=\{k\colon k\in A,\ k\leq n\}$. This result generalises the well-known theorem of P. Erdős and P. Turán where the uniform distribution on the whole symmetric group of permutations $S_n$ is considered, i.e., where $A$ is equal to the set of positive integers $\mathbb N$.

Bibliographie

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

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

[3] Best M. R., “The distribution of some variables on symmetric group”, Proc. Nederl. Akad. Wet. Ser. A, 73 (1970), 385–402 | MR | Zbl

[4] Bovey J. D., “An approximate probability distribution for the order of elements of the symmetric group”, Bull. London Math. Soc., 12 (1980), 41–46 | DOI | MR | Zbl

[5] 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

[6] Bolotnikov Yu. V., Sachkov V. N., Tarakanov V. E., “O nekotorykh klassakh sluchainykh velichin na tsiklakh sluchainykh podstanovok”, Matem. sb., 108(150):1 (1979), 91–104 | MR | Zbl

[7] Volynets L. M., “Chislo reshenii uravneniya v simmetricheskoi gruppe”, Veroyatnostnye protsessy i ikh prilozheniya, MIEM, Moskva, 1985, 104–109

[8] Volynets L. M., “Chislo reshenii uravneniya $x^s=e$ v simmetricheskoi gruppe”, Matem. zametki, 40:2 (1986), 155–160 | MR | Zbl

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

[10] Goncharov V. L., “Iz oblasti kombinatoriki”, Izvestiya AN SSSR. Ser. matem., 8:1 (1944), 3–48 | MR | Zbl

[11] Erdős P., Turán P., “On some problems of a statistical group-theory. I”, Z. Wahrscheinlichkeitstheor. Verw. Geb., 4 (1965), 175–186 | DOI | MR | Zbl

[12] Erdős P., Turán P., “On some problems of a statistical group-theory. II”, Acta Math. Acad. Sci. Hung., 18 (1967), 151–163 | DOI | MR | Zbl

[13] Erdős P., Turán P., “On some problems of a statistical group-theory. III”, Acta Math. Acad. Sci. Hung., 18 (1967), 309–320 | DOI | MR | Zbl

[14] Erdős P., Turán P., “On some problems of a statistical group-theory. IV”, Acta Math. Acad. Sci. Hung., 19 (1968), 413–435 | DOI | MR | Zbl

[15] Grusho A. A., “Properties of random permutations with constraints on the maximum cycle length”, Probabilistic methods in discrete mathematics, eds. Kolchin V. F. et al., TVP, Moscow, 1993, 60–63 | MR | Zbl

[16] Ivchenko G. I., Medvedev Yu. I., “O sluchainykh podstanovkakh”, Trudy po diskretnoi matematike, 5, 2002, 73–92

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

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

[19] Kolchin V. F., “Novoe dokazatelstvo asimptoticheskoi lognormalnosti poryadka sluchainoi podstanovki”, Kombinatornyi i asimptoticheskii analiz, Krasnoyarskii gos. univ., Krasnoyarsk, 1977, 82–93

[20] Kolchin V. F., Sluchainye otobrazheniya, Nauka, Moskva, 1984 | MR | Zbl

[21] Kolchin V. F., “O chisle tsiklov podstanovok s ogranicheniyami na dliny tsiklov”, Diskretnaya matematika, 1:2 (1989), 97–109 | MR | Zbl

[22] Kolchin V. F., “The number of permutations with cycle lengths from a fixed set”, Random graphs, v. 2, eds. Frieze A. et al., Wiley, Chichester, 1992, 139–149 | MR | Zbl

[23] Kolchin V. F., Sluchainye grafy, Fizmatlit, Moskva, 2000 | MR | Zbl

[24] Manstavičius E., “On random permutations without cycles of some lengths”, Period. Math. Hung., 42 (2001), 37–44 | DOI | MR | Zbl

[25] Mineev M. P., Pavlov A. I., “O chisle podstanovok spetsialnogo vida”, Matem. sb., 99(141):3 (1976), 468–476 | MR | Zbl

[26] Mineev M. P., Pavlov A. I., “Ob uravnenii v podstanovkakh”, Trudy Matematicheskogo instituta im. V. A. Steklova AN SSSR, 142, 1976, 182–194 | MR | Zbl

[27] Pavlov A. I., “O teoreme Erdësha i Turana”, Problemy kibernetiki, 64, 1980, 57–66 | Zbl

[28] Pavlov A. I., “O predelnom raspredelenii chisla tsiklov i logarifma poryadka odnogo klassa podstanovok”, Matem. sb., 114(156):4 (1981), 611–642 | MR | Zbl

[29] Pavlov A. I., “O chisle tsiklov i tsiklovoi strukture podstanovok nekotorykh klassov”, Matem. sb., 124(166):4 (1984), 536–556 | MR | Zbl

[30] Pavlov A. I., “O nekotorykh klassakh podstanovok s teoretiko-chislovymi ogranicheniyami na dliny tsiklov”, Matem. sb., 129(171):2 (1986), 252–263 | MR | Zbl

[31] Pavlov A. I., “O podstanovkakh s dlinami tsiklov iz zadannogo mnozhestva”, Teoriya veroyatnostei i ee primeneniya, 31:3 (1986), 618–619

[32] Pavlov A. I., “O chisle podstanovok s dlinami tsiklov iz zadannogo mnozhestva”, Diskretnaya matematika, 3:3 (1991), 109–123 | MR | Zbl

[33] Pavlov A. I., “Asimptotika chisla podstanovok s teoretiko-chislovymi ogranicheniyami na dliny tsiklov”, Dokl. RAN, 335:5 (1994), 556–559 | MR | Zbl

[34] Pavlov A. I., “O teoreme Erdësha–Turana o logarifme poryadka sluchainoi podstanovki”, Dokl. RAN, 350:2 (1996), 170–173 | MR | Zbl

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

[36] Postnikov A. G., Vvedenie v analiticheskuyu teoriyu chisel, Nauka, Moskva, 1971 | MR | Zbl

[37] Sachkov V. N., “Otobrazheniya konechnogo mnozhestva s ogranicheniyami na kontur i vysotu”, Teoriya veroyatnostei i ee primeneniya, 17:4 (1972), 679–694 | MR | Zbl

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

[39] Sachkov V. N., Kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1977

[40] Sachkov V. N., “Asimptoticheskie formuly i predelnye raspredeleniya dlya kombinatornykh konfiguratsii, porozhdaemykh mnogochlenami”, Diskretnaya matematika, 19:3 (2007), 3–14 | MR | Zbl

[41] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, Moskva, 1978 | MR | Zbl

[42] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, MTsNMO, Moskva, 2004

[43] Seneta E., Pravilno menyayuschiesya funktsii, Nauka, Moskva, 1985 | MR | Zbl

[44] Timashëv A. N., “Predelnye teoremy v skhemakh razmeschenii chastits po razlichnym yacheikam s ogranicheniyami na zapolneniya yacheek”, Teoriya veroyatnostei i ee primeneniya, 49:4 (2004), 712–725 | MR | Zbl

[45] Timashëv A. N., “Sluchainye podstanovki s dlinami tsiklov iz zadannogo konechnogo mnozhestva”, Diskretnaya matematika, 20:1 (2008), 25–37 | MR

[46] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 2, Mir, Moskva, 1984 | Zbl

[47] Yakymiv A. L., “Raspredelenie dliny $m$-go maksimalnogo tsikla sluchainoi $A$-podstanovki”, Diskretnaya matematika, 17:4 (2005), 40–58 | MR | Zbl

[48] Yakymiv A. L., Veroyatnostnye prilozheniya tauberovykh teorem, Fizmatlit, Moskva, 2005 | Zbl

[49] Yakymiv A. L., “Predelnaya teorema dlya obschego chisla tsiklov sluchainoi $A$-podstanovki”, Teoriya veroyatnostei i ee primeneniya, 52:1 (2007), 69–83 | MR | Zbl

[50] Yakymiv A. L., “Sluchainye $A$-podstanovki: skhodimost k puassonovskomu protsessu”, Matem. zametki, 81:6 (2007), 939–947 | MR | Zbl

[51] Yakymiv A. L., “Predelnaya teorema dlya srednikh chlenov variatsionnogo ryada dlin tsiklov sluchainoi $A$-podstanovki”, Teoriya veroyatnostei i ee primeneniya, 54:1 (2009), 63–79

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