# Min-entropy of a random pre-image of a random function

I am facing hard time understanding min-entropy.

Fix $v \in \{0,1\}^{n/2}$, let $F\colon \{0,1\}^n \to \{0,1\}^{n/2}$ be chosen randomly, and let $X_v$ be a string chosen uniformly at random among $F^{(-1)}(v)$ (or a special string $\epsilon$ if $F^{(-1)}(v) = \emptyset$). We want to compute the probability that $H_\infty(X_v) \leq n/4$ (over the choice of $F$), where $H_\infty(X_v)=-\log(\max_{x}\{\Pr[X_v=x]\})$ is the min-entropy of $X_v$.

It's not obvious what approach is needed to solve such things! It would be helpful if one could explain where to start...

• @Fayez Please verify that my edit still reflects your question. – Yuval Filmus Apr 2 '14 at 15:46
• The question still needs a CS connection (in the post itself) and your own thoughts/attempts. – Raphael Apr 2 '14 at 16:35
• This is a problem dump, not a question. Where did this problem come from? What is the context and motivation? What do you think? What have you tried, and where did you get stuck? Can you pose a specific question about your approach to this problem? – D.W. Apr 3 '14 at 23:13
• @D.W. it have a motivation in CS and it's not totally have no context !! I prefer to keep the motivation out of the subject because this question is a fraction of other question which I want to think about it alone ! but this I didn't have any clue how to the approach to solve it so I ask for help !! thank you all for your help and useful edits and comments ! – Fayez Abdlrazaq Deab Apr 6 '14 at 5:51

Since $X_v$ is a random variable which is uniformly distributed over its support $F^{-1}(v)$, its min-entropy depends only on the size of the support (and it equals the entropy). The min-entropy is at most $n/4$ if and only if $|F^{-1}(v)| \leq 2^{n/4}$. Now $|F^{-1}(v)|$ is binomially distributed $\mathrm{Bin}(2^n,2^{-n/2})$, since for each string $x \in \{0,1\}^n$, the probability that $F(x) = v$ is $2^{-n/2}$. Therefore you are interested in bounding $$\Pr[\mathrm{Bin}(2^n,2^{-n/2}) \leq 2^{n/4}].$$ You can obtain a good bound on this event, which is rather unlikely, using Chernoff's bound or Hoeffding's bound. Let us know if you encounter any difficulties.