# 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.

• I doubt the preimage is that small. With relabeling, your random function is from $X^2$ to $X$, so I would expect most if not all preimage sets close to the size of $X$. To strengthen this intuition, pick a small subset $Y$ of $X^2$. Off of $Y$, the number of functions on the complement with less than full image is so much smaller than those with full image. Gerhard "Multinomial Distribution Has Small Tails" Paseman, 2019.01.07. – Gerhard Paseman Jan 7 at 17:19
• I'm agree that most of the set will be of same size of $X$. But it's not obvious (and chebychev inequality don't give any intuition on that result) that there is no set with small cardinality, and I don't understand the reasoning with $Y$... – Ievgeni Jan 7 at 17:27
• The reasoning with Y is that if the expected set size is small, then (by looking at all subsets of that size), there should be a lot of functions on the complement of Y with less than full image. I maintain there aren't enough if the size of Y is logarithmic with respect to the size of the whole space. Try a sum over all small subsets Y of all functions whose image off of Y is not full. Even with overcounting, the number should be exponentially small with respect to all functions when Y is quite small. Gerhard "A Big Use Of Smallness" Paseman, 2019.01.07. – Gerhard Paseman Jan 7 at 17:41
• I don't have time now for a long answer. You are considering the order statistics of the multinomial distribution. A precise answer to your question (in form of a limit theorem for the occupation of the smallest cell occupancy) is given in the book [1] (theorem 7 on p.112 (essentially confirming Gerhard Paseman's intuition)). [1] Kolchin,V.F. and Sevast'yanov,B.A. and Chistyakov, V.P., Random Allocations. V.H. WINSTON & SONS, Washington, D.C., 1978. – esg Jan 7 at 18:49
• I would use the following heuristic: as mentioned you are taking a random function from $M^2$ points to $M$ points. The number of times that the value $i$ is taken is close to normal with mean and variance both equal to $M$. These random variables are close to independent. So we'll approximate by $Z_i\sim \mathcal N(M,M)$, or $Z=M+(\sqrt M)N$ where $N$ is a standard normal and $Z_i$ is the number of times the value $i$ is taken. Now since there are $M^2$ random variables, you solve $\mathbb P(Z<L)=1/M^2$ for a good approximation of the typical smallest bin size. – Anthony Quas Jan 8 at 6:49

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 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 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.