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.

Improve this question
$\endgroup$
6
  • $\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
    Commented Jan 7, 2019 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
    Commented Jan 7, 2019 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
    Commented Jan 7, 2019 at 17:41
  • 1
    $\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
    Commented Jan 7, 2019 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
    Commented Jan 8, 2019 at 6:49

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Jan 8, 2019 at 10:58
  • $\begingroup$ Thanks, you're right of course. $\endgroup$
    – kodlu
    Commented Jan 8, 2019 at 15:06
  • $\begingroup$ Okay I'm conviced. Thanks a lot! $\endgroup$
    – Ievgeni
    Commented Jan 8, 2019 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .