How do I know it's a fair PRNG?

I’ve never been afraid of math and I’ve done some reading on pseudorandom number generators, but playing a recent video game made me realize that I have no idea how to tell whether something is statistically sound.

Let me give a simple example. In Puzzle Quest you match tokens. One such token is a skull. I have a piece of equipment that promises me a 50% chance of generating a skull on the board at the start of my turn.

Having played a while, I lamented that I wasn’t keeping records to see how accurate the 50% claim was. (It’s a question of my own interest, not doubting the developers.) But then I thought, “Well, what would I do with it? Suppose it happens that I got 23 skulls over 100 turns. This is possible, even if the overall chance of a skull on the next turn is 50%.” I realized that there was basically no way, short of access to the algorithm itself, to demonstrate that it was or was not fair.

So how are PRNG tested? Is there any way I could test one without access to the algorithm?

Basically, the best you can do by testing a PRNG in a black box is grow progressively more certain that it’s flawed, you can’t prove it.

For something like this, your PRNG is almost certain to be good enough. Problems in PRNGs usually only show up when you look for subtle correlations between results, not just counting the number of successes out of a large number of trials.

That said, for your particular question, if you take n trials, then your expected number of successes should be (of course) n/2, with a standard deviation of sqrt(n)/2. So for instance, if you tried it 100 times, you should get about 50 ± 5 skulls, and if you tried it a million times, you should get 500,000 ± 500 skulls. If your actual result is far outside of this range, then there’s reason to suspect that the null hypothesis (that the PRNG is fair) is false.

That’s a good point, I don’t know why I didn’t consider it. Thanks.

This wouldn’t apply to your situation but if you have the data from a PRNG, you can run statistical checks on it. Here is a program that does that and has a good description of different tests it performs.

Cool. I doubt I could ever gather enough data just through playing to constitute a significant sample, but that’s a cool program regardless.

From what I can remember from statistics class I think you make a Chi-square test on the distribution. We made a very very simple linear congruential generator and tested it with a Chi-square test. I don’t remember the details on this, but you can probably find information about it online. Implementing it wasn’t very difficult, if I remember correctly.

How many data points would constitute a sufficient sample?

That’s the first check, but it’s not sufficient. It shouldn’t be too much trouble to create a Markov chain whose stationary distribution is uniform over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} but whose observations are not independent.