|
This article is cited in 3 scientific papers (total in 3 papers)
Random permutations with prime lengths of cycles
A. N. Timashev Institute of Cryptography, Communications and Informatics, Academy of Federal Security Service of Russian Federation, Moscow
Abstract:
A set of $n$th order permutations with prime lengths of cycles is considered. An asymptotic estimate for the number of all such permutations is obtained as $n\to\infty.$ Given a uniform distribution on the set of such permutations of order $n$, a local limit theorem is proved, evaluating the distribution of the number of cycles $\nu_n$ in a permutation selected at random. This theorem implies, in particular, that the random variable $\nu_n$ is asymptotically normal with parameters ($\log\log n$, $\log\log n$) as $n\to\infty$. It is shown that the random variable $\nu_n(p)$, the number of cycles of a fixed length $p$ in such a permutation ($p$ is a prime number), has in the limit a Poisson distribution with parameter ${1}/{p}.$ Assuming that a permutation of order $n$ is selected in accordance with the uniform distribution from the set of all such permutations with prime cycle lengths, each of which has exactly $N$ cycles $(1\le N\le[{n}/{2}]),$ limit theorems are proved, evaluating the distribution of the random variable $\mu_p(n, N),$ the number of cycles of prime length $p$ in this permutation. The results mentioned are established by means of the asymptotic law for the distribution of prime numbers and the saddle-point method as well as the generalized allocation scheme.
Received: 04.03.2014 Revised: 26.05.2015
Citation:
A. N. Timashev, “Random permutations with prime lengths of cycles”, Teor. Veroyatnost. i Primenen., 61:2 (2016), 365–377; Theory Probab. Appl., 61:2 (2017), 309–320
Linking options:
https://www.mathnet.ru/eng/tvp5060https://doi.org/10.4213/tvp5060 https://www.mathnet.ru/eng/tvp/v61/i2/p365
|
Statistics & downloads: |
Abstract page: | 411 | Full-text PDF : | 64 | References: | 56 | First page: | 8 |
|