# Upper bound on the pseudoentropy of any distribution

From here:

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)$?

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