Random number generation

2015-05-14 — 2023-09-08

Wherein a practical pseudo‑RNG implementation is described, the absence of seedable generators in JavaScript is noted, and methods for producing non‑uniform variates from uniform draws are considered.

computers are awful
Monte Carlo
probabilistic algorithms
probability
pseudorandomness
Figure 1: The RNG reads from the i.i.d. sequence generator in the presence of adversarial discriminators

Practical pseudo-RNG implementation. See also pseudorandomness for theories Monte Carlo for some applications, and for some background theory algorithmic statistics.

1 Uniform PRNGs

Generating uniformly distributed numbers on some interval, such as [0,1].

I regularly need to do this in languages that do not support…

  • local
  • seedable
  • convenient

… PRNGs.

JavaScript doesn’t support seeding. Supercollider does but insists on a per-thread RNG. MaxMSP is a miscellany of folly as usual.

2 Non-uniform variates

Say you have a uniform RNG but you need… Poisson? Gaussian? RNGs. Now what?

  • Luc Devroye’s wonderful and unexpectedly deep Non-Uniform Random Variate Generation has analytic results
  • Using NNs to do it? Reassure yourself this is possible (in principle) with the approximation results in Perekrestenko, Müller, and Bölcskei (2020); Perekrestenko, Eberhard, and Bölcskei (2021).

3 References

Devroye. 1986. Non-uniform random variate generation.
———. 2006. “Nonuniform Random Variate Generation.” In Simulation. Handbooks in Operations Research and Management Science.
Nisan, and Wigderson. 1994. “Hardness Vs Randomness.” Journal of Computer and System Sciences.
Perekrestenko, Eberhard, and Bölcskei. 2021. “High-Dimensional Distribution Generation Through Deep Neural Networks.” Partial Differential Equations and Applications.
Perekrestenko, Müller, and Bölcskei. 2020. “Constructive Universal High-Dimensional Distribution Generation Through Deep ReLU Networks.”