Discreet Mathematics - Random Numbers

Back in College, I wrote the paper below about Random Number Generation. Personally, I really enjoyed creating this paper and thought I'd like to share it with you. You should see a link to a spreadsheet that accompanied this document. Enjoy!

Discreet Mathematics
"Random Number Generation"
Jeffrey R. Byrns


Many people take for granted how computers generate random numbers for any particular program that they may be using. What people generally donÂ’t understand, or even realize is that computers are incapable of creating random numbers. They do however generate numbers that appear to be random, or arbitrary. Many forms of random number generators are in practice today, all of which are nothing more then algorithms with math equations behind them.

One of the most basic, and most popular, forms of random number generation is the algorithm developed by D. Lehmer in 1951 (Sedgewick, p. 511). It is called the linear congurential method. We can generate a set of random numbers with the below algorithm.

A [0] = Seed
b = Constant
M = Constant

For i := 1 to N do
a[ i ] := (a[ i -1] * b + 1 ) Mod M

In order to get a random number we take the previous random number (a[ i -1] ), and then we multiply it by ( b ) and then add 1. Take the result of this and get the remainder when we divide it by M (Mod M). It can help if you think of a[] as being an array.

One of the first questions to be raised is what should the constants for b and M be? D.E. Knuth (born in Milwaukee, Wi) came up with a few rules governing the choices for b and M. According to Knuth, M should be a very large number. It is convenient for computer processing to make M a power of 2 or 10. The constant b should be smaller than M. It shouldnÂ’t be too small however. A good rule of thumb is to use a b with one less digit than M.

Below is an example of the above algorithm applied in an Excel spreadsheet. A scatter plot has been provided to show the “Randomness” of the output. In the example a “Seed” of 15 was used, b is set at 1277, and finally M is set to 131072.



A spreadsheet has been included with this report, Random.xls. This can be used to demonstrate the above example

As you can see above, once you know the “Seed” value you can reproduce this seemingly random number scheme. Seed values can be created by any number of ways. Visual Basic uses the randomize statement to generate the Seed value. In turn it uses the internal clock to create a seed value.

You may have noticed that the resulting numbers generated can be extremely large. Usually, these types of random numbers aren’t what are required. Often what is required is a random number between one and whatever. This can easily be achieved by adding one extra step, Mod it. Probably the best-known application of using the mathematical Mod function is to “Wrap Around”. For instance, lets say you wanted a number between 1 and 10. You could take any of the results from the linear congurential method and mod it by 10, and then add 1. You can be certain that your results will be between 1 and 10.

Exploring other methods of random generators can be done by looking at Microsoft’s spreadsheet application, Excel. Looking under the Data Analysis menu, one can find “Random Number Generation” in a list of analysis tools. Once opened you will find that Excel provides seven different methods of generating random numbers. The web site http://www.vuse.vanderbilt.edu:8888/es130/lectures/lecture7/random.html provides a lot of insight on how to use this functionality. The seven different methods are; Uniform, Normal, Bernoulli, Binomial, Poisson, Patterned, and Discreet. Bernoulli and Binomial will be the remaining focus of this document.

Excel Bernoulli method:

Using the Bernoulli method will result in either a 0 or a 1, pass or fail if you will. It is based on the principle of the Bernoulli Trials. Giving the probability of success at 50% or .5 and 10 trials should reveal a result of 5 1Â’s and 5 0Â’s. The table below demonstrates the output of Excel for this demonstration. An excellent application for this method would be to reproduce a coin-flipping scenario. Given only a pass or fail, any application that requires only two outcomes would be a candidate for this method.

Excel Binomial method:

The Binomial is an expansion of the Bernoulli method. Using a variable number of Bernoulli trials, you can sum them up. In the table, an example of using the Binomial method is displayed. In this case, the probability of success is .5 and the number of trials is 100. Notice the output for 10 separate generations. The numbers hover around 50, or half the amount of the number of trials.

As you can see, computers donÂ’t generate random numbers; they generate numbers that appear to be random. In a sense, one could say that a computer generates arbitrary numbers not random numbers. Arbitrary meaning that what we require is any number, and it doesnÂ’t really matter what is returned. The most common algorithm used to date is the Linear Algorithm, and it is incredibly easy to implement. The math involved is very rudimentary and the steps involved are few. Although the focus of this document has focused on the Linear Congurential method, other methods of creating random numbers exist. Using ExcelÂ’s data analysis tools, one has a plethora of choices when choosing a randomization method.


References

Dewdney, A. (1989). The Turing Omnibus. Rockville. Computer Science Press.

Sedgewick, R. (1988). Algorithms. USA. Addison-Wesley Publishing Company, Inc.

Vanderbilt University. (Unknown). Random Number Generation. Available: http://www.vuse.vanderbilt.edu:8888/es130/lectures/lecture7/random.html