Statistics – Is There a Simple Test for Uniform Distributions?

statistics

I have a function that (more or less) is supposed to select a small number $m$ of random numbers from the range $[1,n]$ (for some $n \gg m$) and I need to test that it work. Is there an easy to implement test that will give good confidence that it is working correctly? (For reference the full on chi squared test is not simple enough.)

Edit:

  • $m$ in $[5,500]$, $n$ is small enough I can use normal int/float types for most math.
  • I can get as many sets as I'm willing to wait for ($>100$s per second)

The reason I'm looking for something simple is that the code I'm checking isn't that complicated. If the test code is more complex than the code under test, then the potential for the test being wrong becomes a real problem.

Edit 2:

I took another look at Chi-squared and it's not as bad as I remembered… as long as I have a fixed number of buckets and a fixed significance threshold. (Or a canned CDF, and I don't think I do.)

Best Answer

You could use a chi square test. Basically, this tests whether the number of draws that fall into various intervals is consistent with a uniform random distribution. See Knuth's TAOCP volume 2, Seminumerical Algorithms for an explanation of the chi-square test.

Update: If the chi square test is too complicated, you could plot a histogram of your output and eyeball it to see if it looks uniform. But if you'd like to quantify whether it's even enough, that's exactly what a chi square test is. The test will also tell you whether the data are too evenly spread out, i.e. not random enough.

Related Question