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

  • $\begingroup$ @Fayez Please verify that my edit still reflects your question. $\endgroup$ – Yuval Filmus Apr 2 '14 at 15:46
  • 2
    $\begingroup$ The question still needs a CS connection (in the post itself) and your own thoughts/attempts. $\endgroup$ – Raphael Apr 2 '14 at 16:35
  • $\begingroup$ 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? $\endgroup$ – D.W. Apr 3 '14 at 23:13
  • $\begingroup$ @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 ! $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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