I sample a random one-to-one function $\pi:\{0\,;\,1\}^n\to\{0\,;\,1\}^n$. I define $f$ as:
$$\forall x\in\left[0\,;\,2^n-1\right]\cap\mathbb{N},f(x)=x\oplus\pi(x)$$
where $\oplus$ is the bitwise XOR.
I now define the following probability:
$$p=\frac{1}{2^{2\,n}}\,\sum\_{y=0}^{2^n-1}\left(\#f^{-1}(y)\right)^2\,.$$
My goal is to show that, in average, this probability decreases exponentially with $n$, but I can't manage to show this.


If $f$ is constant (which happens with negligible probability, since $\pi$ is chosen at random), then this probability is equal to 1. If it is one-to-one, then is it equal to $2^{-n}$. I think these are the extremal values that $p$ can take, but its distribution seems too complex to derive an closed form expression of it.


Intuitively, $\pi$ being chosen at random, there is no particular reason for which a given $y$ would be preferred by $f$. Hence, I think the distribution of $\#f^{-1}(y)$ has an expectation of 1 and a low variance. Though, I can't use this to upper-bound $p$, because of the square (furthermore, I don't have any formal proof of this statement).


If $\pi$ was chosen at random amongst all functions from $\{0\,;\,1\}^n$ to itself, I think I can reason about the fact that $f$ is uniformly random, since every $\pi(x)$ is. However, I am not sure this argument would work here, since we force $\pi$ to be one-to-one. Hence, this samples are not independant anymore, knowing $\pi(0)$ gives us an information on another value of $f$.


Is there a way to compute the distribution of $p$, or at least to upper-bound its expectation?



Expectation of the sum of the squares of the cardinal of an inverse function
$\newcommand{\p}{\oplus}$We have
\begin{equation}
 p=\frac{1}{2^{2n}}\,\sum\_{I\subseteq[n]}|f\_\pi^{-1}(I)|^2,
\end{equation}
where $[n]:=\{1,\dots,n\}$, $f\_\pi(J):=J\p\pi(J)$, $\p$ is the symmetric difference, $\pi$ is a random permutation of the powerset $2^{[n]}$ of the set $[n]$, and $|\cdot|$ is the cardinality. We are going to repeatedly use the fact that $(2^{[n]},\p)$ is a Boolean group.


Note that  

\begin{equation}
 |f\_\pi^{-1}(I)|=\sum\_{J\subseteq[n]}1(J\p\pi(J)=I)=\sum\_{J\subseteq[n]}1(\pi(J)=J\p I),
\end{equation}
and hence
\begin{align\*}
 |f\_\pi^{-1}(I)|^2=\sum\_{J,K\subseteq[n]}1(\pi(J)=J\p I,\pi(K)=K\p I)
\end{align\*}
and
\begin{align\*}
 E|f\_\pi^{-1}(I)|^2=s\_1+s\_2,
\end{align\*}
where
\begin{align\*}
 s\_1:=\sum\_{J\subseteq[n]}P(\pi(J)=J\p I)=\sum\_{J\subseteq[n]}\frac1{2^n}=1,
\end{align\*}
\begin{align\*}
 s\_2:=\sum\_{J,K\subseteq[n],\,J\ne K}p\_{I,J,K},
\end{align\*}
and
\begin{align\*}
 p\_{I,J,K}&:=P(\pi(J)=J\p I,\pi(K)=K\p I) \\
 &=\frac1{2^n}\frac1{2^n-1}\,1(J\p I\ne K\p I) \\ 
 &=\frac1{2^n}\frac1{2^n-1}\,1(J\ne K). 
\end{align\*}
So, $s\_2=1$ and hence $E|f\_\pi^{-1}(I)|^2=2$ for all $I\subseteq[n]$, so that
\begin{equation}
 Ep=\frac{1}{2^{2n}}\,\sum\_{I\subseteq[n]}2=\frac2{2^n}. 
\end{equation}


This confirms your conjecture "that, in average, this probability [that is, $p$] decreases exponentially with $n$".


