What is the limit probability an element of $x \in S$ belongs to $f^n(S)$, for $n \to \infty$?

Question

Let $S$ be a finite set of $|S|=n$ elements and $F$ be the set of all functions $f:S\rightarrow S$.

It's easy to demonstrate that the integer sequence $\{c_i\} = |{\rm Im}(f^i)|$:

1. is non increasing;
2. consists of a strictly decreasing sequence up to a certain $n'$, after which becomes constant;
3. $n' \leq n$ where $n'$, as defined above, is the maximum number for which $i \leq n' \implies \{c_i\} = |{\rm Im}(f^{i})|$ is strictly decreasing;

Quick demonstration:

$\forall i \geq 1, {\rm Im}(f^i) = {\rm Im}(f|_{{\rm Im}(f^{i-1})})$

while $f^0$ is identity and $f|_A$ means "$f$ restricted to $A$".
Obviously, either

$\left|\textrm{Im}(f|_{\textrm{Im}(f^{i-1})})\right| < |\textrm{Im}(f^{i-1})|$

or

$\left|\textrm{Im}(f|_{\textrm{Im}(f^{i-1})})\right| = |\textrm{Im}(f^{i-1})|$

which demonstrates 1. 2 derives from the fact $|\textrm{Im}(f|_{\textrm{Im}(f^{i-1})})| = |\textrm{Im}(f^{i-1})|$ means that $f|_{\textrm{Im}(f^{i-1})}$ is a permutation, and permutations are closed with respect of composition. 3 follows from observing the simple example in which $S = \{1, 2, \cdots, n', \cdots, n\}$ and $f(x) = x+1$, for $x \in \{1, \cdots, n-1\}$ and $f(n) = n'$. In this case, we have $\{c_i\} = n-i$ for $1 \leq i < n$ and $\{c_i\} = 1$ for $n \leq i$, and that shows that $n'$ can have any value between $0$ and $n$.

So, in summary, and roughly speaking, 'if you iterate a function over a finite set enough times, you end up with fixed-sized set'. My question is: when size $|S| = n$ of the initial set tends to infinity, and $f$ is randomly chosen from $F$, what is the expectation of the ratio of the sizes of the set resulting of such iterations and the initial set? Namely what is $\lim_{n \to \infty}E[|\textrm{Im}(f^n(S))|/n]$

There is an immediate application to this question which are the considerations about loss of entropy due to birthday paradox in hashes.

Answer 1

If $|S|=n$ and $c\in S$, then $c\in Im(f^n)$ iff there exists $1\leq k\leq n$ with $f^k(c)=c$.

Proof: If $f^k(c)=c$ and $n=k\cdot l+r$ with $0\leq r<k$, then $f^n(f^{k-r}(c))=f^{k-r}f^r(c)=f^k(c)=c$, thus $c\in Im(f^n)$. If $c\in Im(f^n)$ and $f^n(a)=c$, then $a,f(a),f^2(a),...,f^n(a)$ can't all be pairwise distinct, so there exists $n\geq l>0$ and $k\geq 0$ such that $f^lf^k(a)=f^k(a)$, but then $c=f^i(f^k(a))$ for some $0\leq i\leq l$, thus also $f^j(c)=f^k(a)$ for $j=l-i$, thus $f^{l}(c)=c$.

Now, for each $1\leq k\leq n$ there are $\frac{(n-1)!}{(n-k)!}n^{n-k}$ functions $f$ with $f^k(c)=c$ (where $k$ is minimal with this property).

Define $I_c(f)=1$ if $c\in Im(f^n)$ and $I_c(f)=0$ otherwise. Then $E I_c=n^{-n}\sum_{k=1}^n\frac{(n-1)!}{(n-k)!}n^{n-k}$ and $|Im(f^n)|=\sum_{c\in S}I_c(f)$.

Thus the expected value for $n$ is $n \cdot n^{-n}\sum_{k=1}^n\frac{(n-1)!}{(n-k)!}n^{n-k}=n^{-n}\sum_{k=1}^n\frac{n!}{(n-k)!}n^{n-k}=n^{-n}\sum_{k=0}^{n-1}\frac{n!}{k!}n^{k}\leq n^{-n}n!e^n$

and by Stirling's formula this is bounded by $O(\sqrt{n})$. Thus if you devide the average by $n$ as in the OP, the limit will be $0$.