Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a function that (more or less) is supposed to select a small number m of random number from the range [1,n] (for some n >> 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 set as I'm willing to wait for (>100s 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.)

share|improve this question
    
You may want to look into computing discrepancy (here computing is a verb, discrepancy a noun), this is jargon for determining how far from the uniform distribution a given point set is. Sorry, that's all I can help you with. –  Tom Stephens Aug 14 '10 at 4:32
2  
You might also ask this question at stats.stackexchange. (I'm not saying that your question is inappropriate here.) –  Rasmus Aug 14 '10 at 12:41
    
How small is your m? –  Larry Wang Aug 14 '10 at 15:30
    
And how many sets of results can you feed the test? –  walkytalky Aug 17 '10 at 20:39
    
@walkytalky: see edit. –  BCS Aug 18 '10 at 14:36
add comment

4 Answers 4

up vote 6 down vote accepted

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.

share|improve this answer
    
The OP explicitly states that chi-square is too complicated, although that does seem a little like a counsel of despair... –  walkytalky Aug 17 '10 at 21:45
    
Actually, the n >> m part is what would rule out chi-square for me. Chi-square fails for low-population bins. –  Larry Wang Aug 18 '10 at 13:27
    
Since n > > m, use wide bins. –  John D. Cook Aug 18 '10 at 13:44
1  
If your number of bins is large, the chi square distribution is approximately normal and so you could look at just a mean and standard deviation. –  John D. Cook Aug 18 '10 at 15:45
1  
See page 26 of johndcook.com/Beautiful_Testing_ch10.pdf for help with the chi square test, especially when the normal approximation is appropriate. –  John D. Cook Aug 18 '10 at 15:51
show 1 more comment

You can use the Kolmogorov Smirnov test too. It is a non parametric test, and will work on many distributions - including Uniform. The advantage it has over other tests is that it looks at the whole distribution. Also it is fairly easy to use.

The idea is to compare the CDFs of the $H_0$ distribution with the observed empirical distribution, and find the maximum difference. This difference does not depend on the distribution (hence it is non-parametric), and depends only on $n$, the number of observations you are drawing. Then you look it up against a table to see how different it is from expected range of the difference.

Empirical CDF of your observations $\\{x_0,x_1,...,x_n\\}$ is $F_n(x)=\frac{1}{n}\sum_1^nI_{x_i\lt x}$. Then your test statistic will be $D_n=\sup|F(x)-F_n(x)|$. Assuming you sort your $x_n$'s in ascending order, and assuming your numbers come from Uniform[0,1] (wlg since you can scale them appropriately) it will be $D_n=\max_i(max(|x_i-\frac{i}{n}|,|x_i-\frac{i-1}{n}))$.

Once you compute that, it's only a matter of looking up table or using the right software. I recommend this site which has an excellent tool to compute KS along with many other tests. For KS, you need to select "Dn", put in the value you got, press the button, and assume interpret the result as it is truly uniform if P (computed in the form) < $\alpha$.

share|improve this answer
1  
That seems more complex than chi-squared. –  BCS Aug 20 '10 at 18:05
    
Yep, but it's an exact test (chi squared depends on asymptotic distribution), and looks at the entire distribution (chi squared requires forming arbitrary groups or buckets, and in a sense loses all information inside any particular bucket). –  KalEl Aug 20 '10 at 22:53
1  
@BCS the chi-square has very low power compared to the K-S. There are some possibilities which tend to have somewhat better power still, but the K-S is a substantially better choice and isn't sensitive to individual choices of numbers of bins etc. –  Glen_b Apr 10 '13 at 4:41
add comment

One issue with chi-square goodness-of-fit test is, because it operates on the empirical PDF and not CDF, the outcome depends on the bin size (class interval width) that you choose: if your data actually comes from a non-uniform distribution, a wider bin will create a bigger chance to reach the wrong conclusion (imagine the extreme of taking just one bin for all your data: perfectly rectangular histogram!). Also, if your bin counts are below 5 (as a rule), you need to combine bins together, which will also affect the outcome of the test. CDFs do not use binning and hence do not suffer from this problem. Kolmogorov-Smirnov test for CDF is rather crude, because it considers only one data point (= that of maximum deviation). A better one is Cramer-von Mises test, similar to K-S but instead integrates the differences between theoretical and empirical CDFs across the entire data range. There are other tests (Anderson-Darling, Shapiro-Wilks, etc.)

share|improve this answer
add comment

I am not at all sure that this would work, but it seems reasonable... (if it doesn't work, I'd like to know why)

We can very simply use Monte Carlo integration to approximate pi by setting up a known area and inscribing a circle in it, and sampling the entire area with a uniformly distributed sequence*, and considering the ratio of "hits" to the total number of "shots". (I elaborated on this slightly in this answer to another question.)

* I think the uniform distribution of points is necessary in order to guarantee that there is no bias toward any particular area of the sampling space.

If this is indeed the salient feature of uniformly distributed sequences in this context, then what would happen if we sampled with a non-uniformly distributed sequence? I presume that we would not approximate the digits of pi very well... If this turns out to be true, then you may throw your sequence at a Monte Carlo problem with a known solution and see how it does.

I have a quick Matlab script approximating pi using a 2-d square. In principle, this could be done in any dimension. If you just have a sequence of points (1-d) you could try to approximate the length of a given segment in an interval of known length. It also seems to me that the more points you have the better idea you will get to how far your points are from being uniformly distributed.

(Let me know if something didn't make sense here and I will try to clarify.)

share|improve this answer
    
I'm not following your proposed 1D case. OTOH running Monte Carlo on sqrt(1-x^2) for x in [0,1] should give pi/4 –  BCS Aug 18 '10 at 14:45
    
@BCS: I am pretty far out of my realm on this topic - thanks for the tip on $\sqrt(1-x^2)$ for $x \in [0,1]$. –  Tom Stephens Aug 18 '10 at 15:15
    
Approximating π is likely to be a very bad test: think of a 2-d generator which generates points only in the top-left quadrant of the square. Because of the symmetry of the circle this would still give the right value of π. Trying to estimate the length of various intervals in 1-d is a good idea, but the chi-squared test suggested by others is in fact a systematic way of doing that. –  Jyotirmoy Bhattacharya Aug 19 '10 at 4:22
add comment

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.