Size distribution of the largest component of a random $A$-mapping

A. L. Yakymiv

Diskretnaya Matematika, Tome 31 (2019) no. 4, pp. 116-127.

Résumé

Let $\mathfrak S_n$ be a semigroup of all mappings from the $n$-element set $X$ into itself. We consider a set $\mathfrak S_n(A)$ of mappings from $\mathfrak S_n$ such that their contour sizes belong to the set $A\subseteq N$. These mappings are called $A$-mappings. Let a random mapping $\tau_n$ have a distribution on $\mathfrak S_n(A)$ such that each connected component with volume $i\in N$ have weight $\vartheta_i\geq 0$. Let $D$ be a subset of $N$. It is assumed that $\vartheta_i\to\vartheta>0$ for $i\in D$ and $\vartheta_i\to0$ for $i\in N\setminus D$ as $i\to\infty$. Let $\mu(n)$ be the maximal volume of components of the random mapping $\tau_n$ . We suppose that sets $A$ and $D$ have asymptotic densities $\varrho>0$ and $\rho>0$ in $N$ respectively. It is shown that the random variables $\mu(n)/n$ converge weakly to random variable $\nu$ as $n\to\infty$. The distribution of $\nu$ coincides with the limit distribution of the corresponding characteristic in the Ewens sampling formula for random permutation with the parameter $\rho\varrho\vartheta/2$.

Détail

Keywords: Random $A$-mapping with component weights, the volume of the largest component.

Bibliographie

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

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

[3] Goncharov V. L., “On the field of combinatory analysis”, Am. Math. Soc. Transl., 19, 1–46 | MR | Zbl

[4] Donnelly P. J., Ewens W. J., Padmadisastra S., “Functionals of random mappings: exact and asymptotic results”, Adv. Appl. Probab., 23:3 (1991), 437–455 | DOI | MR | Zbl

[5] Ercolani N. M., Ueltschi D., Cycle structure of random permutations with cycle weights, 2011, arXiv: 1102.4796v1 | MR

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

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

[8] Ivchenko G. I., Medvedev Yu. I., “The method of V. L. Goncharov and its development in the analysis of various models of random permutations”, Theory Probab. Appl., 47:3 (2003), 518–526 | DOI | DOI | MR | Zbl

[9] Ivchenko G.I., Medvedev Yu.I., “Statistika parametricheskoi modeli sluchainykh podstanovok”, Trudy po diskretnoi matematike, 8 (2004), 116–127

[10] Ivchenko G.I., Medvedev Yu.I., “Random combinatorial objects”, Dokl. Math., 69:3 (2004), 344–347 | MR | Zbl

[11] Ivchenko G.I., Medvedev Yu.I., “Random permutations: a general parametric model”, Discrete Math. Appl., 16:5 (2006), 471–478 | DOI | DOI | MR | Zbl

[12] Ivchenko G.I., Medvedev Yu.I., “Sluchainye kombinatornye ob'ekty v obschei parametricheskoi modeli”, Trudy po diskretnoi matematike, 12 (2007), 73–86

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

[14] Kolchin, V. F., Random Mappings, Optimization Software, New York, 1986 | MR | Zbl

[15] Kolchin V. F., Random Graphs, Cambridge Univ. Press, Cambridge, 1999 | MR | Zbl

[16] Pavlov A.I., “On the number of substitutions with cycle lengths from a given set”, Discrete Math. Appl., 2 (1992), 445–459 | DOI | MR

[17] Pavlov Yu.L., Random forests, VSP, Utrecht, 2000, 122 pp. | MR

[18] Sachkov V.N., “Mappings of a finite set with limitations on contours and height”, Theory Probab. Appl., 17 (1972), 640–656 | DOI | MR | Zbl

[19] “Random mappings with bounded height”, Theory Probab. Appl., 18:1 (1973), 120–130 | DOI | Zbl

[20] Sachkov V.N., Kombinatornye metody diskretnoi matematiki, Nauka, Moskva, 1977

[21] Sachkov V.N., Probabilistic Methods in Combinatorial Analysis, Cambridge Univ. Press, Cambridge, 1997 | MR | Zbl

[22] Sachkov V.N., Vvedenie v kombinatornye metody diskretnoi matematiki, izd-vo MTsNMO, Moskva, 2004, 424 pp.

[23] Seneta E., Regularly Varying Functions, Springer-Verlag, Berlin–Heidelberg–New York, 1976 | MR | Zbl

[24] Timashev A.N., Asimptoticheskie razlozheniya v veroyatnostnoi kombinatorike, Izd-vo “TVP”, Moskva, 2011

[25] Timashev A.N., Sluchainye komponenty v obobschennoi skheme razmescheniya, Akademiya, Moskva, 2017

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

[27] Yakimiv A.L., Probabilistic applications of Tauberian theorems, Modern Probability and Statistics, VSP, Leiden, Boston, 2005, 225 pp. | MR | Zbl

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

[29] Yakymiv A.L., “On the Number of $A$-Mappings”, Math. Notes, 86:1 (2009), 132–139 | DOI | DOI | MR | Zbl

[30] Yakymiv A.L., “A limit theorem for the logarithm of the order of a random $A$-permutation”, Discrete Math. Appl., 20:3 (2010), 247–275 | DOI | DOI | MR | Zbl

[31] Yakymiv A.L., “On the number of cyclic points of random $A$-mapping”, Discrete Math. Appl., 23:5 (2013), 503–515 | DOI | MR | Zbl

[32] Yakymiv A.L., “On a number of components in a random $A$-mapping”, Theory Probab. Appl., 59:1 (2015), 114–127 | DOI | DOI | MR | MR | Zbl

[33] Yakymiv A.L., “On the Number of Components of Fixed Size in a Random $A$-Mapping”, Math. Notes, 97:3 (2015), 468–475 | DOI | MR | MR | Zbl

[34] Yakymiv A.L., “Limit theorems for the logarithm of the order of a random $A$-mapping”, Discrete Math. Appl., 27:5 (2017), 325–338 | DOI | DOI | MR | Zbl

[35] Yakymiv A.L., “On the order of random permutation with cycle weights”, Theory Probab. Appl., 63:2 (2018), 209–226 | DOI | DOI | MR | Zbl