2
$\begingroup$

I have difficulties in understanding the notion of density for distribution.

Notion of density for distribution. A distribution $H$ over $\{0,1\}^n$ has density $\sigma$ if for every $x \in \{0,1\}^{n}$, $Pr[H=x] \leq \frac{1}{2^n\sigma}$.

The following is my desperate tries to understand the notion. if $H$ is uniform distribution over $\{0,1\}^n$ then for every $x \in \{0,1\}^n$, $Pr[H=x]=\frac{1}{2^n}$.

if a distribution $H$ has density $\sigma = 1$ then $P[H=x]\leq\frac{1}{2^n}$, so distribution $H$ is upper bounded by the uniform distribution.

if a distribution $H$ has density $\sigma = \frac{1}{2}$ then $P[H=x]\leq\frac{1}{2^{n-1}}$, so distribution $H$ is upper bounded by the uniform distribution over $\{0,1\}^{n-1}$.

if a a distribution $H$ has density $\sigma = \frac{1}{2^n}$ then $P[H=x]\leq 1$.

So density $\sigma$ might determine the part of distribution over $2^n$ where the actual "probabilistic weight" should be placed? However it's always upper bounded, therefore we can always say something about the upper bound?

As you see I don't have intuition behind this notion and I would appreciate any help.

|cite|improve this question
$\endgroup$
  • $\begingroup$ where did you get this definition from? $\endgroup$ – Sasho Nikolov Apr 16 '13 at 20:47
  • $\begingroup$ @SashoNikolov: from a textbook Computational Complexity. A Modern Approach, chapter 19, page 376, definition of Impagliazzo's Hardcore Lemma. $\endgroup$ – com Apr 17 '13 at 4:25
  • $\begingroup$ I think $\{0, 1\}^*$ is a typo and should be $\{0, 1\}^n$. When $\sigma$ is close to 1, this forces the distribution to be close to uniform. Keep in mind that a density $\sigma$ distribution has to be supported on at least $\sigma 2^n$ elements of $\{0, 1\}^n$. Also, see these lecture notes by Boaz: cs.princeton.edu/courses/archive/spr06/cos522/xor.pdf $\endgroup$ – Sasho Nikolov Apr 17 '13 at 5:09
  • $\begingroup$ @fog Please go over your text again and fix your spelling and grammar mistakes. I would do it for you, but in some case it is hard to guess what you intended to write. $\endgroup$ – Yuval Filmus Apr 17 '13 at 6:25
  • $\begingroup$ @SashoNikolov: thank you very much for the reference, It looks like it's a typo in my edition of the textbook. I've changed the question and added some thoughts, but in general the idea is still unclear $\endgroup$ – com Apr 17 '13 at 6:58
2
$\begingroup$

This notion seems to be a measure of uniformity. If $\sigma=1$ you get a uniform distribution on $\{0,1\}^n$ (since the sum over all strings of length $n$ is $1$), but for other $\sigma$s (e.g. $\sigma = 2^{-k}$) it's still distribution on $\{0,1\}^n$, not on $\{0,1\}^{n-k}$ or similar. Thus saying that a distribution on another (disjoint) set is an upper bound is absolutely wrong (but they are related, s.b.).

If for some $x$ the probability is greater than $\frac{1}{2^n}$ it has to be smaller for others. On the other hand for $\sigma=\frac{1}{2}$ at least half of the strings have nonzero probability since the sum of any number of elements $< 2^{n-1}$ is smaller than $1$. This holds for any $\sigma > 0$, i.e. $\sigma 2^n$ elements have nonzero probability.

Using this you can compare the distribution for $\sigma=2^{-k}$ to the distribution for $\sigma=1$ (i.e. uniform) on $\{0,1\}^{n-k}$. It's easy to see that the entropy of the distribution with $\sigma=2^{-k}$ on $\{0,1\}^n$ (let $H$ be a random variable with this distribution) is at least the entropy of the uniform distribution on $\{0,1\}^{n-k}$ (RV denoted by $U$) since for every injection $f: \{0,1\}^{n-k}\rightarrow \{0,1\}^n:$ $$\mathbb{P}(U=x)\geq \mathbb{P}(H=f(x)) \quad .$$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ for any $\sigma$ at least $\sigma$ fraction of the strings have nonzero probability in a density $\sigma$ distribution, otherwise the probabilities cannot sum to 1 $\endgroup$ – Sasho Nikolov Apr 17 '13 at 8:00
  • $\begingroup$ @SashoNikolov: Yes you're right, however I thought stating it for $\frac{1}{2}$ explicitly helps building up some intuition. Sorry btw that I answered basically with the content of your comment, but reading comments on mobile phones is somewhat inconvenient. If you add an answer I'm willing to delete mine. $\endgroup$ – frafl Apr 17 '13 at 9:02
  • $\begingroup$ nevermind, I like your current version of the answer. btw $n + \log_2 \sigma$ is also called the min-entropy of $H$, and as you pointed out is a lower bound on entropy $\endgroup$ – Sasho Nikolov Apr 17 '13 at 16:34
  • $\begingroup$ @SashoNikolov and frafl thank you for the great answers, very intuitive explanation! $\endgroup$ – com Apr 17 '13 at 18:43

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.