Generating a normal random variable

[Physics_wiz]

I'm trying to write a program in excel to generate random variables with mean mu and standard deviation sigma. I can simply refer to the worksheet function for it but it takes forever when I have it inside a loop doing a monte carlo simulation. There is one function in excel that returns a random number between 0 and 1 and I can refer to that function in the loop as many times as I want because it's not expensive (ie. doesn't take much time).

So, here's the problem:
I have mu, sigma, and a random number between 0 and 1.
I need to generate a random number from a normal distribution with mean mu and standard deviation sigma.

Anyone know how to do this?

Thanks.

 

[HallsofIvy]

I know that Knuth has an algorithm but don't remember any details.

Anyway, I googled on "Normal Distribution" and "algorithm" and got a number of hits. One you might find interesting is this:
http://www.seio.es/test/Archivos/t62/t62bun.pdf .

 

[mathman]

The "standard" method (I used it years ago) is to generate normal variates in pairs.
If you use exp(-(x²+y²)/2) as the integrand, convert to polar coordinates (r,a), then let u=r²/2, you can then choose u= -ln(X), a=2pi*Y, where X and Y are random numbers, and the normal variates will be rcos(a) and rsin(a), where r=(2u)^1/2.

 

[chroot]

Use the central limit theorem. If you add several uniform random variables, the result is (roughly) Gaussian.

Here's an example from a (Verilog) program:

//
	// Calculate roughly Gaussian noise by applying the central limit theorem
	// to four [0,1] uniform random numbers. Multiply by sqrt(3) to fix the
	// variance at 1.
	//
	
	noise = ( ( ($random / 4294967295.0 + 0.5) +
		    	($random / 4294967295.0 + 0.5) +
		    	($random / 4294967295.0 + 0.5) +
		    	($random / 4294967295.0 + 0.5) ) - 2.0 ) * 1.732050808 * NOISE_AMPLITUDE;

The example given by mathman is the Box-Muller method, which is faster, but more difficult to understand.

http://en.wikipedia.org/wiki/Box-Muller_transform

Here's an excellent page with code for both methods:

http://www.dspguru.com/howto/tech/wgn2.htm

- Warren

 

[Physics_wiz]

Ok, so I made a small program in excel to test it, but it doesn't look right. Either I'm doing something wrong or excel's random number generator isn't good enough (probably the former).

Here's the code:

Sub mac()
With Sheets("Sheet1")

For counter = 1 To 1000

            For counter2 = 0 To 100
                Randomize
                U1 = Rnd
                Randomize
                U2 = Rnd
                V1 = 2 * U1 - 1
                V2 = 2 * U2 - 1
                S = V1 * V1 + V2 * V2
                If S >= 1 Then counter2 = 100
            Next
             
            X = Sqr(2 * Log(S) / S) * V1
            Y = Sqr(2 * Log(S) / S) * V2
            
            .Cells(counter, 1) = X
            .Cells(counter, 2) = Y
Next
End With
            
End Sub

This generates 2000 numbers in two columns that are supposed to be normally distrubuted with mean 0 and standard deviation 1. Right?

The problem is that the maximum number in the 2000 generated is .812241 and the minimum is -.82961. With a standard deviation of 1, I should see about 32% of the data outside of the range [-1, 1] but it looks like it's all in the range [-.8, .8]. What's going on here?

 

[Physics_wiz]

I found my mistake!

Here's how the code should look:

Sub mac()
With Sheets("Sheet1")

For counter = 1 To 1000

            For counter2 = 0 To 100
                Randomize
                U1 = Rnd
                Randomize
                U2 = Rnd
                V1 = 2 * U1 - 1
                V2 = 2 * U2 - 1
                S = V1 * V1 + V2 * V2
                If S < 1 Then counter2 = 100
            Next
             
            X = Sqr(-2 * Log(S) / S) * V1
            Y = Sqr(-2 * Log(S) / S) * V2
            
            .Cells(counter, 1) = X
            .Cells(counter, 2) = Y
Next
End With
            
End Sub

Now I'm getting 4 sigma events just like I should.

 

[mathman]

Suggestion: try coding the algorithm I proposed. You need log, sin, cos, and sqrt functions. However, you won't have an inner loop.