Skip to main content

2  Uniform Random Variables

In this chapter, we will consider the generation of random numbers for the uniform probability model. From the uniform distribution, we can generate realizations of random variables of any other probability model. The generation of realizations of random variables from the uniform distribution, in general, cannot be performed by machines in a purely algorithmic way, since any sequence produced by traditional software is a predictable sequence of pseudo-random numbers. Recently, however, it has been possible to capture thermal noise from processors to generate genuinely random numbers. In Python, this is possible through the os module, using the os.urandom() method.

Two random number generators must produce the same results in their applications. If this does not occur, one of them cannot be considered a good random number generator (Press et al. 1992).

The concepts of uniform numbers and random numbers are often confused. Uniform numbers are those that vary randomly in a real interval of values with constant probability. However, we must differentiate uniform random numbers from other types of random numbers, such as, for example, normal or Gaussian random numbers. These other types generally come from transformations performed on uniform random numbers. Therefore, a reliable source to generate uniform random numbers determines the success of stochastic inference methods and Monte Carlo simulation processes.

2.1 Uniform Random Numbers

Uniform random numbers are those that, in principle, lie within a real interval, generally between \(0\) and \(1\), for which we cannot produce a predictable sequence of values and whose density function is constant. In various computer programs, these numbers are generated using the random command or similar commands. In Pascal, for example, if this command is used with the argument \(n\), random(n), integer random numbers \(U\) in the interval \(0 \leq U \le n-1\) are generated, and if the argument \(n\) is not used, the generated numbers are real random values in the interval \([0, 1)\).

In general, programs use the congruential method. Let us consider integer uniform numbers \(U_1, U_2, U_3, \dots\) between \(0\) and \(m-1\), where \(m\) represents a large integer. We can generate these numbers using the congruential method through the recursive relation:

\[U_{i+1}=\left( a U_{i} + c \right) \mod m \tag{2.1}\]

where \(m\) is called the modulus, and \(a\) and \(c\) are positive integers called the multiplier and increment, respectively. The mod operator returns the remainder of the division of the argument \(\left( a U_{i} + c \right)\) by \(m\). The recurrent sequence (2.1) repeats in a period that is not greater than \(m\), for obvious reasons. If \(a\), \(c\), and \(m\) are appropriately chosen, the sequence has a maximum length equal to \(m\). The choice of the initial value \(U_0\) determines the sequence. The value of the corresponding uniform number in the interval from \(0\) to \(1\) is given by \(U_{i+1}/m\), which is always less than \(1\), but can be equal to zero.

Let us present a didactic example to illustrate a random number generator. Let \(U_0=a=c=7\) and \(m=10\), therefore,

\[U_1=(7\times 7+7) \mod 10 = 56 \mod 10 = 6\] \[U_2=(7\times6+7) \mod 10 = 49 \mod 10 = 9\] and so on. We obtain the sequence of random numbers: \[\{ 7, 6, 9, 0, 7, 6, 9, 0, 7, 6, 9, \cdots \}\] and we verify that the period is equal to \(4\), \(\{7, 6, 9, 0, \cdots\}\), which is less than \(m=10\).

This method has the disadvantage of being serially correlated. If \(m\), \(a\), or \(c\) are not carefully chosen, the correlation can compromise the generated sequence. On the other hand, the method has the advantage of being very fast. We can notice that with each call of the method, only a few calculations are executed. We generally choose the value of \(m\) to be the largest integer that can be represented by a \(32\)-bit machine, which is \(2^{32}\). An example that was used for many years on IBM mainframe computers, which represents a terrible choice, is \(a= 65{,}539\) and \(m = 2^{31}\).

Serial correlation is not the only problem with this method. The higher-order bits are more random than the lower-order (less significant) bits. We should generate integers between 1 and 20 by \(j=1+\text{int}(20 \times \text{random}(\text{seed}))\), instead of using the less accurate method \(j=1+\mod (\text{int}(1000000\times \text{random}(\text{seed})),20)\), which uses lower-order bits. There is strong evidence, empirical and theoretical, that the congruential method

\[U_{i+1}= a U_{i} \mod m \tag{2.2}\]

is as good as the congruential method with \(c \ne 0\), if the modulus \(m\) and the multiplier \(a\) are chosen with care (Press et al. 1992). Park and Miller (1988) proposed a minimal “standard” generator based on the choices:

\[a = 7^5 = 16{,}807 \quad m = 2^{31} - 1 = 2{,}147{,}483{,}647 \tag{2.3}\]

This random number generator is not perfect, but it passed all the tests to which it was subjected and has been used as a standard to compare and judge other generators. A problem that arises and that we must overcome is that it is not possible to directly implement in a high-level language equation (2.2) with the constants from (2.3), because the product of \(a\) and \(U_i\) generally exceeds the maximum limit of \(32\) bits for integers. We can use a trick, due to Schrage (1979), to multiply \(32\)-bit integers and apply the modulo operator, ensuring portability for implementation in virtually all languages and all machines. Schrage’s algorithm is based on the factorization of \(m\) given by:

\[m= aq + r;\qquad \textrm{i.e.}, \qquad q = \lfloor m/a \rfloor; \quad r =m \mod a\]

where \(\lfloor z \rfloor\) denotes the integer part of the number \(z\) used as an argument. For a number \(U_{i}\) between 1 and \(m-1\) and for a small \(r\), specifically for \(r<q\), Schrage (1979) showed that both \(a(U_i \mod q)\) and \(r\lfloor U_i/q \rfloor\) belong to the interval \(0\), \(\cdots\), \(m-1\) and that \[a U_{i} \mod m=\left\{ \begin{array}{ll} a(U_i \mod q) - r\lfloor U_i/q \rfloor , & \textrm{if greater than 0}\\ a(U_i \mod q) - r\lfloor U_i/q\rfloor + m , & \textrm{otherwise.}\\ \end{array} \right. \tag{2.4}\]

Computationally we observe that the relation: \[a(U_i \mod q) = a(U_i-q\lfloor U_i/q\rfloor)\] is verified. In Python, one can choose to use the % (mod) operator, which returns the remainder of the operation between two integers, and the // (div) operator, which returns the quotient result for integer operations. The quantity \(U_i \mod q = U_i - (U_i \quad \textrm{div} \quad q)\times q\) can be obtained in Python simply by \(U_i \% q\). We assign the result to any variable defined as an integer. To apply Schrage’s algorithm to the constants of (2.3) we must use the following values: \(q=127{,}773\) and \(r = 2{,}836\).

Next, we present the minimal standard random number generator algorithm:

The average time and total time were computed to run 100000 uniform random numbers. To capture the time, the datetime package was used, as well as to obtain the time difference between the start and the end of the processing of our function. The block to do this must be executed all at once, that is, by marking the block and pressing enter in Positron.

Some considerations regarding this algorithm: a) the gnap function (minimal standard random number generator) returns a real number between \(0\) and \(1\). This type of specification determines that the variables have double precision. Double precision (double-precision float) has numbers in the range from \(\pm 2.225 \times 10^{-308}\) to \(\pm 1.798 \times 10^{308}\), occupies \(24\) bytes of memory, and has \(15-17\) significant digits; b) the seed value is defined by the user and is passed as a parameter to the function. This means that the program variable that calls the function and is passed as a seed must be updated with the new modified value in gnup. If its initial value is zero or negative, the function assigns an integer dependent on the system time at the time of the call; c) the function has a dependency on the datetime package, which was used to capture the system time and day.

The routine is initialized with the values of \(n\) and the seed provided by the user. If the seed is null or negative, we assign a new value dependent on the system clock at the time of the call. From this point on, the program must repeatedly call the gnap function, which returns the value of the random number between \(0\) and \(1\) using the algorithm described above, until the sequence requested by the user is completed. In successive calls of this function, the seed value is always equal to the value of the last step.

The period of gnap is on the order of \(2^{31} \approx 2.15\times 10^{9}\), that is, the complete sequence is slightly over 2 billion random numbers. Thus, we can use gnap for a few practical purposes. As we have already pointed out, the minimal standard random number generator has two basic limitations, namely, short sequence and serial correlation.

Alternatively, since Python is capable of dealing with integers of arbitrary size without the limitations of \(32\) or \(64\) bits and without overflow, we can implement the standard random number generator without Schrage (1979)’s trick. In R, it is also possible to do something similar using coercion from double to integers. We should be concerned about using Schrage (1979)’s trick in languages where integers are \(32\) bits or to ensure code portability to any operating system or programming language. The simplified code is presented below, whose function was named gna_ws and whose arguments are the necessary constants and whose default values are the same as those previously used. The dependency on the datetime package remains in this version.

As there are methods to eliminate serial correlation and that increase the period of the sequence, we recommend that they be adopted. Of course, the function presented was intended to illustrate how we can program our own functions to generate uniform random numbers. Python, however, has its own uniform number generator, which we will see next. One of the best and most interesting random number generators is the Mersenne Twister (MT). Mersenne Twister is a pseudo-random number generator developed by Makoto Matsumoto and Takuji Nishimura in the years 1996 and 1997 (Matsumoto and Nishimura 1998). The MT has the following merits according to its developers:

  • it was developed to eliminate the flaws of different existing generators;

  • it has the advantage of presenting the longest period and highest order of equidistribution of any other implemented method. It provides a period that is on the order of \(2^{19.937}-1 \approx 4.3154 \times 10^{6001}\), and a 623-dimensional equidistribution;

  • it is one of the fastest existing generators, although complex;

  • it makes very efficient use of memory.

There are many implemented versions of this algorithm, including in Fortran and C, which are available on the internet. Fortunately, Python already has this algorithm implemented. As it is a more advanced topic, which goes beyond what we intend to present in these lecture notes, we will not describe this type of procedure for incorporating functions written in other languages.

2.2 Uniform Random Numbers in Python

In Python, we can generate continuous uniform random numbers using a pre-programmed function. Uniform random numbers are generated by the command random.uniform(low=0.0, high=1.0, size=None) from the numpy library, where None is to generate just one value, and can be replaced by \(n\), between low and high (excluded), which are arguments that delimit the minimum and maximum value of the sequence to be generated. Seed control to generate a reproducible sequence of uniform numbers is given by the command random.seed(seed=None) from numpy, where the seed argument must be an integer. Python automatically determines a new seed with each call. We can generate different sequences in each call of the generator command, without worrying about the random seed. The uniform random number generator uses the Mersenne-Twister algorithm by default.

In the program presented below, we illustrate how we can generate \(n\) uniform random numbers between \(0\) and \(1\) in a compact, simple, and efficient way:

We made a program to compare the execution time of the gnap and random.uniform() functions and we return the average time for each realization of the random variable. This way, we verify that the random.uniform algorithm is the fastest of all, according to the relative values presented below. Obviously, we have to consider that the numpy algorithm is a compiled function. The gnap algorithm, in turn, was implemented in Python, which uses an interpreted language. The time comparisons can be seen in the following program. The program used was:

We can make a histogram using the program below. For this, we use the matplotlib library.

WarningNote about graphs in the browser

In some browsers (especially Firefox), displaying graphs with plt.show() in the interactive environment of this page may fail. If the graph does not appear, open the material in Google Chrome, Microsoft Edge, or Safari.

2.3 Genuinely Random Numbers

Using Python, we just need to use the os module. The os.urandom(k) function makes a system call (like getrandom in Linux or BCryptGenRandom in Windows) that returns true and uniform random bytes coming from the OS hardware ecosystem. The returned result contains k random bytes of uniform entropy from the processor/operating system. The int.from_bytes() method receives this generated value as an argument and transforms it into an \(8k\)-bit integer. If we divide this by the total number of combinations of the \(8k\)-bit representation, which is \(2^{8k}\), we will have a uniform random number in the interval \([0,\,1)\).

Since each bit generated by the hardware has exactly a \(50\%\) chance of being \(0\) or \(1\) (independently of the previous bits), all bit combinations from \(0\) to \(2^{8k}-1\) are equally likely. By dividing by the maximum value, we map this discrete uniform distribution to the continuous interval \([0, 1)\) without distorting the distribution’s probability. The option byteorder='big' in int.from_bytes(dados_fisicos, byteorder='big') makes Python read the most significant bits first, that is, from left to right in the value of the dados_fisicos variable that was generated. This option value in the context of generating continuous uniform numbers does not affect randomness, but was used because it is the natural logic of building integers in bits.

The script below illustrates the generation of a uniform random sample of size \(n=5\).

Speed is the main point where the hardware generator and the NumPy generator drastically diverge. The hardware procedure (os.urandom) is much slower than np.random.uniform. We performed a comparative test identical to the previous one, in which we observed that NumPy can be from \(10\) to more than \(100\) times faster, depending on the sample size.

2.4 Comparative Performance Analysis

With the execution results of the different approaches presented in this chapter, we can build a computational overview of the efficiency of each method. The following table consolidates the estimated average time for generating each uniform random number in Python:

Generation Method Generator Type Average Time per Number Relative Speed (vs. NumPy)
np.random.uniform Pseudo-random (Vectorized in C) ~0.008 µs 1.0x (Speed Reference)
gna_ws Pseudo-random (Congruential without Schrage) ~0.171 µs ~22 times slower
gnap Pseudo-random (Minimal standard with Schrage) ~0.232 µs ~30 times slower
os.urandom Genuinely Random (Via Hardware) ~0.304 µs ~39 times slower

This empirical comparison brings two fundamental lessons for computational statistics:

  1. The Cost of the Operating System Boundary: The hardware procedure (os.urandom) proved to be the slowest of all. This occurs because Python needs to interrupt its flow and make a system call (syscall) so that the operating system kernel consults the hardware ecosystem. This process, added to the lack of vectorization (use of the for loop), creates a computational bottleneck.
  2. The Efficiency of NumPy: The numpy library is extremely fast not only because it uses deterministic mathematical formulas (pseudo-random algorithm), but also because it delegates the creation of the numbers to optimized memory blocks compiled in the C language, operating on the nanosecond scale.

In short, the hardware generator is indispensable for information security, cryptography, and digital key generation purposes, scenarios in which unpredictability must be absolute. However, for heavy stochastic simulations, such as Monte Carlo methods that demand millions or billions of realizations quickly, the np.random.uniform command remains the correct choice due to its speed and efficiency.

2.5 Exercises

  1. Use the gnap generator to generate \(n\) realizations of an exponential distribution \(f(x)= \lambda e^{-\lambda x}\). We know from the probability integral transform theorem that if \(U\) has a uniform distribution, \(X=F^{-1}(U)\) has a probability distribution with density \(f(x)=F'(x)\); where \(F(x)=\int_{-\infty}^{x}f(t)dt\) is the distribution function of \(X\) and \(F^{-1}(y)\) is its inverse function for the value \(y\). For the exponential, the probability distribution function is: \(F(x)=\int_{0}^{x}\lambda e^{-\lambda t}dt=1-e^{-\lambda x}\). To obtain the inverse function we have to equate \(u\) to \(F(x)\) and solve for \(x\). Thus, \(u=1-e^{-\lambda x}\) and solving for \(x\) we have: \(x=-\ln{(1-u)}/\lambda\). Due to the symmetry of the uniform distribution, \(1-u\) can be replaced by \(u\). The final result is: \(x=-\ln{(u)}/\lambda\). To generate exponential numbers, simply generate uniform numbers and apply the relation \(x=-\ln{(u)}/\lambda\). Do this to build a function that generates \(n\) exponential realizations. Apply the function to obtain random samples from the exponential of size \(n=100\) and obtain the histogram of the simulated sample. Calculate the mean and the variance and compare them with the theoretical values of the exponential distribution.

  2. To generate numbers from a normal distribution, whose density is given by \(f(x) = 1/(\sqrt{2\pi \sigma^2})\exp\{-(x-\mu)^2/(2\sigma^2)\}\), what would be the difficulty in being able to use the theorem announced in the previous proposed exercise?

  3. How could we adapt the algorithm presented in this chapter to generate uniform random numbers using the values proposed by Park and Miller, that is, \(a=48.271\) and \(m=2^{31}-1\)? Implement the algorithm, taking care regarding the new multiplier \(q\) and remainder \(r\) of the factorization of \(m\)?

  4. How could you propose a simple statistical test to evaluate the randomness of the sequence of uniform numbers generated by these algorithms presented in the chapter? Implement your idea.