3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 7 at 17:19
  • 1
    $\begingroup$ 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$... $\endgroup$ – Ievgeni Jan 7 at 17:27
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 7 at 17:41
  • $\begingroup$ 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. $\endgroup$ – esg Jan 7 at 18:49
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Jan 8 at 6:49
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm agree with every part of the reasoning except the last step with the crude bound. I don't understand how we could use it. Shouldn't we upper bound entropy instead lower bound it? $\endgroup$ – Ievgeni Jan 8 at 10:58
  • $\begingroup$ Thanks, you're right of course. $\endgroup$ – kodlu Jan 8 at 15:06
  • $\begingroup$ Okay I'm conviced. Thanks a lot! $\endgroup$ – Ievgeni Jan 8 at 17:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.