4 ms·
A truly random source will yield independent and identically distributed values. You can take a collection of those values and convert them to an index in the
by nullc 2y ago
A truly random source will yield independent and identically distributed values.
You can take a collection of those values and convert them to an index in the set of all possible permutations of those values. That index will be uniformly distributed in the range of the number of permutations, regardless of the input distribution so long as it's IID.
Once you have a uniform value on a range you can extract uniform bits from it.
See also: Von Neumann's debiasing algorithm.
In practice RNGs use some kind of debiaser, though often they use ones that leave a lot of entropy on the floor. OTOH, stronger debiasers are more harmed by failures to be completely IID (e.g. some inter-output correlation, or the distribution changing over time with temperature).