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.



Expected size of the smallest preimage set
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](https://mathoverflow.net/questions/236508/are-there-good-bounds-on-binomial-coefficients/236511#236511) 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.


