6
$\begingroup$

Let $m$ be a positive integer. Let $S$ be the set of non-negative integers $x$ less than $m$, with $|S|=m$. Let $X_0$ be the discrete uniform distribution over $S$, with $P(x)=\begin{cases} 1/m & \text{if } x\in S \\ 0 & \text{if } x\not\in S \end{cases}$

Let $F$ be any of the $m^m$ discrete functions from $S$ to $S$.

For that particular $F$, let $X_{i+1}=F(X_i)$ be the discrete distribution of the output of $F$ for input distribution $X_i$ (or equivalently the discrete distribution of $F^i$ for input distribution $X_0$); and let $H_i=H(X_i)$ be the entropy of $X_i$.

Question: How is the distribution of $H_i$ when $F$ is a uniformly random discrete function from $S$ to $S$? In particular, can we find a little-$\mathcal o$ expression of its mean (perhaps variance or standard deviation, skewness..) when $m\to\infty$?


An heuristic approximation is proposed here, with $n=\log_2(m)$, in a cryptographic context.

It holds that $H_0=\log_2(m)$; and $\forall i\in\mathbb N, H_{m-1}\le H_{i+1}\le H_i\le\log_2(m)$.

$H_i$ for an individual $F$ depends only on $i$ and the structure of the Functional Graph of $F$, irrespective of its labeling. Here a graph showing a random $F$ (a truncated hash with $m=2^{10}$).

Functional Graph of a random function


Another example yielding a maximally high $i$ before $H_i$ no longer decreases is with $$F(x)=\begin{cases} x-1 & \text{if } 1\le x<m \\ 0 & \text{if } 0\le x\le1\text{ and }x<m \end{cases}$$ we have $$F^i(x)=\begin{cases} x-i & \text{if } i\le x<m \\ 0 & \text{if } 0\le x\le i\text{ and }x<m \end{cases}$$ and it comes $$H_i=\begin{cases} \log_2(m) & \text{if } i=0 \\ \log_2(m)-{i+1\over m}\log_2(1+i) & \text{if } 0\le i\le m-1 \\ 0 & \text{if } i\ge m-1 \end{cases}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.