Pseudorandom number generation in Excel

[Brad Gile]

The generation of random numbers is too important to be left to chance.

-Robert R. Coveyou, Oak Ridge National Laboratory

[Brad Gile]

Article at http://home.comcast.net/~charltoncr/mt19937ar.htm
Download at http://home.comcast.net/~charltoncr/#MersenneTwister.

I have not tried this yet. IIRC, there is an MT for C# as well.

[campbell]

Here's a description of some of the randomness tests
[from http://en.wikipedia.org/wiki/Diehard_tests]

The tests are:

* Birthday spacings: Choose random points on a large interval. The spacings between the points should be asymptotically Poisson distributed. The name is based on the birthday paradox.

* Overlapping permutations: Analyze sequences of five consecutive random numbers. The 120 possible orderings should occur with statistically equal probability.

* Ranks of matrices: Select some number of bits from some number of random numbers to form a matrix over {0,1}, then determine the rank of the matrix. Count the ranks.

* Monkey tests: Treat sequences of some number of bits as "words". Count the overlapping words in a stream. The number of "words" that don't appear should follow a known distribution. The name is based on the infinite monkey theorem.

* Count the 1s: Count the 1 bits in each of either successive or chosen bytes. Convert the counts to "letters", and count the occurrences of five-letter "words".

* Parking lot test: Randomly place unit circles in a 100 x 100 square. If the circle overlaps an existing one, try again. After 12,000 tries, the number of successfully "parked" circles should follow a certain normal distribution.

* Minimum distance test: Randomly place 8,000 points in a 10,000 x 10,000 square, then find the minimum distance between the pairs. The square of this distance should be exponentially distributed with a certain mean.

* Random spheres test: Randomly choose 4,000 points in a cube of edge 1,000. Center a sphere on each point, whose radius is the minimum distance to another point. The smallest sphere's volume should be exponentially distributed with a certain mean.

* The squeeze test: Multiply 231 by random floats on [0,1) until you reach 1. Repeat this 100,000 times. The number of floats needed to reach 1 should follow a certain distribution.

* Overlapping sums test: Generate a long sequence of random floats on [0,1). Add sequences of 100 consecutive floats. The sums should be normally distributed with characteristic mean and sigma.

* Runs test: Generate a long sequence of random floats on [0,1). Count ascending and descending runs. The counts should follow a certain distribution.

* The craps test: Play 200,000 games of craps, counting the wins and the number of throws per game. Each count should follow a certain distribution.

Info on some of these tests [or stronger versions of them]:http://www.jstatsoft.org/v07/i03/paper

[campbell]

Sorry if I linked these before, but software to run randomness tests can be found here:
http://csrc.nist.gov/groups/ST/toolk..._software.html

and here:
http://www.phy.duke.edu/~rgb/General/dieharder.php

[whisper]

Originally Posted by 1695814

why is that?

If you want to see how a change to something that isn't effecting the underlying risk profile has on the model, you want to push through the exact same underlying risk profile to model the differences.

If you have a separate series of numbers - its impossible to tell what is due to your change and what is due normal variation.

[whisper]

Originally Posted by MountainHawk

So, you do your own testing of RNG? I use @Risk, and just sort of accepted that the RNG they use is 'random' enough. The current version uses the Mersenne Twister as a default (with 7 other options available), plus a stratified sampling technique if you want called Latin Hypercube, which I've never looked into other than to know it's a stratified sampling technique.

My only problem with @Risk is that adding a new @Risk random variable can screw up your output.

[campbell]

Here we go, I'm finally getting around to writing an article on this, and I'm using a title suggested by an AO denizen...

So let's do a group edit/write here [I'm lazy, sue me... or, hey, Eddie, I'm giving you and Howard a break on editing this!]

This is not even a finished first draft, I'm still pulling together links. I'll spoiler it so it doesn't ruin the look... I'm open to nit-picking edits as well as suggestions of stuff I've missed. You'll see some of my lists aren't finished. Whatever. Just getting it out there.

Spoiler:

Rand-dum or Random
By Mary Pat Campbell with help from the AO community



First: you have no business doing Monte Carlo modeling in Excel.

Clear?

Fine.

Now that’s out of the way, we’re using Excel all the time for inappropriate things, so what’s a few random trials between friends?

Even if you’re using a tool that isn’t fully appropriate for Monte-Carlo modeling in terms of efficiency, there’s no reason to make the situation worse: to wit, using Excel’s built-in pseudorandom number generating function RAND().

Below I will give some reasons why using this function is a bad idea, as well as a few options to use in place of RAND(). Along the way, we will see some principles in choosing a pseudorandom number generator for various purposes, as well as pointing out some resources along this realm.

1. RAND() is a volatile function.

Volatile functions are ones that recalculate every time Excel recalculates. For mundane volatile functions such as TODAY(), this is not such a big deal, as they rarely change their results upon recalculation
(and generally, you’re only calling them a few times within a spreadsheet – not a million times).

But every time Excel recalculates, you get a different number resulting. And the slightest thing will make Excel recalculate. Change a font? Excel recalculates. Hit enter in an empty cell? Excel recalculates.

This can be a big pain if you have a lot of calls to RAND() in your spreadsheet. Every single one of the cells that contains that function will recalculate.

To be sure, there are a few ways to get around this problem. First, you can set your calculation mode to Manual, in which case the spreadsheet is recalculating only when you request it to.

Second, you can copy your “random number cells” and paste as values over those very same cells. Of course, if you need more “random” numbers, you’re going to need to put the formulas back in.

2. RAND() is not seeded.

What do I mean by a seeded PRNG? I mean that you give the PRNG a specific number, a “seed”, which initializes the algorithm underlying the routine… and will give you the exact same sequence of pseudo-random numbers in a particular order each time you use that particular seed.

This makes it easy to reproduce a particular Monte Carlo run without needing to store all the pseudorandom variates that go into producing your MC estimate.

………[time passes… something here?]


What should you look for in a PRNG for Monte Carlo purposes?
1. Reproducibility
2. Good statistical behavior
a. Proper distribution
b. Lack of correlation
c. Good moment matching
d.
[needs more in the above list]

Some options that don’t have this issue:
A. Use Excel’s VBA function Rnd(), which is seeded. Of course, this requires coding some in VBA, but it’s not too bad to implement. Problem: it’s a black box, but you can run the results through the randomness test suite Dieharder and see how it does for what you want.
B. Use the free Excel add-in NtRand. This is based on the popular-for-MC-PRNG [enough jargon yet?] Mersenne Twister, and is fairly easy to use with Excel. What’s more, it will produce correlated normal variates, which is pretty handy if you don’t want to be doing a Cholesky decomposition yourself. NtRand can be found here:
C. Use your own code in VBA. You can find standard code for PRNGs at Numerical Recipes [yes, they’re not in VBA, but it’s relatively easy to take the FORTRAN code and do a transfer]. You may also have seen the interest rate generator that has come out of the Academy. You can find the VBA code for a PRNG inside the modules that are part of the release… reusing code is a sign of programming maturity, right?
D. Random.org – now, interestingly, this does not give you pseudorandom sequences – it’s based on observed noise in the atmosphere.



By the way, I do use RAND() all the time – to create very simple illustrative examples to show how various formulas work in a stochastic cash-flow model. It’s fine for a quick simulation or two, but not serious Monte Carlo estimation.

By the way, wonder of wonders, I found a RAND() substitute that was, if anything, worse than the original. I leave it up to the exercise for the reader of this article to see what’s bad about the following:

=(NOW()*100000 - INT(NOW()*100000))

Information about why the author thought this was a good idea resides at this link:
http://support.microsoft.com/kb/44738/en-us

If you’d like to argue in favor of this approach, buy me a drink, and I’ll listen to your defense of that monstrosity. But I’m going to need more than just one drink to sit still for it.


Links:

Diehard(er) tests: http://www.phy.duke.edu/~rgb/General/dieharder.php

More on the Diehard tests: http://en.wikipedia.org/wiki/Diehard_tests

NtRand: http://www.ntrand.com/

Random.org: come on, you can guess this one

On some difficult-to-pass randomness tests: http://web.ipac.caltech.edu/staff/fm...nessTest09.pdf

[limabeanactuary]

Just sent off my article on this. Should be appearing in the July edition of CompAct.

thanks to the AO for its help in getting it together!

[limabeanactuary]

http://www.soa.org/library/newslette...-campbell.aspx

Thanks to the community at the Actuarial Outpost for discussion of PRNG issues in Excel.

(and the reason I realized my article was out is that someone just emailed to object to something I wrote)

[limabeanactuary]

Here's the item someone sent me:
http://www.noesis.net.au/main/Resour...rces/prng.html

I assume that's Excel 2007's PRNG, not the Excel 2010 version [which I was told was a Mersenne Twister with longer period]