Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

There are plenty of questions around regarding random number generation, but I couldn't find anything that exactly matched my question. Apologies if I missed one.

Most random number generators in software tend to have flat distribution - in the given range, any number is as likely to come next as any other (more or less). This is obviously the intention, because anything other than a flat distribution isn't entirely random because some numbers are more likely than others. However, there are times when a flat distribution is not desirable. For example, when building a game, it is often necessary to model real-world scenarios, many of which have a normal (bell-curve) distribution.

If a "good" PRNG (such as an existing RNG from a popular programming language's main library) is fed into a simple equation, such as the equation for a bell curve, or a sine wave, or some other distribution, how far can we assume that the resulting PRNG is also "good"? Most of the tests for PRNGs test whether the system is purely random, so they won't work on this system. Is it just a matter of counting outputs over a long time and seeing how well they fit the desired distribution, or is there a simpler (eg. analytical or algebraic) way to check this?

Any help would be appreciated.

share|improve this question
1  
"If a "good" PRNG (such as an existing RNG from a popular programming language's main library)" -- those often suck –  CodesInChaos Feb 28 '13 at 9:26
    
I don't see how "analytical or algebraic" will help you. If you use a standard formula, that formula is probably supported by a mathematical proof. The question is if your code implements the formula correctly. –  CodesInChaos Feb 28 '13 at 9:29
    
@CodesInChaos What I meant is some way to algebraically prove the resultant distribution based on the provided distribution from the underlying PRNG and the formula it's put through, rather than statistically recording outputs over a number of iterations. –  anaximander Feb 28 '13 at 9:47
2  
Do you want a formula that transforms uniform random numbers into a specific distribution? Or do you want to know how to verify if an implementation of such a formula is correct? –  CodesInChaos Feb 28 '13 at 16:03
    
@CodesInChaos The latter. I can do the transformation, but I like to test things to check I did them right. –  anaximander Feb 28 '13 at 21:37

2 Answers 2

You need to grab a bunch of numbers and see if they fit the desired curve. You did the algebra when you created the flat->curve transform equation. Doing more algebra isn't going to help you prove that you already know how to do algebra. You need some other way to prove that you created the equation correctly, and that you implemented it correctly.

The most straightforward way to check it is just to grab a bunch of numbers and plot them.

share|improve this answer
    
And in the case of e.g. verifying that your data fit a normal distribution, you would do a Chi-square test. For other distribution, other tests apply. But then you're going deep into statistics/stochastics and I don't remember much of that fro my university days ;-) –  Jan Doggen Feb 28 '13 at 17:20
    
@JanDoggen Thankfully, software makes it really easy. –  Jonathan Rich Feb 28 '13 at 18:40

If the bell curve is implemented properly (e.g. doesn't distort the nature of the PRNG), then the generated bell curve PRNG will be as good as the PRNG it was generated from.

Also, due to the nature of the bell curve function, the translation should be bidirectional (you should be able to turn a bell curve PRNG into a flat PRNG, assuming real values). If it is not bidirectional, you did something wrong.

You might want to cross-post this to theoretical cs. You might get a cooler answer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.