-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathrandextract.html
More file actions
231 lines (176 loc) · 27.7 KB
/
randextract.html
File metadata and controls
231 lines (176 loc) · 27.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
<!DOCTYPE html><html xmlns:dc="http://purl.org/dc/terms/" xmlns:og="http://ogp.me/ns#" ><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><title>A Note on Randomness Extraction</title><meta name="citation_pdf_url" content="https://peteroupc.github.io/randextract.pdf"><meta name="citation_url" content="https://peteroupc.github.io/randextract.html"><meta name="citation_title" content="A Note on Randomness Extraction"><meta name="dc.date" content="2026-03-01"><meta name="citation_date" content="2026/03/01"><meta name="citation_publication_date" content="2026/03/01"><meta name="citation_online_date" content="2026/03/01"><meta name="og:title" content="A Note on Randomness Extraction"><meta name="og:type" content="article"><meta name="og:url" content="https://peteroupc.github.io/randextract.html"><meta name="og:site_name" content="peteroupc.github.io"><meta name="dc.format" content="text/html"><meta name="dc.language" content="en"><meta name="title" content="A Note on Randomness Extraction"><meta name="dc.title" content="A Note on Randomness Extraction"><meta name="twitter:title" content="A Note on Randomness Extraction"><meta name="dc.creator" content="Peter Occil"/><meta name="author" content="Peter Occil"/><meta name="citation_author" content="Peter Occil"/><meta name="viewport" content="width=device-width"><link rel=stylesheet type="text/css" href="/style.css">
<script type="text/x-mathjax-config"> MathJax.Hub.Config({"HTML-CSS": { availableFonts: ["STIX","TeX"], linebreaks: { automatic:true }, preferredFont: "TeX" },
tex2jax: { displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], processEscapes: true } });
</script><script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS_HTML-full"></script></head><body> <div class="header">
<nav><p><a href="#navigation">Menu</a> - <a href="#top">Top</a> - <a href="/">Home</a></nav></div>
<div class="mainarea" id="top">
<h1 id="a-note-on-randomness-extraction">A Note on Randomness Extraction</h1><p>This version of the document is dated 2026-03-01. <a href='https://github.com/peteroupc/peteroupc.github.io/issues'>Post an issue or comment on this document</a>.</p>
<p><a href="mailto:poccil14@gmail.com"><strong>Peter Occil</strong></a></p>
<p><em>Randomness extraction</em> (also known as <em>unbiasing</em>, <em>debiasing</em>, <em>deskewing</em>, <em>whitening</em>, or <em>entropy extraction</em>) is a set of techniques for turning data sources into random bits that each equal 1 or 0 with equal probability. This note covers some useful extraction techniques.</p>
<p><a id="In_Information_Security"></a></p>
<h2 id="in-information-security">In Information Security</h2>
<p>In information security, randomness extraction serves to generate a seed, password, encryption key, or other secret value from hard-to-predict nondeterministic sources.</p>
<p>Randomness extraction for information security is discussed in NIST SP 800-90B sec. 3.1.5.1, and RFC 4086 sec. 4.2 and 5.2. Possible choices of such extractors include keyed cryptographic hash functions (see, for example, (Cliff et al., 2009)<sup id="fnref:1"><a href="#fn:1" class="footnote" rel="footnote" role="doc-noteref">1</a></sup>; (Coretti et al., 2019)<sup id="fnref:2"><a href="#fn:2" class="footnote" rel="footnote" role="doc-noteref">2</a></sup>) and two-universal hash functions with a fixed but randomly chosen seed (Frauchiger et al., 2013)<sup id="fnref:3"><a href="#fn:3" class="footnote" rel="footnote" role="doc-noteref">3</a></sup>. In information security applications:</p>
<ul>
<li>Unkeyed hash functions and other unkeyed extraction functions should not be used by themselves in randomness extraction.</li>
<li>Lossless compression should not be used as a randomness extractor.</li>
<li>Where possible, there should be two or more independent nondeterministic sources from which to apply randomness extraction (McInnes and Pinkas 1990)<sup id="fnref:4"><a href="#fn:4" class="footnote" rel="footnote" role="doc-noteref">4</a></sup>.</li>
</ul>
<p>Some papers also refer to two-source extractors and resilient functions (especially the works by E. Chattopadhyay and D. Zuckerman), but there are few if any real implementations of these extraction techniques.</p>
<blockquote>
<p><strong>Example:</strong> The Cliff reference reviewed the use of HMAC (hash-based message authentication code) algorithms, and implies that one way to generate a seed is as follows:</p>
<ol>
<li>Gather data with at least 512 bits of entropy.</li>
<li>Run HMAC-SHA-512 with that data to generate a 512-bit HMAC.</li>
<li>Take the first 170 (or fewer) bits as the seed (512 divided by 3, rounded down).</li>
</ol>
</blockquote>
<p><a id="Outside_of_Information_Security"></a></p>
<h2 id="outside-of-information-security">Outside of Information Security</h2>
<p>Outside of information security, randomness extraction serves the purpose of recycling randomly generated numbers or, more generally, to transform those numbers from one form to another while preserving their randomness. This can be done, for example, to reduce calls to a pseudorandom number generator (PRNG) or to generate a new seed for such a PRNG.</p>
<p>Perhaps the most familiar example of randomness extraction is the one by von Neumann (1951)<sup id="fnref:5"><a href="#fn:5" class="footnote" rel="footnote" role="doc-noteref">5</a></sup>, which works if “independence of successive [coin] tosses is assumed”<sup id="fnref:6"><a href="#fn:6" class="footnote" rel="footnote" role="doc-noteref">6</a></sup>:</p>
<ol>
<li>Flip a coin twice (whose probability of heads is unknown).</li>
<li>If the coin lands heads then tails, return heads. If it lands tails then heads, return tails. If neither is the case, go to step 1.</li>
</ol>
<p>An algorithm found in (Morina et al. 2022)<sup id="fnref:6:1"><a href="#fn:6" class="footnote" rel="footnote" role="doc-noteref">6</a></sup> (called <strong>Algorithm M</strong> in this note) extends this to loaded dice. According to personal communication with K. Łatuszyński, the key “is to find two non overlapping events of the same probability” via “symmetric events {X_1 < X_2} and {X_2 < X_1} that have the same probability”.</p>
<ol>
<li>Throw a (loaded) die, call the result <em>X</em>. Throw the die again, call the result <em>Y</em>.</li>
<li>If <em>X</em> is less than <em>Y</em>, return 0. If <em>X</em> is greater than <em>Y</em>, return 1. If neither is the case, go to step 1.</li>
</ol>
<p>Algorithm M in fact works in a surprisingly broad range of cases; for more, see the <a href="#Appendix"><strong>appendix</strong></a>.</p>
<p>Pae (2005)<sup id="fnref:7"><a href="#fn:7" class="footnote" rel="footnote" role="doc-noteref">7</a></sup> and (Pae and Loui 2006)<sup id="fnref:8"><a href="#fn:8" class="footnote" rel="footnote" role="doc-noteref">8</a></sup> characterize <em>extracting functions</em>. Informally, an <em>extracting function</em> is a function that maps a fixed number of digits to a variable number of bits such that, whenever the input has a given number of ones, twos, etc., every output bit-string of a given length occurs with the same probability as every other output bit-string of that length, regardless of the input’s probability of zero or one.<sup id="fnref:9"><a href="#fn:9" class="footnote" rel="footnote" role="doc-noteref">9</a></sup> Among others, von Neumann’s extractor and the one by Peres (1992)<sup id="fnref:10"><a href="#fn:10" class="footnote" rel="footnote" role="doc-noteref">10</a></sup> are extracting functions. The Peres extractor takes a list of bits (zeros and ones generated from a “coin” with a given probability of heads) as input and is described as follows:</p>
<ol>
<li>Create two empty lists named U and V. Then, while two or more bits remain in the input:
<ol>
<li>If the next two bits are 0/0, append 0 to U and 0 to V.</li>
<li>Otherwise, if those bits are 0/1, append 1 to U, then write a 0.</li>
<li>Otherwise, if those bits are 1/0, append 1 to U, then write a 1.</li>
<li>Otherwise, if those bits are 1/1, append 0 to U and 1 to V.</li>
</ol>
</li>
<li>If U is not empty, do a separate (recursive) run of this algorithm, reading from the bits placed in U.</li>
<li>If V is not empty, do a separate (recursive) run of this algorithm, reading from the bits placed in V.</li>
</ol>
<p>A streaming algorithm, which builds something like an “extractor tree”, is another example of a randomness extractor (Zhou and Bruck 2012)<sup id="fnref:11"><a href="#fn:11" class="footnote" rel="footnote" role="doc-noteref">11</a></sup>.</p>
<p>I maintain <a href="https://github.com/peteroupc/peteroupc.github.io/blob/master/rextract.rb"><strong>source code of this extractor and the Peres extractor</strong></a>, which also includes additional notes on randomness extraction.</p>
<p>Pae’s “entropy-preserving” binarization (Pae 2018)<sup id="fnref:12"><a href="#fn:12" class="footnote" rel="footnote" role="doc-noteref">12</a></sup>, given later, is meant to be used in other extractor algorithms such as the ones mentioned earlier. It assumes the number of possible values, <em>n</em>, is known. However, it is obviously not efficient if <em>n</em> is a large number.</p>
<ol>
<li>Let <em>f</em> be a number in the interval [0, <em>n</em>) that was previously randomly generated. If <em>f</em> is greater than 0, write a 1 (and go to step 2).</li>
<li>If <em>f</em> is less than <em>n</em> − 1, write a 0 <em>x</em> times, where <em>x</em> is (<em>n</em> − 1) − <em>f</em>.</li>
</ol>
<p>Some additional notes:</p>
<ol>
<li>Different kinds of random numbers should not be mixed in the same extractor stream. For example, if one source outputs random 6-sided die results, another source outputs random sums of rolling 2 six-sided dice, and a third source outputs coin flips with a probability of heads of 0.75, there should be three extractor streams (for instance, three extractor trees that implement the Zhou and Bruck algorithm).</li>
<li>Hash functions, such as those mentioned in my <a href="https://peteroupc.github.io/hqrand.html#Counter_Based_PRNGs"><strong>examples of high-quality PRNGs</strong></a>, also serve to produce random-behaving numbers from a variable number of bits. In general, they can’t be extracting functions; however, as long as their output has more bits than used to produce it, that output can serve as input to an extraction algorithm.</li>
<li>Peres (1992)<sup id="fnref:10:1"><a href="#fn:10" class="footnote" rel="footnote" role="doc-noteref">10</a></sup> warns that if a program takes enough input bits (such as flips of a coin with unknown probability of heads) so that the extracting function outputs <em>m</em> bits with them, those <em>m</em> bits will not be uniformly distributed. Instead, the extracting function should be passed blocks of input bits, one block at a time (where each block should have a fixed length of at least 2 bits), until <em>m</em> bits or more are generated by the extractor this way.</li>
<li>Extractors that maintain state, such as the Zhou and Bruck extractor tree, should be used only on sources whose distribution does not change significantly over time. Dividing the source into blocks, as in the previous note, and assigning one extractor instance to each block, can improve robustness for sources whose distribution can change over time.</li>
<li>The lower bound on the average number of coin flips needed to sample a new probability given a coin that shows heads with an unknown probability is as follows (and is a special case of the <em>entropy bound</em>; see, for example, (Pae 2005)<sup id="fnref:7:1"><a href="#fn:7" class="footnote" rel="footnote" role="doc-noteref">7</a></sup>, (Peres 1992)<sup id="fnref:10:2"><a href="#fn:10" class="footnote" rel="footnote" role="doc-noteref">10</a></sup>): ln(2) / ((λ − 1) * ln(1 − λ) − λ * ln(λ)), where λ is the probability of heads of the input coin and ranges from 0 for always tails to 1 for always heads. According to this formula, a growing number of coin flips is needed if the input coin strongly leans towards heads or tails. (For certain values of λ, Kozen (2014)<sup id="fnref:13"><a href="#fn:13" class="footnote" rel="footnote" role="doc-noteref">13</a></sup> showed a tighter lower bound of this kind, but this bound is nontrivial and assumes λ is known.)</li>
</ol>
<p>Devroye and Gravel (2020)<sup id="fnref:14"><a href="#fn:14" class="footnote" rel="footnote" role="doc-noteref">14</a></sup> suggest a special randomness extractor to reduce the number of random bits needed to produce a batch of samples by a sampling algorithm. The extractor works based on the probability that the algorithm consumes <em>X</em> random bits to produce a specific output <em>Y</em>. Since the algorithm seems not to be well developed, I discuss this extractor in detail elsewhere, in “<a href="https://peteroupc.github.io/randmisc.html"><strong>Miscellaneous Notes on Randomization</strong></a>”.</p>
<p><a id="Notes"></a></p>
<h2 id="notes">Notes</h2>
<p><a id="Appendix"></a></p>
<h2 id="appendix">Appendix</h2>
<p> </p>
<p><a id="On_Algorithm_M"></a></p>
<h3 id="on-algorithm-m">On Algorithm M</h3>
<p>Algorithm M works regardless of what numbers <em>X</em> and <em>Y</em> can take on and with what probability, and even if the “dice” for <em>X</em> and <em>Y</em> are loaded differently, as long as—</p>
<ul>
<li>each <em>pair</em> of throws is independent of each other,</li>
<li>each “die” has a chance of showing different outcomes, and</li>
<li>the chance that the first “die” shows a number less than the second “die” is the same as the chance that the first “die” shows a greater number.</li>
</ul>
<p>More formally, P(<em>X</em> < <em>Y</em>) must be equal to P(<em>X</em> > <em>Y</em>). This relationship is equivalent to <em>statistical indifference</em> (Montes Gutiérrez 2014)<sup id="fnref:15"><a href="#fn:15" class="footnote" rel="footnote" role="doc-noteref">15</a></sup>, (De Schuymer et al. 2003)<sup id="fnref:16"><a href="#fn:16" class="footnote" rel="footnote" role="doc-noteref">16</a></sup>. This relationship works even if <em>X</em> and <em>Y</em> depend on each other but independent of everything else; this is easy to see if we treat <em>X</em> and <em>Y</em> as a single random “vector” [<em>X</em>, <em>Y</em>]. This is shown by the following two propositions. In the propositions below, a random variable is <em>nondegenerate</em> if it does not take on a single value with probability 1.</p>
<p><strong>Proposition 1.</strong> <em>Let X and Y be real-valued nondegenerate random variables. Then Algorithm M outputs 1 or 0 with equal probability if and only if X and Y are statistically indifferent.</em></p>
<p><em>Proof.</em> For every <em>X</em> and every <em>Y</em> there are only three mutually exclusive possibilities, <em>X</em>><em>Y</em>, <em>Y</em>><em>X</em>, and <em>X</em>=<em>Y</em>. Because both random variables are nondegenerate, P(<em>X</em>><em>Y</em>) or P(<em>Y</em>><em>X</em>) or both are nonzero, and P(<em>X</em>=<em>Y</em>) < 1. For the algorithm to return 0, <em>X</em> must be less than <em>Y</em>, and for it to return 1, <em>X</em> must be greater than <em>Y</em>.</p>
<p>For the “only if” part: For the algorithm to return 1 or 0 with equal probability, it must be that P(<em>X</em>><em>Y</em>) = P(<em>Y</em>><em>X</em>). But this necessarily means that P(<em>X</em>><em>Y</em>) and P(<em>Y</em>><em>X</em>) are both 1/2 or less. And if we assign half of the remainder (the remainder being P(<em>X</em>=<em>Y</em>)) to each probability, we get—</p>
<ul>
<li>P(<em>X</em>><em>Y</em>) + P(<em>X</em>=<em>Y</em>)/2 = 1/2, and</li>
<li>P(<em>Y</em>><em>X</em>) + P(<em>X</em>=<em>Y</em>)/2 = 1/2,</li>
</ul>
<p>and thus, <em>X</em> and <em>Y</em> must be statistically indifferent by definition (see later).</p>
<p>For the “if” part: If <em>X</em> and <em>Y</em> are statistically indifferent, this means that α = P(<em>X</em>><em>Y</em>) + P(<em>X</em>=<em>Y</em>)/2 and β = P(<em>Y</em>><em>X</em>) + P(<em>X</em>=<em>Y</em>)/2 are equal and α = β = 1/2. Since both α and β are equal and P(<em>X</em>=<em>Y</em>) in α and β are also equal, this must mean that P(<em>X</em>><em>Y</em>) = P(<em>Y</em>><em>X</em>). It thus follows that for <em>X</em> and <em>Y</em>, the algorithm will return 1 or 0 with equal probability. ◻</p>
<p><strong>Proposition 2.</strong> <em>Let X and Y be real-valued nondegenerate random variables that are independent, identically distributed, and defined on the same probability space. Then X and Y are statistically indifferent.</em></p>
<p><em>Proof.</em> By definition, <em>X</em> and <em>Y</em> are statistically indifferent if and only if <em>X</em> is statistically preferred to <em>Y</em> and vice versa (that is, P(<em>X</em>><em>Y</em>) + P(<em>X</em>=<em>Y</em>)/2 >= P(<em>Y</em>><em>X</em>) + P(<em>Y</em>=<em>X</em>)/2) (De Schuymer et al. 2003)<sup id="fnref:16:1"><a href="#fn:16" class="footnote" rel="footnote" role="doc-noteref">16</a></sup>. Because both random variables are nondegenerate, P(<em>X</em>><em>Y</em>) or P(<em>Y</em>><em>X</em>) or both are nonzero, and P(<em>X</em>=<em>Y</em>) < 1. Moreover, because both random variables are identically distributed, their distribution functions <em>F</em><sub><em>X</em></sub> and <em>F</em><sub><em>Y</em></sub> are the same, and therefore their values and expectations for any particular <em>z</em> (for example, <em>F</em><sub><em>X</em></sub>(<em>z</em>) and E[<em>F</em><sub><em>X</em></sub>(<em>z</em>)], respectively) are the same.</p>
<p>If we look at Theorem 3.12 in (Montes Gutiérrez 2014)<sup id="fnref:15:1"><a href="#fn:15" class="footnote" rel="footnote" role="doc-noteref">15</a></sup>, we see that we can replace—</p>
<ul>
<li>the left hand side of Equation 3.5 with 0 − 0, since it’s a difference of expectations of the same distribution function and random variable, and</li>
<li>the right hand side with (1/2) * 0, since the difference of <em>P</em>(<em>X</em> =<em>Y</em>) and <em>P</em>(<em>X</em> = <em>X′</em>) is taken and <em>P</em>(<em>X</em> =<em>Y</em>) is equivalent to <em>P</em>(<em>X</em> = <em>X′</em>), which is equivalent because <em>X</em>, <em>X′</em> and <em>Y</em> are identically distributed by the hypotheses of this proposition and Theorem 3.12.</li>
</ul>
<p>As a result, Equation 3.5 becomes 0 >= 0, which is true and thus establishes that <em>X</em> is statistically preferred to <em>Y</em> (by Theorem 3.12). It thus trivially follows that <em>Y</em> is likewise statistically preferred to <em>X</em> once we replace the roles of both variables, since both variables are identically distributed. As a result, <em>X</em> and <em>Y</em> are found to be statistically indifferent and the proposition is proved. ◻</p>
<p>Here are some of the many examples where this algorithm works:</p>
<ul>
<li>Set <em>X</em> and <em>Y</em> to two independent Gaussian random numbers with a mean of 0 but a different standard deviation. Or…</li>
<li>Set <em>X</em> and <em>Y</em> to two independent uniform(0, 1) random numbers. Or…</li>
<li>Set <em>X</em> and <em>Y</em> to two independent uniform(0, 1) random numbers, then set <em>Y</em> to (<em>X</em>+<em>Y</em>)/2.</li>
</ul>
<p>See also a procedure given as a remark near the end of a paper by Camion (1974)<sup id="fnref:17"><a href="#fn:17" class="footnote" rel="footnote" role="doc-noteref">17</a></sup>.</p>
<p><a id="License"></a></p>
<h2 id="license">License</h2>
<p>Any copyright to this page is released to the Public Domain. In case this is not possible, this page is also licensed under <a href="https://creativecommons.org/publicdomain/zero/1.0/"><strong>Creative Commons Zero</strong></a>.</p>
<div class="footnotes" role="doc-endnotes">
<ol>
<li id="fn:1">
<p>Cliff, Y., Boyd, C., Gonzalez Nieto, J. “How to Extract and Expand Randomness: A Summary and Explanation of Existing Results”, 2009. <a href="#fnref:1" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:2">
<p>Coretti, S., Dodis, Y., et al., “Seedless Fruit is the Sweetest: Random Number Generation, Revisited”, 2019. <a href="#fnref:2" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:3">
<p>Frauchiger, D., Renner, R., Troyer, M., “True randomness from realistic quantum devices”, 2013. <a href="#fnref:3" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:4">
<p>McInnes, J. L., & Pinkas, B. (1990, August). On the impossibility of private key cryptography with weakly random keys. In Conference on the Theory and Application of Cryptography (pp. 421-435). <a href="#fnref:4" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:5">
<p>von Neumann, J., “Various techniques used in connection with random digits”, 1951. <a href="#fnref:5" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:6">
<p>Giulio Morina. Krzysztof Łatuszyński. Piotr Nayar. Alex Wendland. “From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains.” Ann. Appl. Probab. 32 (1) 327 - 359, February 2022. <a href="https://doi.org/10.1214/21-AAP1679"><strong>https://doi.org/10.1214/21-AAP1679</strong></a> <a href="#fnref:6" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:6:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:7">
<p>Pae, S., “Random number generation using a biased source”, dissertation, University of Illinois at Urbana-Champaign, 2005. <a href="#fnref:7" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:7:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:8">
<p>Pae, S., Loui, M.C., “Randomizing functions: Simulation of discrete probability distribution using a source of unknown distribution”, <em>IEEE Transactions on Information Theory</em> 52(11), November 2006. <a href="#fnref:8" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:9">
<p>It follows from this definition that an extracting function must map an all-X string (such as an all-zeros string) to the empty string, since there is only one empty string but more than one string of any other length. Thus, no reversible function can be extracting, and a function that never returns an empty string (including nearly all hash functions) can’t be extracting, either. <a href="#fnref:9" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:10">
<p>Peres, Y., “<a href="https://projecteuclid.org/euclid.aos/1176348543"><strong>Iterating von Neumann’s procedure for extracting random bits</strong></a>”, Annals of Statistics 1992,20,1, p. 590-597. <a href="#fnref:10" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:10:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a> <a href="#fnref:10:2" class="reversefootnote" role="doc-backlink">↩<sup>3</sup></a></p>
</li>
<li id="fn:11">
<p>Zhou, H. and Bruck, J., “<a href="https://arxiv.org/abs/1209.0730"><strong>Streaming algorithms for optimal generation of random bits</strong></a>”, arXiv:1209.0730 [cs.IT], 2012. <a href="#fnref:11" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:12">
<p>S. Pae, “<a href="https://arxiv.org/abs/1602.06058v2"><strong>Binarization Trees and Random Number Generation</strong></a>”, arXiv:1602.06058v2 [cs.DS], 2018. <a href="#fnref:12" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:13">
<p>Kozen, D., <a href="http://www.cs.cornell.edu/~kozen/Papers/Coinflip.pdf"><strong>“Optimal Coin Flipping”</strong></a>, 2014. <a href="#fnref:13" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:14">
<p>Devroye, L., Gravel, C., “<a href="https://arxiv.org/abs/1502.02539v6"><strong>Random variate generation using only finitely many unbiased, independently and identically distributed random bits</strong></a>”, arXiv:1502.02539v6 [cs.IT], 2020. <a href="#fnref:14" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:15">
<p>Montes Gutiérrez, I., “Comparison of alternatives under uncertainty and imprecision”, doctoral thesis, Universidad de Oviedo, 2014. <a href="#fnref:15" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:15:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:16">
<p>De Schuymer, Bart, Hans De Meyer, and Bernard De Baets. “A fuzzy approach to stochastic dominance of random variables”, in <em>International Fuzzy Systems Association World Congress</em> 2003. <a href="#fnref:16" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:16:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:17">
<p>Camion, Paul, “Unbiased die rolling with a biased die”, North Carolina State University. Dept. of Statistics, 1974. <a href="#fnref:17" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
</ol>
</div>
</div><nav id="navigation"><ul>
<li><a href="/">Back to start site.</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io">This site's repository (source code)</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io/issues">Post an issue or comment</a></ul>
<div class="noprint">
<p>
<a href="//x.com/intent/post?text=A+Note+on+Randomness+Extraction&url=https%3A%2F%2Fpeteroupc.github.io%2Frandextract.html">Share via X (Twitter)</a>, <a href="//www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fpeteroupc.github.io%2Frandextract.html">Share via Facebook</a>, <a href="//news.ycombinator.com/submitlink?u=https%3A%2F%2Fpeteroupc.github.io%2Frandextract.html&t=A+Note+on+Randomness+Extraction">Share via Hacker News</a>, <a href="//www.reddit.com/submit?url=https%3A%2F%2Fpeteroupc.github.io%2Frandextract.html&title=A+Note+on+Randomness+Extraction">Share via Reddit</a>
</p>
</div>
<p style='font-size:120%;font-weight:bold'><a href='https://peteroupc.github.io/randextract.pdf'>Download a PDF of this page</a></p><p>Of interest to the computer graphics and music community:</p><ul><li><a href='https://peteroupc.github.io/graphics.html'><b>Graphics for classic-style game development</b></a>.<li><a href='https://peteroupc.github.io/graphics.html#Building_a_Public_Domain_music_synthesis_library_and_instrument_banks'><b>MIDI music synthesis for classic-style games and apps</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper'><b>Tileable wallpapers with limited colors and resolution</b></a>.<li><a href='https://peteroupc.github.io/graphicsapi.html'><b>Lean programming interfaces for classic graphics</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper/docs/uielements.html'><b>Traditional user-interface graphics</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper/docs/pixeltovector.html'><b>Converting images to vector graphics</b></a>.</ul><p>Open questions for math and probability experts:</p><ul><li><a href='https://peteroupc.github.io/requests.html'><b>Requests and open questions</b></a>.<li><a href='https://peteroupc.github.io/bernreq.html'><b>Open questions on the Bernoulli factory problem (the new-coins-from-old problem)</b></a>.<li><a href='https://peteroupc.github.io/requestsother.html'><b>Other open questions on probability</b></a>.<li><a href='https://peteroupc.github.io/sampling.html'><b>The sampling problem</b></a>.</ul></nav></body></html>