On random mappings with restrictions on component sizes

A. L. Yakymiv

Diskretnaya Matematika, Tome 35 (2023) no. 3, pp. 143-163.

Résumé

Let $\mathfrak{S}_{n}$ be a semigroup of mappings from the $n$-element set $X$ into itself and let $\mathfrak{S}_{n}(A)$ be a set of mappings from $\mathfrak{S}_{n}$ whose component sizes belong to the set $A$. By $\sigma_n=\sigma_n(A)$ we denote a random mapping having a uniform distribution on the set $\mathfrak{S}_{n}(A)$. Such objects were considered by A.N. Timashev in 2019. For a certain class of sets $A$ having positive densities in the set $N$ of natural numbers, the asymptotic number of elements of the set $\mathfrak{S}_{n}(A)$ is found for $n\rightarrow\infty$. An estimate is also obtained for the total variation distance between the $\sigma_n(A)$ mapping structure and the corresponding sequence of independent Poisson random variables.

Détail

Keywords: mappings with constraints on component sizes, total number of elements.

Bibliographie

[1] Arratia R., Barbour A. D., Tavare S., Logarithmic Combinatorial Structures: A Probabilistic Approach, European Mathematical Society, 2003, 363 pp. | MR | Zbl

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

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

[4] Bingham N. H., Goldie Ch. M., Teugels J. L., Regular Variation, Cambridge University Press, 1987, 494 pp. | MR | Zbl

[5] Goncharov V. L., “Iz oblasti kombinatoriki”, Izv. AN SSSR, ser. mat., 8, 1944, 3-48 | Zbl

[6] Hansen J. C., “A functional central limit theorem for random mappings”, Ann. Probab, 17:1 (1989), 317–332 | DOI | MR | Zbl

[7] Harris B., “A survey of the early history of the theory of random mappings”, Probabilistic methods in discrete mathematics (Petrozavodsk, 1992), Progr. Pure Appl. Discrete Math., 1, VSP, Utrecht, 1993, 1–22 | MR

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

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

[10] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 2, Mir, M., 1984, 752 pp. | MR

[11] Karamata J., “Über die Hardy–Littelwoodsche Umkehrungen des Abelschen Steitigkeitssatzes”, Math. Z., 32 (1930), 319–320 | DOI | MR

[12] Karamata J., “Neuer Beweis und Verallgemeinerung einiger Tauberian-Sätze”, Math. Z., 33:2 (1931), 294–299 | DOI | MR | Zbl

[13] Kolchin V. F., Sluchainye otobrazheniya, Nauka, M., 1984, 208 pp.

[14] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2000, 256 pp.

[15] Manstavićius E., “Total variation approximation and a functional limit theorem”, Monatsh. Math., 161 (2010), 313–334 | DOI | MR | Zbl

[16] Manstavićius E., “On total variation approximations for random assemblies”, AofA'12, Discrete Math. Theoretical Computer Sci., AQ, 97–108 | MR | Zbl

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

[18] Postnikov A. G., Vvedenie v analiticheskuyu teoriyu chisel, Nauka, M., 1971, 416 pp.

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

[20] Sachkov V. N., Veroyatnostnye metody v kombinatornom analize, Nauka, M., 1978, 286 pp.

[21] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, MTsNMO, M., 2004, 423 pp. | MR

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

[23] Timashev A. N., Bolshie ukloneniya v veroyatnostnoi kombinatorike, Akademiya, M., 2011, 248 pp.

[24] Timashev A. N., Asimptoticheskie razlozheniya v veroyatnostnoi kombinatorike, TVP, M., 2011, 312 pp.

[25] Timashev A. N., Additivnye zadachi s ogranicheniyami na znacheniya slagaemykh, Akademiya, M., 2015, 184 pp.

[26] Timashev A. N., Raspredeleniya tipa stepennogo ryada i obobschennaya skhema razmescheniya, Akademiya, M., 2016, 168 pp.

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

[28] Timashev A. N., Sluchainye komponenty v obobschennoi skheme razmescheniya, Akademiya, M., 2017, 120 pp.

[29] Timashev A. N., “Sluchainye otobrazheniya s ob'emami komponent iz zadannogo mnozhestva”, Teoriya veroyatn. i ee primen., 64:3 (2019), 599–609 | DOI | MR | Zbl

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

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

[32] Yakymiv A. L., “O poryadke sluchainoi podstanovki s vesami tsiklov”, Teoriya veroyatn. i ee primen., 63:2 (2018), 260–283 | DOI | MR | Zbl

[33] Yakymiv A. L., “Dispersiya chisla tsiklov sluchainoi $A$-podstanovki”, Diskretnaya matematika, 32:3 (2020), 135–146 | DOI

[34] Yakymiv A. L., “Local limit theorem for the multiple power series distributions”, Mathematics, 8:11 (2020), 8 pp. | DOI

[35] Yakymiv A. L., “Momentnye kharakteristiki sluchainogo otobrazheniya s ogranicheniyami na razmery komponent”, Tr. MIAN, 316, MIAN, M., 2022, 376–389 | DOI

[36] Yakymiv A. L., “Random mappings with constraints on the cycle lengths”, J. Math. Sci. (N.Y.), 267:2 (2022), 228–233 | DOI | MR | Zbl