<p>Take any distribution $D$ on $\{0,1\}^n$. Sample $k(n)$ points $x_1, \cdots, x_{k(n)}$ independently from $D$ and let $\tilde D$ be the uniform distribution that gives a random $x_i$. Then, if $k(n)$ is super-polynomially large e.g. $k=n^{\log n}$, you cannot distinguish $D$ and $\tilde D$ using only $\mathrm{poly}(n)$ samples. Hence $D$ is computationally indistinguishable from a distribution $\tilde D$ with entropy $\mathrm{poly}\log(n)$.</p>

CC BY-SA 3.0
2015-07-28T18:49:04.420Z
2015-07-28T18:49:04.420Z
Thomas Steinke
<p>From <a href="http://www.cs.tau.ac.il/~iftachh/papers/AccessibleEntropy/AccessibleEntropy_full.pdf" rel="nofollow">here</a>:</p>

<blockquote>
  <p>The notion of pseudoentropy is only useful, however, as a lower bound on the computational entropy in a distribution. Indeed, it can be shown that every distribution on $\{0,1\}^n$ is computationally indistinguishable from a distribution of entropy at most $poly (\log n)$.</p>
</blockquote>

<p>How is that any distribution on $n$-cube can be computationally indistinguishable from one with entropy at most $poly(\log n)$?</p>

<pseudorandomness>
Upper bound on the pseudoentropy of any distribution
user34954
# Upper bound on the pseudoentropy of any distribution

(Asked by: username_0 on 2015-07-28)

From [here](http://www.cs.tau.ac.il/~iftachh/papers/AccessibleEntropy/AccessibleEntropy_full.pdf):

> The notion of pseudoentropy is only useful, however, as a lower bound on the computational entropy in a distribution. Indeed, it can be shown that every distribution on $\{0,1\}^n$ is computationally indistinguishable from a distribution of entropy at most $poly (\log n)$.

How is that any distribution on $n$-cube can be computationally indistinguishable from one with entropy at most $poly(\log n)$?

**Tags:** pseudorandomness


---

## 1 answers

### Answer by username_1 on 2015-07-28. Score: 2

Take any distribution $D$ on $\{0,1\}^n$. Sample $k(n)$ points $x\_1, \cdots, x\_{k(n)}$ independently from $D$ and let $\tilde D$ be the uniform distribution that gives a random $x\_i$. Then, if $k(n)$ is super-polynomially large e.g. $k=n^{\log n}$, you cannot distinguish $D$ and $\tilde D$ using only $\mathrm{poly}(n)$ samples. Hence $D$ is computationally indistinguishable from a distribution $\tilde D$ with entropy $\mathrm{poly}\log(n)$.


---

