The Precision of Pseudo-Random Number Generators

Names: Ahsan Fayyaz, Jiangliang Hu, Shahran Jyhan, Jake Luceno, & Zhicong Wen

Eng 21007 Writing for Engineering

Professor Alikhani

City College of New York

October 10^th   2018

 

Abstract

The goal of this report is to categorize the speed and precision of three different pseudo-random number generating functions, taken respectively from three separate programming languages: C++, MATLAB, and Python.  Our results provided insufficient evidence to reject our hypothesis that the data sets produced by Python and MATLAB were sampled from truly random distributions.  Our data did however allow us to reject the output produced by C++, providing extremely strong evidence of it being a sample from a distribution different from the true population distribution of random numbers.  The trade off came in the speed of the programs, with C++ running at almost two full orders of magnitude quicker than its more precise counterparts.  Our conclusion suggests that any of the three generators is likely sufficient for everyday programming needs, with C++ providing a strong trade-off between speed and precision.

Introduction

Few things in life are ever a sure thing. Often, to describe the likelihood of a given scenario, we turn to probabilities and statistics to simulate a given outcome.  We use the mean, the standard deviation, and related measures to determine whether or not we think a given situation may be likely.

In computer science, to accomplish these simulations, we often utilize what are called random variables.  Random variables can take on any value within a given range, for example, any number from 1 to 100.  It may be quite useful to introduce some form of randomness into a program, whether to randomly place ships in a digital version of the game battleship, or to emulate the swerving of the financial market for purposes of analysis and stock investing.

Consequently, having a random number generator you can rely on as a programmer is tantamount to producing accurate and reliable data, in whatever simulation one may be coding.

Unfortunately, true randomness is very difficult to simulate, especially on a computer, where the machine deals in finite algorithms, and doesn’t leave open much room for varied interpretation.  Computers are very much input/output machines, and consequently, any input you give the machine will deterministically produce a given output.  This is true for random numbers as well.  Truly random numbers cannot be generated on a computer, which is why we turn to so called “pseudo-random number generators” (Rubin, 2011).

These generators produce numbers which approximate those produced by truly random generators, but they do so algorithmically, and therefore, deterministically.  Their results may appear random at first, but it is theoretically possible to show that the results are not random, in the truest sense of the word (Rubin, 2011).

Knowing this, we have chosen to create an experiment which will test some aspects of pseudo-random number generators.  We will use three different pseudo-random algorithms (utilizing the programming languages C++, python, and MATLAB), and perform rudimentary statistical analysis of our results to see if we can determine the extent to which these pseudo-random generators emulate their truly random counterparts.

Specifically, we will generate 1,000,000 sets of 1,000 random numbers in the range of [1,100] using each programming language’s native “random” function.  By comparing the means of these distributions, we may be able to demonstrate, using a Statistical Z-Test, that these generators produce distributions sufficiently distinct from their truly random counter-parts (LaMorte, 2017).

Materials and methods

To complete this experiment, all one requires is a computer with a C++ compiler, a Python interpreter, and the MATLAB software suite installed.

Procedure

To test the pseudo-random number generators of the software packages, one needs to begin by constructing a data set.  To do this, three programs must be written, one in each programming language, to generate 1,000,000 sets of pseudo-random numbers, 1000 numbers in each set, with each individual number on the range [1, 100] (For examples of such code please see appendix A).

Averages are then taken across all data sets, such that each the experimenter is left with 1,000,000 averages.  Those averages are then themselves averaged to produce a “true” average for each of the programming languages.

The reasons for taking the individual average for each data set before taking the average across the whole data set is that it allows our data to conform to what is called “the assumption of normalcy.”  In accordance with central limit theorem, a sampling distribution of sufficient size will approach normalcy, such that we may perform a Z Hypothesis Test in order to compare the means of our population and our samples (Stat Trek, 2018).

Z-Tests are a type of hypothesis testing which allow the comparison of means.  We assume that our samples are indeed random, and then attempt to use the Z-Test to prove they are not.  If the Z-Test fails to prove they are not random, it does not imply they are true random; simply that there is insufficient evidence to reject the assumption of true randomness (LaMorte, 2017).

Since the mean and standard deviation of a truly random distribution can be computed exactly, we use them as our true population parameters with which to compare our samples.  The Z-Test we conducted was performed at an alpha level of 0.05, meaning that we will reject any sample which had less than a 5% chance of occurring, given the assumption that the numbers are drawn from a truly random distribution.

For further details regarding the calculation of the means and standard deviations/ standard errors of the various distributions, as well as the computation of the Z statistic, please see results.

Results

We expect a true random number generator to produce numbers such that the chance of any given number being chosen is the same as the chance of any other given number being chosen.  This is called a uniform distribution (Discrete Uniform Distribution, 2018).

To calculate the mean of a uniform distribution, on the general range [A, B], the value of the following formula can be easily calculated (Discrete Uniform Distribution, 2018):

Random numbers on the range [1, 100], The uniform distribution in question, have a mean, or µ, of exactly 50.5.

Figure 1. Uniform Distribution

The standard deviation of a uniform distribution is given by the formula (Discrete Uniform Distribution, 2018):
The standard deviation of the random distribution shown in Figure 1 is calculated to be approximately 28.866.

This standard deviation and mean can be used to calculate the mean and standard error for the sampling distribution needed for our Z test.  The normal formula for calculating standard error from standard deviation is the following: , where is the standard deviation, and n is the number of samples (Stat Trek, 2018).  In our first case, we produce a sampling distribution which shows us the likelihood of any given 1000 random numbers having a specific mean.  The expected mean is 50.5, like it was in the uniform distribution.  The standard error represents how dispersed our data is.  It tells us how likely a given sample mean is, granted that it is a sample created from taking 1000 random numbers from our uniform distribution.  Our standard error in this case is calculated to be approximately 0.9128.

Since we have taken 1,000,000 sets of 1,000, this number is not our final standard error.  We are in fact sampling at a second layer, to produce a distribution which tells us how likely we are to see a given sample “true average,” granted again, that each of the billion numbers drawn was drawn from the original uniform distribution.  This formula is the same as it was for the first standard error, although it uses our first standard error in place of the standard deviation, and n is now 1,000,000:

In the case of our data, we obtain the final standard error value of 0.9128/1000 = 0.0009128.

We now move on to calculating the Z score statistic for the Z test.  The Z Test states two hypotheses; the null hypothesis and the alternative hypothesis, denoted H₀ and H_A respectively (LaMorte, 2017).

H₀: The three programs generate random data sets with a mean equal to the population mean of 50.5

H_A: The three programs generate random data sets with means not equal to the population mean of 50.5

To test these hypotheses, we first decide on alpha level for our test.  Alpha levels represent how precise we want our test to be.  For example, by choosing an alpha level of 0.05, we are stating that for any sample which had a less than 5% chance of occurring, given our assumption that it is drawn from a population with a true mean of 50.5, we will reject our null hypothesis.  This is equivalent to the statement, if , we will reject the null hypothesis (LaMorte, 2017).

The Z statistic for a given sample mean, , is given by the formula: , where µ represents the true population mean (LaMorte, 2017).  The values of  for each program are reported in Table 1. and Figure 2.

Then using our formula for the Z statistic, we calculate the number of standard deviations away from the population mean each sample mean is (LaMorte, 2017).  The summary of the data is reported in Table 2. and Figure 3.

 

Table 1. Sample Means

C++	Python	MATLAB
50.4680	50.4982	50.4993

Figure 2. Non-Standardized Normal Distribution

 

Table 2. Sample Z-Scores

C++	Python	MATLAB
-35.494	-1.938	-0.745

 

Figure 3. Standardized Normal Distribution

 

Discussion

The above data and figures represent the culmination of a variety of statistical analysis and sampling techniques which we utilized in order to evaluate three pseudo-random number generators for precision and speed.

As the result, all three programs generally have a sample mean close to the population mean of 50.5. The non-standardized normal distribution graph shows that C++ has a sample mean of 50.4680, Python has a sample mean of 50.3982, and MATLAB has a sample mean of 50.4993.  The standard error of this distribution was calculated to be 0.0009128.

The data shows that MATLAB was solidly located within the acceptance zone of our Z-Test, with a Z-Score of -0.745.  Python bordered very close to the edge of the rejection zone, but was still technically located within the acceptance zone, with a Z-Score of -1.938, where the cut-off score derived from our alpha level was +/- 1.96.  Consequently, we fail to reject our null hypotheses, that these samples are taken from a distribution with a true mean of 50.5, and therefore have insufficient evidence to claim that MATLAB or Python’s random functions generate data meaningfully different from true random.

We do however reject our null hypothesis for our data set sampled from C++.  The sample mean fell well outside the acceptance zone, with a Z-Score of -35.494, making it extremely unlikely that this sample was taken from a truly random distribution.

 

Conclusion

Steve Ward says “One thing that traditional computer systems aren’t good at is coin flipping” (Rubin, 2011, par. 1). They’re deterministic, which means that if you ask the same question you’ll get the same answer every time (Rubin, J. M., 2011).

Real random numbers are generated by physical phenomena such as coin tossing, dice, runners, noise from electronic components, nuclear fission, etc. These random number generators are called physical random number generators, but they have the drawback of requiring relatively complicated technical specifications. We can only generate truly random numbers by sampling actual physical phenomena, which themselves are nondeterministic (Random vs. Pseudorandom, 2012).

Pseudorandom numbers are actually fixed periodic sequences, meaning that given enough data, it is possible to predict the next number using the numbers which have previously been generated.  Random functions in a computer are simulated by deterministic algorithms, which produce these periodic sequences (although ideally their period is extremely long).  Even the best algorithm is limited to a pre-determined set of outcomes.  Ultimately, the concepts of ‘random’ and ‘algorithm’ are contradictory, as algorithms, by definition, produce deterministic results based on their input (Random vs. Pseudorandom, 2012).

For most applications, a pseudo-random number generator is sufficient. For instance, if someone is designing a simple version of Tetris, and they require a random number generator to decide which piece comes next, then it won’t matter if it is truly random, as long as it is not easily predictable by the player.  The game will work properly with Pseudorandom number generators of sufficient complexity.

In summary, our results suggest C++ has the fastest generator, with the whole process running in under a minute.  As a trade-off however, we have shown that C++ does not produce truly random results.  MATLAB and Python are relatively similar to each other in terms of performance. Although both required more than 20 minutes of run time, their results were indistinguishable from true randomness. We however acknowledge some limitations in our study.  The number of samples we took is disproportionately large, which affects the practicality of our findings, in terms of both speed and precision.  The statistical significance of our results is fairly high, as our results are conclusive regarding C++, but the clinical significance of our study is very low.  We have shown that there is a distinguishable difference between C++ and truly random number generators, but the absolute difference is less than 0.04 at the sample size used.  In practice, this difference will rarely be of consequence to everyday programming needs (LaMorte, 2017).

 

References

 

1. (2012, May 07). Random vs. Pseudorandom Number Generators. Retrieved from https://www.youtube.com/watch?v=itaMNuWLzJo

Are Random Number Generators Really Random? (n.d.). Retrieved October 3, 2018, from http://www.knowtherng.com/are-random-number-generators.html

C++ Calculate Average of a Vector. (n.d.). Retrieved October 3, 2018, from https://it-offshore.co.uk/code/23-c/26-c-calculate-average-of-vector-without-a-for-loop

Discrete uniform distribution. (2018, August 21). Retrieved October 3, 2018, from https://en.wikipedia.org/wiki/Discrete_uniform_distribution

LaMorte, W. (2017). Hypothesis Testing for Means & Proportions. Retrieved October 3, 2018, from http://sphweb.bumc.bu.edu/otlt/MPH-Modules/BS/BS704_HypothesisTest-Means-Proportions/BS704_HypothesisTest-Means-Proportions3.html

Rubin, J. M. (2011, November 11). Can a computer generate a truly random number? Retrieved October 3, 2018, from https://engineering.mit.edu/engage/ask-an-engineer/can-a-computer-generate-a-truly-random-number/

Stat Trek. (2018). Sampling Distributions. Retrieved October 3, 2018, from https://stattrek.com/sampling/sampling-distribution.aspx