Moment Characteristics of a Random Mapping with Restrictions on Component Sizes

A. L. Yakymiv

Informatics and Automation, Branching Processes and Related Topics, Tome 316 (2022), pp. 376-389.

Résumé

Let $\mathfrak {S}_n$ be the semigroup of mappings of an $n$-element set $X$ into itself. For a set $D\subseteq \mathbb N$, denote by $\mathfrak {S}_n(D)$ the family of those mappings in $\mathfrak {S}_n$ whose component sizes belong to $D$. Suppose that a random mapping $\sigma _n=\sigma _n(D)$ is uniformly distributed on $\mathfrak {S}_n(D)$. We consider a class of sets $D\subseteq \mathbb N$ with positive densities in the set $\mathbb N$ of positive integers. Let $\zeta _n$ be the number of components of the random mapping $\sigma _n$. We find asymptotic formulas for the expectation and variance of the random variable $\zeta _n$ as $n\to \infty $.

Détail

Keywords: random mappings, total number of components of a random mapping.

Bibliographie

[1] Arratia R., Barbour A.D., Tavaré S., Logarithmic combinatorial structures: A probabilistic approach, Eur. Math. Soc., Zürich, 2003 | MR | Zbl

[2] Ju. V. Bolotnikov, V. N. Sačkov, and V. E. Tarakanov, “On some classes of random variables on cycles of permutations”, Math. USSR, Sb., 36:1 (1980), 87–99 | DOI | MR | Zbl | Zbl

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

[4] Harris B., “Probability distributions related to random mappings”, Ann. Math. Stat., 31:4 (1960), 1045–1062 | DOI | MR | Zbl

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

[6] Klimavičius J., Manstavičius E., “Turán–Kubilius' inequality on permutations”, Ann. Univ. Sci. Budapest. Sect. Comput., 48 (2018), 45–51 | MR | Zbl

[7] Kubilius J., Probabilistic methods in the theory of numbers, Transl. Math. Monogr., 11, Amer. Math. Soc., Providence, RI, 1964 | DOI | MR | Zbl

[8] Kubilius J., “Estimating the second central moment for any additive arithmetic functions”, Lith. Math. J., 23 (1983), 183–189 | DOI | MR

[9] Manstavičius E., “A Turán–Kubilius inequality on mappings of a finite set”, From arithmetic to zeta-functions: Number theory in memory of Wolfgang Schwarz, Springer, Cham, 2016, 295–307 | MR | Zbl

[10] Manstavičius E., Stepas V., “Variance of additive functions defined on random assemblies”, Lith. Math. J., 57:2 (2017), 222–235 | DOI | MR | Zbl

[11] A. I. Pavlov, “On two classes of permutations with number-theoretic conditions on the lengths of the cycles”, Math. Notes, 62:6 (1997), 739–746 | DOI | MR | Zbl

[12] Timashev A.N., Sluchainye komponenty v obobschennoi skheme razmescheniya, Izd. dom “Akademiya”, M., 2017

[13] Turán P., “Über einige Verallgemeinerungen eines Satzes von Hardy und Ramanujan”, J. London Math. Soc., 11:2 (1936), 125–133 | DOI | MR

[14] V. A. Vatutin and V. G. Mikhailov, “Limit theorems for the number of empty cells in an equiprobable scheme for group allocation of particles”, Theory Probab. Appl., 27:4 (1983), 734–743 | DOI | MR | Zbl

[15] A. L. Yakymiv, “On the distribution of the $m$th maximal cycle lengths of random $A$-permutations”, Discrete Math. Appl., 15:5 (2005), 527–546 | DOI | MR | Zbl

[16] A. L. Yakymiv, “Asymptotics with remainder term for moments of the total cycle number of random $A$-permutation”, Discrete Math. Appl., 31:1 (2021), 51–60 | DOI | MR | Zbl

[17] A. L. Yakymiv, “Size distribution of the largest component of a random $A$-mapping”, Discrete Math. Appl., 31:2 (2021), 145–153 | MR | Zbl

[18] A. L. Yakymiv, “Variance of the number of cycles of random $A$-permutation”, Discrete Math. Appl., 32:1 (2022), 59–68 | DOI | MR | MR

[19] Zubkov A.M., Ivchenko G.I., Medvedev Yu.I., “Korni proizvodyaschikh funktsii i summy tselochislennykh sluchainykh velichin”, Mat. vopr. kriptogr., 11:1 (2020), 27–46 | MR | Zbl