How and Why Computers Roll Loaded Dice

[joshuaellinger]

Weird -- it appears to be missing the last 10-20 years of development in random numbers by the data science and cryptography community. They have put a lot of work into it.

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.

[binarycoffee]

So this is not what the article is about.

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.

[1] https://arxiv.org/abs/2003.03830

[2] https://en.wikipedia.org/wiki/Alias_method

[loup-vaillant]

Don't bother with elliptic curves, any stream cipher will do. We make messages indistinguishable from random with those, we might as well use them for random number generation as well.

The arc4random_buf(3) function for instance uses the Chacha20 cipher under the hood (some outdated & broken implementations may still use RC4).

[acqq]

The article is not about randomness in general, once one reads the whole. It's just the title and the longish intro that can mislead.

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."

[mindslight]

I think the algorithm is most likely worthwhile, but the article is terrible. Another instance of journalism adding a narrative meant to entertain but really just disinforms.

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.

[benrbray]

This article is a bit rough around the edges, and they really should make it clear when they mean "pseudorandom" vs "random", especially when one goal of the article is ostensibly to explain pseudorandomness to laymen!

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)

With a small correction [3], we can guarantee that our samples have uniform distribution (Haar measure) on the space of all orthogonal matrices:

  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;

For more, read about random matrix theory! As an exercise for the reader, how would you generate: a random symmetric matrix? a random skew-symmetric matrix? a random positive-definite matrix? a random hamiltonian path in a fixed graph?

[1]: http://gregorygundersen.com/blog/2018/04/29/reparameterizati...

[2]: https://timvieira.github.io/blog/post/2014/07/31/gumbel-max-...

[3]: http://www.ams.org/notices/200705/fea-mezzadri-web.pdf

[ache7]

Modern computers have some sources of entropy that can be used to create a random numbers. For example, the timings of the memory access, race condition of threads. User interaction (mouse movement, delays between keystrokes) can also be used as an input signal to feed a random number generator (which is some hashing algorithm).

[roaur]

> Pi itself is not a random number, for example, but the digits of pi are believed to be random in this way (what mathematicians describe as “normal”): Every integer from 0 to 9 appears about the same number of times.

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?

[wdevanny]

Normal has myriad uses in mathematics. See [1]. Somewhat annoyingly there is no common thread to their meanings (Or at least not one that I am aware of).

The article intends normal number, not normal distribution.

[1] https://en.wikipedia.org/wiki/Normal

[morelisp]

It is not. They are so-named because in any base, almost all reals have this property, i.e. reals which do not are abnormal.

https://en.wikipedia.org/wiki/Normal_number

[SilasX]

I feel like it’s leaving something out. Some major advance in RNGs is just based on padding the possibilities so they’re a power of two and throwing out the “padding possibilities” if they come up?

[kingkawn]

It seems comical that our idea of randomness is so specific