3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Nov 28 '20 at 8:46
  • $\begingroup$ @EmilJerabek can you do it with Shannon entropy if you don't care about efficiency? $\endgroup$ – Joshua Grochow Nov 28 '20 at 20:09
  • 2
    $\begingroup$ 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. $\endgroup$ – J.G Nov 28 '20 at 22:01
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Dec 2 '20 at 19:02
  • 3
    $\begingroup$ @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. $\endgroup$ – J.G Dec 2 '20 at 22:31
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Sorry, what do you mean by 'extract'? $\endgroup$ – Karagounis Z Dec 4 '20 at 1:54
  • $\begingroup$ Instead of "extract" read "generate" $\endgroup$ – Yuval Peres Dec 4 '20 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.