Random data unbiasing
This algorithm converts integers representing the duration of
successive clicks from a Geiger counter into unbiased,
uncorrelated random bits. Detailed description.
- A simple implementation of the algorithm in Python.
- a C implementation of the same algorithm, rather more
complex but much faster.
- A Python implementation of an alternative strategy for the
same job, due to Juels, Jakobsson, Shriver, and Hillyer.
- An optimised C implementation of that strategy, based on GNU MP.
A simpler problem is that of converting a stream of independent
coin flips with a fixed but unknown bias to a stream of
independent unbiased random bits. An asymptotically optimal
strategy for this is the Advanced Multi-Level Strategy (AMLS),
first proposed by Yuval Peres. AMLS is used as a component of the
algorithm above. Here are some implementations of that
- in Python, but try reading it even if you don't speak
Python. It's a very straightforward implementation of the
strategy, with a simple test rig.
- a C implementation of the same strategy. This uses a rather
cunning technique due to firstname.lastname@example.org which overwrites
the input bits array rather than using auxiliary storage to
generate the output bits recursively; Peres informs me he
presented this same technique in the very first lecture
describing the AMLS. Version 0.5.
- corners' original version of the above code, in C++ (really
C). "You can do anything you want with it. It comes with a
"garbage man's guarantee". Satisfaction guaranteed, or double
your garbage back. (smile)"
- in Python. A more complex version that produces bits
asynchronously; you push input bits into it and it pushes
output bits upstream. Extremely space inefficient.
- a similar C implementation; call "
bit, &output);" every time you get a biased random
bit, and it will write as many output bits as it can to the
output. It also uses fixed storage, so it doesn't reach the
asymptotically perfect efficiency, but in practice that
doesn't really matter. Version 0.1.
- Two implementations by Benjamin Goldberg, email@example.com.
Turn Loaded Dice into Fair Coins
- Ari Juels, Markus Jakobsson, Elizabeth Shriver, Bruce
K. Hillyer, IEEETIT: IEEE Transactions on Information
von Neumann's Procedure for Extracting Random Bits [PDF]
- Yuval Peres, The Annals of Statistics, 1992, pp
590-597. The paper which first presented the AMLS. From Yuval
Peres' research archive.
a Biased Coin [PDF]
- Teaching notes by Michael Mitzenmacher describing the
Advanced Multi-Level Strategy - a very good introduction. Six
pages. From this