Random $A$-Permutations: Convergence to a Poisson Process

A. L. Yakymiv

Matematičeskie zametki, Tome 81 (2007) no. 6, pp. 939-947.

Résumé

Suppose that $S_n$ is the permutation group of degree $n$, $A$ is a subset of the set of natural numbers $\mathbb N$, and $T_n=T_n(A)$ is the set of all permutations from $S_n$ whose cycle lengths belong to the set $A$. Permutations from $T_n$ are usually called $A$-permutations. We consider a wide class of sets $A$ of positive asymptotic density. Suppose that $\zeta_{mn}$ is the number of cycles of length $m$ of a random permutation uniformly distributed on $T_n$. It is shown in this paper that the finite-dimensional distributions of the random process $\{\zeta_{mn},m\in A\}$ weakly converge as $n\to\infty$ to the finite-dimensional distributions of a Poisson process on $A$.

Détail

Keywords: random permutation, total variance distance
Mots-clés : Poisson process, permutation group, permutation cycle, normal distribution.

Bibliographie

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

[2] A. L. Yakymiv, “Raspredelenie dliny $m$-go maksimalnogo tsikla sluchainoi $A$" pod"-stanovki”, Diskret. matem., 17:4 (2005), 40–58 | MR | Zbl

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

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

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

[6] M. P. Mineev, A. I. Pavlov, “Ob uravnenii v podstanovkakh”, Teoriya chisel, matematicheskii analiz i ikh prilozheniya, Tr. MIAN, 142, 1976, 182–194 | MR | Zbl

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

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

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

[10] Veroyatnost i matematicheskaya statistika, Nauchnoe izdatelstvo “Bolshaya rossiiskaya entsiklopediya”, M., 1999

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

[12] V. F. Kolchin, “Odna zadacha o razmeschenii chastits po yacheikam i tsikly sluchainykh podstanovok”, Teoriya veroyatn. i ee primen., 16:1 (1971), 67–82 | MR | Zbl

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

[14] A. L. Yakymiv, “O podstanovkakh s dlinami tsiklov iz zadannogo mnozhestva”, Diskret. matem., 1:1 (1989), 125–134 | MR | Zbl

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

[16] R. Arratia, S. Tavare, “The cycle structure of random permutations”, Ann. Probab., 20 (1992), 1567–1591 | DOI | MR | Zbl

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

[18] L. A. Shepp, S. P. Lloyd, “Ordered cycle lengths in a random permutation”, Trans. Amer. Math. Soc., 121:2 (1966), 340–357 | DOI | MR | Zbl