Expectation of the sum of the squares of the cardinal of an inverse function 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?
 A: $\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$".
