Diskretnaya Matematika General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Diskr. Mat., 2017, Volume 29, Issue 1, Pages 136–155 (Mi dm1411) Limit theorems for the logarithm of the order of a random $A$-mapping

A. L. Yakymiv

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow

Abstract: Let $\mathfrak S_n$ be a semigroup of mappings of a set $X$ with $n$ elements into itself, $A$ be some fixed subset of the set $N$ of natural numbers, and $V_n(A)$ be a set of mappings from $\mathfrak S_n$, with lengths of cycles belonging to $A$. The mappings from $V_n(A)$ are called $A$-mappings. We suppose that the set $A$ has an asymptotic density $\varrho>0$, and that $|k\colon k\leq n, k\in A, m-k\in A|/n\to\varrho^2$ as $n\to\infty$ uniformly over $m\in[n,Cn]$ for each constant $C>1$. A number $M(\alpha)$ of different elements in a set $\{\alpha, \alpha^2, \alpha^3,…\}$ is called an order of mapping $\alpha\in\mathfrak S_n$. Consider a random mapping $\sigma=\sigma_n(A)$ having uniform distribution on $V_n(A)$. In the present paper it is shown that random variable $\ln M(\sigma_n(A))$ is asymptotically normal with mean $l(n)=\sum_{k\in A(\sqrt{n})}\ln(k)/{k}$ and variance $\varrho\ln^3(n)/24$, where $A(t)=\{k\colon k\in A, k\leq t\}, t>0$. For the case $A=N$ this result was proved by B. Harris in 1973.

Keywords: random $A$-mappings, order of $A$-mapping, cyclic points, contours, trees, height of random\linebreak$A$-mapping, random $A$-permutations.

 Funding Agency Grant Number Russian Foundation for Basic Research 14-01-00318_а This study was supported by the Russian Foundation for Basic Research, grant 14-01-00318.

DOI: https://doi.org/10.4213/dm1411  Full text: PDF file (618 kB) References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2017, 27:5, 325–338 Bibliographic databases:    UDC: 519.212.2
Revised: 21.11.2016

Citation: A. L. Yakymiv, “Limit theorems for the logarithm of the order of a random $A$-mapping”, Diskr. Mat., 29:1 (2017), 136–155; Discrete Math. Appl., 27:5 (2017), 325–338 Citation in format AMSBIB
\Bibitem{Yak17} \by A.~L.~Yakymiv \paper Limit theorems for the logarithm of the order of a random $A$-mapping \jour Diskr. Mat. \yr 2017 \vol 29 \issue 1 \pages 136--155 \mathnet{http://mi.mathnet.ru/dm1411} \crossref{https://doi.org/10.4213/dm1411} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3771057} \elib{https://elibrary.ru/item.asp?id=28405141} \transl \jour Discrete Math. Appl. \yr 2017 \vol 27 \issue 5 \pages 325--338 \crossref{https://doi.org/10.1515/dma-2017-0034} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000414954500008} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85031789597} 

• http://mi.mathnet.ru/eng/dm1411
• https://doi.org/10.4213/dm1411
• http://mi.mathnet.ru/eng/dm/v29/i1/p136

 SHARE:      Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. L. Yakymiv, “On the order of random permutation with cycle weights”, Theory Probab. Appl., 63:2 (2018), 209–226      2. A. L. Yakymiv, “Size distribution of the largest component of a random $A$-mapping”, Discrete Math. Appl., 31:2 (2021), 145–153      • Number of views: This page: 330 Full text: 27 References: 35 First page: 23 Contact us: math-net2021_11 [at] mi-ras ru Terms of Use Registration to the website Logotypes © Steklov Mathematical Institute RAS, 2021