Expected size of the smallest preimage set Let $f$ a function from $\{0, 1 \}^{2n}$ to $\{0, 1 \}^{n}$ uniformly picked at random. I would like to have an estimation of the expected size of the smallest premiage set of $f$, more formally $\mathbb{E}_{f \leftarrow \left(2^n\right)^{2^{2n}}} \left(\min \left(|f^{<-1>}\left( i\right) |\right)_{i \in \{ 0,1\}^{n}} \right)$.
Intuitively I think this set is very small (in $O\left(n\right)$), but I can't prove anything so tight.
 A: This is not a full answer but easy to obtain. See the  reference by @esg in the comments for the full answer.
I will give a very loose upperbound to this probability, which still tends to zero quite fast with increasing $N.$ You have $N^2$ balls thrown into $N$ bins where $N=2^n.$ So the probability that the lightest loaded bin has less than $N^\theta$ balls can be upper bounded (using the union bound in the first step)
$$
\mathbb{P}[Min<N^\theta]\leq 
N \sum_{0\leq k < N^\theta} \mathbb{P}[X_1=k]=
N \sum_{0\leq k < N^\theta} \binom{N^2}{k} 2^{-N^2}
$$
where $X_1$ is the number of balls in the first bin. The binomial coefficients 
$$\binom{N^2}{k}$$ are superincreasing in $k$ so upperbounding by the largest coefficient gives
$$
\mathbb{P}[Min<N^\theta]\leq N^{1+\theta} \binom{N^2}{N^\theta} 2^{-N^2}\sim
 N^{1+\theta} 2^{-N^2(1-\mathbb{H}(N^{\theta-2}))}.
$$
by the entropy approximation to the binomial coefficient.
Using the crude bound $\mathbb{H}(p)< 2\sqrt{p(1-p)}$ we still get a bound that goes to zero exponentially fast.
