31
$\begingroup$

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.)

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Tom Stephens
    Aug 14, 2010 at 4:32
  • 3
    $\begingroup$ You might also ask this question at stats.stackexchange. (I'm not saying that your question is inappropriate here.) $\endgroup$
    – Rasmus
    Aug 14, 2010 at 12:41
  • $\begingroup$ How small is your m? $\endgroup$
    – Larry Wang
    Aug 14, 2010 at 15:30
  • $\begingroup$ And how many sets of results can you feed the test? $\endgroup$
    – walkytalky
    Aug 17, 2010 at 20:39
  • $\begingroup$ @walkytalky: see edit. $\endgroup$
    – BCS
    Aug 18, 2010 at 14:36

6 Answers 6

Reset to default
27
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ The OP explicitly states that chi-square is too complicated, although that does seem a little like a counsel of despair... $\endgroup$
    – walkytalky
    Aug 17, 2010 at 21:45
  • $\begingroup$ Actually, the n >> m part is what would rule out chi-square for me. Chi-square fails for low-population bins. $\endgroup$
    – Larry Wang
    Aug 18, 2010 at 13:27
  • 1
    $\begingroup$ Since n > > m, use wide bins. $\endgroup$
    – John D. Cook
    Aug 18, 2010 at 13:44
  • 2
    $\begingroup$ 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. $\endgroup$
    – John D. Cook
    Aug 18, 2010 at 15:45
  • 4
    $\begingroup$ See page 26 of johndcook.com/Beautiful_Testing_ch10.pdf for help with the chi square test, especially when the normal approximation is appropriate. $\endgroup$
    – John D. Cook
    Aug 18, 2010 at 15:51
25
$\begingroup$

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$.

$\endgroup$
9
  • 3
    $\begingroup$ That seems more complex than chi-squared. $\endgroup$
    – BCS
    Aug 20, 2010 at 18:05
  • 5
    $\begingroup$ 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). $\endgroup$
    – KalEl
    Aug 20, 2010 at 22:53
  • 5
    $\begingroup$ @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. $\endgroup$
    – Glen_b
    Apr 10, 2013 at 4:41
  • 2
    $\begingroup$ @astabada The answer you link to there is actually mine (how did your simulation go?). Relative power in the KS test depends on the alternative under consideration. The issue considered in that answer is one in which it exhibits low power, but the comments above apply against more typical alternatives: (i) the K-S (overall) has much better power than the chi-square, and (ii) there are better tests still. Numerous studies across a host of alternatives of interest do support both claims. Given specific types of alternatives, you can usually outdo K-S by tailoring the test. $\endgroup$
    – Glen_b
    Jan 29, 2015 at 20:43
  • 2
    $\begingroup$ @astabada Indeed, reread the second sentence of that answer you link to, which summarizes the situation - i.e. your question there happens to relate to a particular kind of alternative it isn't very sensitive to (compared to say the Anderson-Darling test, for example). More generally it has reasonable power. $\endgroup$
    – Glen_b
    Jan 29, 2015 at 20:51
4
$\begingroup$

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.)

$\endgroup$
4
$\begingroup$

A good way to test for this is to note that the CDF for any continuous random variable transforms it to a uniform distribution, so you can transform a uniform distribution by the inverse CDF to get any distribution you like, and then compute statistics designed to test for that distribution.

For instance, in section 2.3, p. 679 of Cook, Gelman & Rubin they describe how to do this to transform a hypothetically uniform distribution to the standard normal, and then use the fact that the sum of squares of the normal follow a χ$^2$-distribution with N degrees of freedom, where N is the number of observations

$\endgroup$
0
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – BCS
    Aug 18, 2010 at 14:45
  • $\begingroup$ @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]$. $\endgroup$
    – Tom Stephens
    Aug 18, 2010 at 15:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jyotirmoy Bhattacharya
    Aug 19, 2010 at 4:22
0
$\begingroup$

The kurtosis excess measure of a uniform distribution is -1.2, so perhaps measuring the kurtosis and assuring that it is close to that value could be a quick and easy way to compute if your distribution is uniform.

See:

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .