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?
Thanks for your help.
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. &quot;Universal finitary codes with exponential tails.&quot; Proceedings of the London Mathematical Society 94, no. 2 (2007): 475-496.