Chi Squared

A simple statistical test that can be useful for testing the randomness of a distribution:

Generate a uniform distribution d[0..r] using the (suspected) PseudoRandomNumberGenerator you want to test and doing N runs. N should be greater than say 10*r.

The average fill in each slot in d is f = N/r

ChiSquared = Sum[0<=i<r]((d[i]-f)^2)/f

If ChiSquared is within 2*Squareroot(r) of r 90% of the time, the generator passed this test.

Note that being within these limits 95% of the time if just as bad as only being within them 85% of the time.

This test is necessary but not sufficient - it is easy to construct distributions that pass the test and are obviously not random. (For example, mod r of each of the numbers from 1 to N.)

-- JanLarsen

[Note that squaring avoids negative signs, but other powers (or absolute value) would also do that. Some books give the impression that squaring is used merely to keep the mathematics simple.]

Squaring is actually natural, although you're right; most probability books don't explain it very well. Consider the simplest version of the random walk. We have a random variable X: P[X = +1] = P[X = -1] = 1/2. Flip a fair coin, and go 1 step left or right depending on whether the coin turns up heads or not.

Consider a sequence of identically distributed random variables X_1, X_2, ..., X_n, ..., all with the same distribution as X. Define S_n = X_1 + X_2 + ... + X_n.

What is the expected value of S_n^2? We use induction to show that E[S_k^2] = k.

  k = 1: E[S_1^2] = E[X_1^2] = 1/2 * 1^2 + 1/2 * 1^2 = 1.

  Induction: Assume E[S_k^2] = k.

  E[S_(k+1)^2] = E[(S_k + X_(k+1))^2]
               = 1/2 E[(S_k + 1)^2] + 1/2 E[(S_k - 1)^2] since S_k and X_(k+1) are independent
               = 1/2 E[S_k^2 + 2 S_k + 1] + 1/2 E[S_k^2 - 2 S_k + 1]
               = E[S_k^2] + 1
               = k+1.

So, the distribution of the distance from S_n to 0 is about the square root of n. This is where squares come in.

One needs more than that. You introduced squares, and ended up with a square root. Hardly a big surprise. One needs to know that 2 is a better power to use than 4 or 2.04, say, as it's nearly always 2 that is chosen, regardless of the precise context.

The chi-square statistic applies to gaussian probability distributions, where the probability of obtaining a value of x when the mean of the underlying distribution is xMean is proportional to exp(-(x-xMean)^2). The 2 in the chi-square comes from that 2 in the exponential describing the probability distribution. So, when are gaussian statistics appropriate? They are when there are a large number of similar-magnitude effects that cause deviation from the mean (like the random walk example above). When that assumption is violated, and the so-called Central Limit Theorem no longer applies sufficiently well, you'll need to apply a different form of the chi-square statistic that takes the particular conditions into account. How to do this is described in advanced statistics textbooks. -- DaveVanBuren

It seems to me the use of powers of two is the SimplestThingThatCouldPossiblyWork. Two is the easiest power to calculate (if you ignore the trivial 0 and 1). Remember that a lot of statistics was invented before calculators and computers.

In some cases, a power of 4 has a different meaning. The kurtosis is calculated as E[y^4]-3 and measures the "sharpness" of the distribution. Distributions with a positive kurtosis have a sharper peak. The variance, working at a power of 2, doesn't measure this.

Thanks. I think y needs to have a variance of 1 for your expression to be right. I suspect that 4 is much more of a convenience choice (for sharpness) than 2 is for other tests.

See ImprovingRandomNumbers