When does a random test fail?

Question

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!

Answer 1

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.

Answer 2

This is classical hypothesis testing. The null hypothesis state that the data are randomly placed in the categories. If the null hypothesis is true V will ASYMPTOTICALLY have the stated chi square distribution (this is an approximate (not an exact) test). v is your test statistic. You reject randomness if the value of v is large relative the reference chi square distribution which in your case would mean the test for randomness fails. Often the 5% level is chosen as the cutoff point for rejection which means you would compare the observed v to the 95th percentile of the chi square distribution (reject if it is larger).