The notion of density of distribution

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.

• where did you get this definition from? – Sasho Nikolov Apr 16 '13 at 20:47
• @SashoNikolov: from a textbook Computational Complexity. A Modern Approach, chapter 19, page 376, definition of Impagliazzo's Hardcore Lemma. – com Apr 17 '13 at 4:25
• 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 – Sasho Nikolov Apr 17 '13 at 5:09
• @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. – Yuval Filmus Apr 17 '13 at 6:25
• @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 – com Apr 17 '13 at 6:58

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 .$$
• 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 – Sasho Nikolov Apr 17 '13 at 8:00
• @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. – frafl Apr 17 '13 at 9:02
• 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 – Sasho Nikolov Apr 17 '13 at 16:34