Expected number of periodic points of a random map $f\colon V\to V$ on a finite set $V$.

Question

Let $V$ be a finite set (say $|V|=n$) and let $F(V)$ be the set of all maps $f\colon V\to V$. Note that $|F(V)|=n^{n}$. A directed graph on $V$ is a subset $E\subset V\times V$ (there is an edge from $v$ to $v'$ if and only if $(v,v')\in E$. Given $E\subset V\times V$, a (directed) $E$-cycle of length $k$ is a sequence $v_{1},v_{2},\ldots,v_{k}$ such that $v_{i}\neq v_{j}$ whenever $i\neq j$ and $$(v_{1},v_{2})\in E, \ (v_{2},v_{3})\in E, \ \ldots, \ (v_{k-1},v_{k})\in E, \ (v_{k},v_{1})\in E.$$ Let $G_{1}(V)\subset P(V\times V)$ be the set of directed graphs $E$ on $V$ with outdegree $$\text{Out}_{E}(v):=|\{v'\in V:(v,v')\in E\}|=1,\qquad\forall v\in V.$$ Given $f\in F(V)$, define the graph $$E_{f}:=\{(v,f(v)):v\in V\}.$$ We call this the graph associated to $f$. Then $f\mapsto E_{f}$ is clearly a bijection between $F(V)$ and $G_{1}(V)$. We can endow $G_{1}(V)$ with the uniform probability measure $\mathbb{P}\colon P(G_{1}(V))\to[0,1]$, i.e. $\mathbb{P}\{E_{f}\}=n^{-n}$ for all $f\in F(V)$. For $1\leq k\leq n$ consider the random variable $$\gamma_{k}(E):=\text{number of $E$-cycles of length $k$}.$$ Recall that $v\in V$ is an $k$-periodic point ($k=1,2,3,\ldots$) for $f$ if and only if $f^{k}(v)=v$. Note that the number of $k$-periodic points for $f$ is $k\gamma_{k}(E_{f})$. So the number of periodic points of $f$ points is $$\gamma:=\sum_{k=1}^{n}k\gamma_{k}.$$ My question is: What is the expectation $$\mathbb{E}(\gamma)=\int_{G_{1}(V)}\gamma \ \text{d}\mathbb{P}$$ and what is the asymptotic behaviour of $\mathbb{E}(\gamma)$ w.r.t. $n$?

Answer 1

Given any ordered $k$-tuple $(v_1, \ldots, v_k)$ of distinct vertices, the probability that it forms a $k$-cycle, i.e. that $f(v_i) = v_{i+1}$ for $i \le k-1$ and $f(v_k) = v_1$, is $n^{-k}$. There are $n!/(n-k)!$ such $k$-tuples, but there are $k$ of them for each $k$-cycle, so by linearity of expectation $$\mathbb E(\gamma_k) = \frac{n!}{(n-k)! k} n^{-k}$$ and $$ \mathbb E(\gamma) = \sum_{k=1}^n \frac{n!}{(n-k)!} n^{-k} = {\mbox{$_2$F$_0$}(1,1-n;\,\ ;\,-{n}^{-1})} $$ This is $a(n)/n^{n-1}$ where $a(n)$ is OEIS sequence A001865. According to that, $a(n) \sim \sqrt{\pi n/2}\; n^{n-1}$, so $\mathbb E(\gamma) \sim \sqrt{\pi n/2}$ as $n \to \infty$.