# When does a random test fail?

I must implement some Chi Square Test to test the randomness of "my" implementation, but I can't understand what this tests really say.

The tests are different but what I always do is: divide in different categories, calculate the probability to fall in these categories and then calculate this number:

$v = \sum_{i=0}^{k} \frac{(x_k - p_k)^2}{p_k}$

Where k is how many categories are, $x_k$ is how many elements in kth category I've counted and $p_k$ is probabily of the kth category multiplied by the number of total instances.

I know that $v$ should be distributed like $\chi^2$ of $k-1$ freedom degree; so i calculate many $v$ and see where they are. For example I see that almost 80% is in $(\chi^2_{.10}, \chi^2_{.90})$. But then? What can I say?

For example this is an output of one of my test:

Test Gap:
Categories: 11. Freedom Degree:  10. Gaps: 10000. Iterations: 10000.
[.10,.90): 8017.              Expected :8000.0
[.01,0.05)U[.95,.99): 772.    Expected :800.0
[.05,0.10)U[.90,.95): 1000.   Expected :1000.0
[0,0.01)U(.99,1]: 211.        Expected :200.0


I know that I cannot say "This is true randomness!", but.. well, can I say that I passed the test? Why? Should I repeat the test other times and...?

Thank you!

-
How do you calculate $p_k$? –  Aniko May 4 '12 at 12:42
It depends on the test. –  Fabio F. May 4 '12 at 12:53

If I understand correctly, then you can calculate your statistic $v$ multiple times. In that case you are looking for a one-sample test for evaluating whether the $v_i$ values that are generated by using your implementation many times, follow a $\chi^2_{k-1}$ distribution. So you consider $v_i$ your data, not the $x_{ki}$. The Kolmogorov-Smirnov test can be used for this. It looks at the largest vertical deviation between the observed cumulative distribution function and the theoretical one.
@FabioF, it should rejected $5\%$ of the time when the null hypothesis is true - that's the definition of the significance level, $\alpha$. –  Macro May 4 '12 at 13:20