<p>The relevance of Shannon entropy is to repeated sampling: Given <span class="math-container">$n$</span> independent samples from a source with binary Shannon Entropy <span class="math-container">$k$</span>, you can extract <span class="math-container">$nk(1+o(1)$</span> i.i.d. uniform bits as <span class="math-container">$n$</span> 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.</p>
<p>[1] M. Keane and M. Smorodinsky (1979), Bernoulli schemes of the same
entropy are finitarily isomorphic. Annals of Math. 109, 397–406.</p>
<p>[2] P. Elias (1972), The efficient construction of an unbiased random sequence. Ann. Math. Statist. 43, 865–870.</p>
<p>[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.</p>
<p>[4] Y. Peres (1992), Iterating von Neumann’s procedure for extracting random bits. Ann. Stat. 20, 590–597.</p>
<p>[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.</p>

CC BY-SA 4.0
2020-12-04T01:54:39.913Z
Sorry, what do you mean by 'extract'?
Karagounis Z
CC BY-SA 4.0
2020-12-04T03:49:31.537Z
Instead of "extract" read "generate"
Yuval Peres
CC BY-SA 4.0
2020-12-02T18:07:28.717Z
2020-12-02T18:07:28.717Z
Yuval Peres
<p>All the sources online say that, intuitively, a distribution with entropy <span class="math-container">$k$</span> has <span class="math-container">$k$</span> bits of pure randomness in it.</p>
<p>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 <span class="math-container">$k$</span> bit binary string?</p>
<p>Thanks for your help.</p>

CC BY-SA 4.0
2020-11-28T08:46:49.850Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-11-28T20:09:31.467Z
@EmilJerabek can you do it with Shannon entropy if you don't care about efficiency?
Joshua Grochow
CC BY-SA 4.0
2020-11-28T22:01:08.870Z
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.
Jason Gaitonde
CC BY-SA 4.0
2020-12-02T19:02:54.110Z
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.
Joshua Grochow
CC BY-SA 4.0
2020-12-02T22:31:53.383Z
@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.
Jason Gaitonde
CC BY-SA 4.0
2020-12-08T21:28:00.513Z
There is a standard and trivial answer to the question _as stated_, assuming $k>0$. Select any two distinct outcomes $A$ and $B$ that each have positive probability.  Sample twice; if you get $A$ then $B$, output "0"; if you get $B$ then $A$ output "1"; otherwise repeat as necessary.  This will output a single random bit.  Do it $k$ times to get a uniformly random $k$-bit binary string.  No doubt OP has some additional constraints on the answer in mind?
Neal Young
<it.information-theory><randomness><shannon-entropy>
Generating $k$ random bits from a pdf with entropy $H(p) = k$
Karagounis Z
# Generating $k$ random bits from a pdf with entropy $H(p) = k$

(Asked by: username_0 on 2020-11-28)

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.

**Tags:** it.information-theory, randomness, shannon-entropy

> **Comments:**
> **username_1**: 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.  
> **username_2**: @EmilJerabek can you do it with Shannon entropy if you don't care about efficiency?  
> **username_3**: 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.  
> **username_2**: Ah, username_5'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.  
> **username_3**: @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.  
> **username_4**: There is a standard and trivial answer to the question _as stated_, assuming $k>0$. Select any two distinct outcomes $A$ and $B$ that each have positive probability.  Sample twice; if you get $A$ then $B$, output "0"; if you get $B$ then $A$ output "1"; otherwise repeat as necessary.  This will output a single random bit.  Do it $k$ times to get a uniformly random $k$-bit binary string.  No doubt OP has some additional constraints on the answer in mind?  

---

## 1 answers

### Answer by username_5 on 2020-12-02. Score: 5

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, username_5, and Dan Romik. "Universal finitary codes with exponential tails." Proceedings of the London Mathematical Society 94, no. 2 (2007): 475-496.

> **Comments:**
> **username_0**: Sorry, what do you mean by 'extract'?  
> **username_5**: Instead of "extract" read "generate"  

---

