5
$\begingroup$

For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ associate a sequence $\text{seq}(f))$ defined recursively by

  • $\text{seq}(f)_1 = f(1)$, and
  • $\text{seq}(f)_{k+1} = f(\text{seq}(f)_k)$ for all $k\in\mathbb{N}$.

Eventually $\text{seq}(f)$ will be periodic, and with $\text{per}(f)$ we denote the length of the period of $\text{seq}(f)$. By $E_n$ we denote the expected value of $\text{per}(f)$ for any $f\in\text{Fun}(n)$. Explicitly, we have $$E_n = \frac{1}{n^n}\sum_{f\in\text{Fun}(n)}\text{per}(f).$$

Questions. Do we have $\lim\sup_{n\to\infty} E_n/n > 0$, and if yes, what is that value? If no, do we have $\lim\sup_{n\to\infty} E_n/\log(n) > 0$?

$\endgroup$
9
$\begingroup$

The standard references here include An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet.

The first significant reference is probably "Probability distributions related to random mappings", Bernard Harris, Ann. Math. Statist. 31 (1960), 1045-1062, linked to in another answer. A summary is also given in the paper "Random Mapping Statistics" by Odlyzko and Flajolet available here

The use of bivariate generating functions and saddle point methods gives the estimates for cycle length (a pre-period is followed by a cycle giving a so-called rho ($\rho$) as in Pollard's rho method). If the function has a fixed point that just becomes a cycle length of 1.

In summary the expected cycle length over your ensemble of functions is $\sqrt{\pi n/8}.$ So $$ \lim_{n\rightarrow \infty} \frac{E_n}{\sqrt{n}}=constant. $$

For whatever it's worth the expected rho-length, tail-length (initial pre-period segment of a rho) are also $O(\sqrt{n}).$ The expected component size you end up in, if you start at a random point, is $2n/3.$

$\endgroup$
0
5
$\begingroup$

A standard reference for all sorts of average statistics of random maps of $\{1,\ldots,,N\}$ is Probability distributions related to random mappings, Bernard Harris, Ann. Math. Statist. 31 (1960), 1045-1062.

$\endgroup$
1
  • $\begingroup$ Thanks for that, I didn't have the full reference to this paper $\endgroup$ – kodlu Apr 5 at 1:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.