3

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.

5
  • 1
    "If a "good" PRNG (such as an existing RNG from a popular programming language's main library)" -- those often suck Feb 28, 2013 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. Feb 28, 2013 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. Feb 28, 2013 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? Feb 28, 2013 at 16:03
  • @CodesInChaos The latter. I can do the transformation, but I like to test things to check I did them right. Feb 28, 2013 at 21:37

2 Answers 2

3

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.

2
  • 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, 2013 at 17:20
  • @JanDoggen Thankfully, software makes it really easy. Feb 28, 2013 at 18:40
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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