Pseudo-random number generators: continuous values from discrete machines

Author

Jeet Sukumaran

1 How a discrete-valued machine generating continuous random values

A computer’s RNG (Random Number Generator), generates (pseudo-)random integer values. For continous value, the computer will generate values by sampling from a grid in \([0, 1)\).

As with the challenges of a deterministic machine generating random values, when requiring random continuous value, we are faced with the challenge of a discrete-value calculating machine dealing with non-integer values. A computer can generate a pseudo-random integer value, \(k\), using its Pseudo-Random Number Generator. For continuous values, the generated integer value, \(k\) is then scaled to a floating-point \(x\) by, for e.g., \(\frac{k}{2p}\), where \(p\) is the number usable bits and \(0 \le k \le 2^p - 1\). The result in floating point value in the range \(0 \le x < 1\).

While 1 is excluded from the range, this does not change the distribution. A continuous uniform distribution on \([0, 1]\) assigns probability zero to any single point, include \(0\) or \(1\) in that range, so this exclusion of 1 does not change the characteristics of the distribution. (With continuous distributions, we do not ask what is the probability of observing any particular value. We ask is the probability of observing a range of values.)

Let

\(p\) = number of mantissa bits of the target floating-point type (\(p=53\) for Float64)
\(k\) drawn uniformly from

\[ {0,1,\dots,2^p - 1} \]

Define

\[ x = \frac{k}{2^p}. \]

Then:

The mapping \(k \mapsto x\) is bijective
Each possible \(x\) has probability exactly \(2^{-p}\)
The support is

\[ \left\{ 0, \frac{1}{2^p}, \frac{2}{2^p}, \dots, \frac{2^p-1}{2^p} \right\} \subset [0,1) \]

Note this is a discrete uniform distribution over the set of values \(\{0, \frac{1}{2^p}, \frac{2}{2^p}, \ldots, \frac{2^p-1}{2^p}\}\), not a continuous one. The operation bins the range \([0, 1)\) into \(2^p\) equal width bins of \(\frac{1}{1^p}\) width. For Float64 this result in \(2^{53} \approx 9 \times 10^{15}\) bins of width \(2^{-53} \approx 1.11 \times 10^{-16}\).