Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation Let $P$ be a random permutation of $n&gt;1$ bits. Let $F$ be the function on the same domain $\{0,1\}^n$, defined by $F(x)=P(x)\oplus x$. When $P$ is a block cipher with key a message block, that's the Davies-Meyer construction of a one-way compression function, a variant of which being used in MD5, SHA-1, and SHA-2.

Let $H_F$ be the entropy (in bits) of the source $F(x)$ where $x$ is a vector of $n$ random unbiased independent bits. That is
$$\begin{align*}
H_F&amp;=\sum_{y\in F(\{0,1\}^n)}-\Pr(F(x)=y)\cdot\log_2\big(\Pr(F(x)=y)\big)\\
\\
&amp; = n-{1\over2^n}\cdot\sum_{y\in F(\{0,1\}^n)}\big(\#{\{x, F(x)=y)\}}\big)\cdot\log_2\big(\#{\{x, F(x)=y)\}}\big)
\\
&amp; = n-{1\over2^n}\cdot\sum_{2\le\,j\,\le2^n}\big(\#{\{y,(\#\{x:F(x)=y\})=j\}}\big)\cdot j\cdot\log_2(j)
\end{align*}$$
Note: $\#{\{x, F(x)=y)\}}$ of the 2nd equation is the number of preimages of vector $y$; and $\#{\{y,(\#\{x:F(x)=y\})=j\}}$ of the 3rd is the number of vectors with exactly $j$ preimages.

$H_F$ can be from $0$ (when $P$ happens to be XOR with some constant) to $n$ bits (when $F$ happens to be a permutation, e.g. for $P:$ $00\to00$, $01\to10$, $10\to11$, $11\to01$ ).

Let $H(n)$ be the expected value of $H_F$; that is, the average of $H_F$ over all $(2^n)!$ permutations $P$. A plausible conjecture is that
$$\lim_{n\to\infty}{H(n)\over n}=1$$
How to prove this, and what's a first order approximation of $n-H(n)$ for large $n$?



If $F$ was a random function, we'd have $n-H(n)\approx0.8272\dots$ starting with moderate $n$ according to my analysis there. But I fail to rigorously derive that for the much narrower class of $F$ in the question.
All functions (including permutations) mapping a finite field $\mathbb{F}_q$ to itself can be uniquely represented by polynomials (via Lagrange Interpolation, possibly followed by reduction modulo $x^{q}-x.$ When $q=2^n,$ the linear permutations $F(x)=x+a,$ for $a\neq 0,$are exactly the type of polynomial that give zero entropy in your formulation since $F(x)+x=a$ a constant. 

Focusing only on $q=2^n$ due to crypto applications, we don't know explicit representation of many other permutations but some include certain monomials $F(x)=x^{e}$ with special conditions on exponent $e,$ as well as families such as Dickson's polynomials, which don't have an $x$ term in their polynomial and won't suffer the weakness of zero entropy for $F(x)+x$. As for computing what fraction of overall permutation polynomials have an $x$ in their polynomial expression, it's likely to be a difficult problem.

Edit: The below is redundant, due to your comment, the above is still relevant but I can take it to a comment if requested, it's a bit long.

If we model the map $F(x)=P(x)+x$ by a random mapping instead of a random permutation from $A=\{0,1\}^n$ to itself, then the number of points $y$ in $A$ that have no preimages, i.e., there is no $x\in A$ with $f(x)=y,$ is on average equal to $e^{-1}\#A=\frac{2^n}{e}.$

This would mean that the expected size of the range of $F$ is $$\mathbb{E}[F(A)]=(1-e^{-1}) 2^n\approx 0.6321 \cdot 2^n$$ yielding $$H(n)\approx n+\log_2(0.6321)= n-0.66172,$$
so as you predicted the  $\lim_{n\rightarrow \infty}H(n)/n=1.$

References for this type of argument include Sedgewick and Flajolet's book An Introduction to the Analysis of Algorithms, and the paper "Random Mapping Statistics" by Flajolet and Odlyzko in Eurocrypt'89, but a very readable account is in Chapter 5 of Riordan's classic book An Introduction to Combinatorial Analysis, from 1958.