4
$\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.

Improve this question
$\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
    Commented Nov 28, 2020 at 8:46
  • $\begingroup$ @EmilJerabek can you do it with Shannon entropy if you don't care about efficiency? $\endgroup$
    – Joshua Grochow
    Commented Nov 28, 2020 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$
    – Jason Gaitonde
    Commented Nov 28, 2020 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
    Commented Dec 2, 2020 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$
    – Jason Gaitonde
    Commented Dec 2, 2020 at 22:31

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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