# Generating $k$ random bits from a pdf with entropy $H(p) = k$

All the sources online say that, intuitively, a distribution with entropy $$k$$ has $$k$$ bits of pure randomness in it.

So can we formalize this as follows? Suppose I can only sample from my distribution, is there an algorithm or procedure to generate a uniform $$k$$ bit binary string?

• Google “randomness extractor”. Note that you need to bound the min-entropy of the source distribution, it is not possible to do this with only a bound on the Shannon entropy. Commented Nov 28, 2020 at 8:46
• @EmilJerabek can you do it with Shannon entropy if you don't care about efficiency? Commented Nov 28, 2020 at 20:09
• I think there’s known examples where one cannot extract from Shannon entropy (in Vadhan’s survey): a source on $n$ bits that is all-zero with .99 probability and otherwise uniform has $\Omega(n)$ Shannon entropy, but even seeded extraction with logarithmic random bits is not possible. The reason is that the output of any such extractor on this source is concentrated on a polynomial number of strings, but no such output distribution can be close to uniform on $\Omega(n)$ bits. Commented Nov 28, 2020 at 22:01
• Ah, Yuval Peres's answer is what I was thinking of. @J.G. Do you know how this answer squares with the example you mentioned? Seems like it's something about order of quantifiers, but I'm not entirely sure. Commented Dec 2, 2020 at 19:02
• @JoshuaGrochow I think the answer shows that Shannon entropy is the right measure given a "large" number of i.i.d. samples. I thought we get just one sample from a source (+ some uniform bits on the side, i.e. seeded extractors) or some constant number of i.i.d. samples (i.e. two-source extractors)--these need min-entropy guarantees. In the example, you expect to get a nonzero string every 100 independent samples on average (where the number 100 crucially depends on the source itself) which is (almost) uniform on $n$ bits, so you get $\Omega(n)$ uniform bits per sample asymptotically I think. Commented Dec 2, 2020 at 22:31

The relevance of Shannon entropy is to repeated sampling: Given $$n$$ independent samples from a source with binary Shannon Entropy $$k$$, you can extract $$nk(1+o(1)$$ i.i.d. uniform bits as $$n$$ tends to infinity with probability tending to 1. This follows e.g. from the Keane-Smorodinsky [1] finitary isomorphism theorem. See also [2]-[5] below.

[1] M. Keane and M. Smorodinsky (1979), Bernoulli schemes of the same entropy are finitarily isomorphic. Annals of Math. 109, 397–406.

[2] P. Elias (1972), The efficient construction of an unbiased random sequence. Ann. Math. Statist. 43, 865–870.

[3] D. E. Knuth and A. C. Yao (1976), The complexity of nonuniform random number generation. Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), 357–428. Academic Press, New York.

[4] Y. Peres (1992), Iterating von Neumann’s procedure for extracting random bits. Ann. Stat. 20, 590–597.

[5] Harvey, Nate, Alexander E. Holroyd, Yuval Peres, and Dan Romik. "Universal finitary codes with exponential tails." Proceedings of the London Mathematical Society 94, no. 2 (2007): 475-496.

• Sorry, what do you mean by 'extract'? Commented Dec 4, 2020 at 1:54
• Instead of "extract" read "generate" Commented Dec 4, 2020 at 3:49