On the Number of Components of Fixed Size in a Random $A$-Mapping

A. L. Yakymiv

Matematičeskie zametki, Tome 97 (2015) no. 3, pp. 462-470.

Résumé

Let $\mathfrak S_n$ be the semigroup of mappings of a set of $n$ elements into itself, let $A$ be a fixed subset of the set of natural numbers $\mathbb N$, and let $V_n(A)$ be the set of mappings from $\mathfrak S_n$ for which the sizes of the contours belong to the set $A$. Mappings from $V_n(A)$ are usually called $A$-mappings. Consider a random mapping $\sigma_n$ uniformly distributed on $V_n(A)$. It is assumed that the set $A$ possesses asymptotic density $\varrho$, including the case $\varrho=0$. Let $\xi_{in}$ be the number of connected components of a random mapping $\sigma_n$ of size $i\in\mathbb N$. For a fixed integer $b\in\mathbb N$, as $n\to\infty$, the asymptotic behavior of the joint distribution of random variables $\xi_{1n},\xi_{2n},\dots,\xi_{bn}$ is studied. It is shown that this distribution weakly converges to the joint distribution of independent Poisson random variables $\eta_1,\eta_2,\dots,\eta_b$ with some parameters $\lambda_i=\mathsf E\eta_{i}$, $i\in\mathbb N$.

Détail

Keywords: random $A$-mapping, asymptotic behavior of the joint distribution of random variables, regularly/slowly varying function in the sense of Karamata, Stirling's formula.
Mots-clés : Poisson random variable

Bibliographie

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

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

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

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

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

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

[7] A. A. Grusho, “Properties of random permutations with constrains on the maximum cycle length”, Probabilistic Methods in Discrete Mathematics, Progr. Pure Appl. Discrete Math., 1, VSP, Utrecht, 1993, 459–469 | MR

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

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

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

[11] F. Manstavicius, “On random permutations without cycles of some lengths”, Period. Math. Hung., 42:1-2 (2001), 37–44 | DOI | MR | Zbl

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

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

[14] A. N. Timashev, “Predelnye teoremy v skhemakh razmeschenii chastits po razlichnym yacheikam s ogranicheniyami na zapolneniya yacheek”, TVP, 49:4 (2004), 712–725 | DOI | MR | Zbl

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

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

[17] V. N. Sachkov, “Sluchainye otobrazheniya ogranichennoi vysoty”, TVP, 18:1 (1973), 122–132 | MR | Zbl

[18] Yu. L. Pavlov, Sluchainye lesa, Karelskii nauchnyi tsentr RAN, Petrozavodsk, 1996

[19] V. F. Kolchin, Sluchainye otobrazheniya, Teoriya veroyatnostei i matematicheskaya statistika, Nauka, M., 1984 | MR | Zbl

[20] V. F. Kolchin, Sluchainye grafy, Teoriya veroyatnostei i matematicheskaya statistika, Fizmatlit, M., 2000 | MR | Zbl

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

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

[23] A. N. Timashev, “Sluchainye otobrazheniya konechnykh mnozhestv s izvestnym chislom komponent”, TVP, 48:4 (2003), 818–828 | DOI | MR | Zbl

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

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

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

[27] R. Arratia, A. D. Barbour, S. Tavaré, Logarithmic Combinatorial Structures: A Probabilistic Approach, EMS Monogr. Math., European Math. Soc., Zürich, 2003 | MR | Zbl

[28] R. J. Riddell Jr., G. E. Uhlenbeck, “On the theory of the virial development of the equation of state of mono-atomic gases”, J. Chem. Phys., 21 (1953), 2056–2064 | DOI | MR

[29] L. Katz, “Probability of indecomposability of a random mapping function”, Ann. Math. Statist., 26:3 (1955), 512–517 | DOI | MR | Zbl

[30] B. Bollobás, Random Graphs, Academic Press, London, 1985 | MR | Zbl

[31] B. Bollobás, Random Graphs, Cambridge Stud. Adv. Math., 73, Second edition, Cambridge University Press, 2001 | MR | Zbl

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