How and Why Computers Roll Loaded Dice
quantamagazine.org
quantamagazine.org
If I recall correctly there are two major angles, 1. there is an instruction in modern Intel chips that samples random thermal noise. 2. there are a whole class of elliptical curve approaches that pass a bunch of randomness tests.
And I'm just scratching the surface here.
It's about:
https://arxiv.org/abs/2003.03830
"The Fast Loaded Dice Roller: A Near-Optimal Exact Sampler for Discrete Probability Distributions"
"Empirical evaluations on a broad set of probability distributions establish that FLDR is 2x-10x faster in both preprocessing and sampling than multiple baseline algorithms, including the widely-used alias and interval samplers. It also uses up to 10000x less space than the information-theoretically optimal sampler, at the expense of less than 1.5x runtime overhead."
Also if I had to guess without studying the paper, the benefit of the sum of the weights being a power of two isn't just being efficient in memory or time, but rather efficient in use of the random input tape. Naively, if you want to generate a uniform number between 0-128 inclusive from an input of uniform bits, you consume 8 random bits and if they form a value within the range you return it. Otherwise (129-255) you throw all the bits away and start over. Using the leftover entropy seems like it should be possible somehow.
The arc4random_buf(3) function for instance uses the Chacha20 cipher under the hood (some outdated & broken implementations may still use RC4).
It discusses a new method to generate integer values according to an arbitrary probability distribution, using as input a uniform random generator. Whether the input generator is truly random, pseudorandom, cryptographically secure etc, is irrelevant: the output will presumably only be as random/secure as the input RNG.
Admittedly, the article does a poor job at explaining what the FLDR method is about, and it looks as biased as the method itself (sorry for the easy pun). From my understanding of the paper [1], the method is better than the state-of-the-art Alias method [2] only when the entropy of the target distribution is low. When entropy is high, it performs similarly (or may even be a bit slower) but uses up to 8 times more memory space.
As an aside, using a source of random numbers to generate other random objects is quite an interesting problem! For converting from one probability distribution to another, we have classical methods like rejection/importance sampling, and modern deep learning makes constant use of the "reparameterization trick" [1,2]. Looking beyond just numbers, here's a neat trick for generating a random orthogonal matrix:
A = np.random(n,n)
Q,_ = np.qr(A)
def haar_measure(n):
# naive method
Z = randn(n,n) + 1j*randn(n,n) / np.sqrt(2);
Q,R = np.linalg.qr(Z);
# correction
d = np.diag(R);
PH = np.diag(d) / np.absolute(d);
return Q @ PH;
[1]: http://gregorygundersen.com/blog/2018/04/29/reparameterizati...
[2]: https://timvieira.github.io/blog/post/2014/07/31/gumbel-max-...
Does this not make the digits of Pi discreetly distributed (an equal chance for each integer?)? Is the meaning of 'normal' here not referencing a normal distribution?
The article intends normal number, not normal distribution.
The common thread is the Latin word "norma" for a carpentry square. This gets taken literally in cases like "normal vector", figuratively in cases like "Euclidean norm" (i.e. to measure) then increasingly distant as the word is a root to mean usual/ordinary/average (i.e. according to standard measure) in many languages and thereby ends up in "normal number", "normalized vector", etc. "Normal distribution" inherits it doubly, Gauss used it in the orthogonality sense and later authors in the ordinary sense.