Notes

Chapter 7: Mechanisms in Programs and Nature

Section 5: The Intrinsic Generation of Randomness


[Generating sequences with] unequal probabilities

Given a sequence a of n equally probable 0's and 1's, the following generates a single 0 or 1 with probabilities approximating {1-p, p} to n digits:

Fold[({BitAnd, BitOr}[[1 + First[#2]]][#1, Last[#2]]) &, 0, Reverse[Transpose[{First[RealDigits[p, 2, n,-1]], a}]]]

This can be generalized to allow a whole sequence to be generated with as little as an average of two input digits being used for each output digit.

From Stephen Wolfram: A New Kind of Science [citation]