Diskretnaya Matematika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 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

 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