Random $A$-permutations and Brownian motion

A. L. Yakymiv

Informatics and Automation, Branching processes, random walks, and related problems, Tome 282 (2013), pp. 315-335.

Résumé

We consider a random permutation $\tau _n$ uniformly distributed over the set of all degree $n$ permutations whose cycle lengths belong to a fixed set $A$ (the so-called $A$-permutations). Let $X_n(t)$ be the number of cycles of the random permutation $\tau _n$ whose lengths are not greater than $n^t$, $t\in[0,1]$, and $l(t)=\sum_{i\leq t,i\in A}1/i$, $t>0$. In this paper, we show that the finite-dimensional distributions of the random process $\{Y_n(t)=(X_n(t)-l(n^t))/\sqrt{\varrho\ln n}$, $t\in[0,1]\}$ converge weakly as $n\to\infty$ to the finite-dimensional distributions of the standard Brownian motion $\{W(t),t\in[0,1]\}$ in a certain class of sets $A$ of positive asymptotic density $\varrho$.

Bibliographie

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

[2] Curtiss J.H., “A note on the theory of moment generating functions”, Ann. Math. Stat., 13 (1942), 430–433 | DOI | MR | Zbl

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

[4] Donnelly P., Kurtz T.G., Tavaré S., “On the functional central limit theorem for the Ewens sampling formula”, Ann. Appl. Probab., 1 (1991), 539–545 | DOI | MR | Zbl

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

[6] Hansen J.C., “A functional central limit theorem for the Ewens sampling formula”, J. Appl. Probab., 27 (1990), 28–43 | DOI | MR | Zbl

[7] Kolchin V.F., “The number of permutations with cycle lengths from a fixed set”, Random graphs, V. 2, J. Wiley Sons, New York, 1992, 139–149 | MR | Zbl

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

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

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

[11] Kolchin V.F., Sluchainye otobrazheniya, Nauka, M., 1984 | MR

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

[13] Kolchin V.F., Sluchainye grafy, Fizmatlit, M., 2000 | MR | Zbl

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

[15] Mineev M.P., Pavlov A.I., “Ob odnom uravnenii v podstanovkakh”, Tr. MIAN, 142, 1976, 182–194 | MR | Zbl

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

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

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

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

[20] Postnikov A.G., Vvedenie v analiticheskuyu teoriyu chisel, Nauka, M., 1971 | MR

[21] Sachkov V.N., “Otobrazheniya konechnogo mnozhestva s ogranicheniyami na kontury i vysotu”, Teoriya veroyatn. i ee primen., 17:4 (1972), 679–694 | MR | Zbl

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

[23] Sachkov V.N., Kombinatornye metody diskretnoi matematiki, Nauka, M., 1977

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

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

[26] Sevastyanov B.A., Vetvyaschiesya protsessy, Nauka, M., 1971 | MR | Zbl

[27] Seneta E., Pravilno menyayuschiesya funktsii, Nauka, M., 1985 | MR | Zbl

[28] Timashev A.N., Obobschennaya skhema razmescheniya v zadachakh veroyatnostnoi kombinatoriki, Akademiya, M., 2011

[29] Timashev A.N., Asimptoticheskie razlozheniya v veroyatnostnoi kombinatorike, TVP, M., 2011

[30] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, T. 2, Mir, M., 1984

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

[32] Yakymiv A.L., Veroyatnostnye prilozheniya tauberovykh teorem, Fizmatlit, M., 2005 | Zbl

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

[34] Yakymiv A.L., “Predelnaya teorema dlya srednikh chlenov variatsionnogo ryada dlin tsiklov sluchainoi $A$‐podstanovki”, Teoriya veroyatn. i ee primen., 54:1 (2009), 63–79 | DOI | MR | Zbl

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

[36] Yakymiv A.L., “Odno obobschenie teoremy Kurtissa dlya proizvodyaschikh funktsii momentov”, Mat. zametki, 90:6 (2011), 947–952 | DOI | MR