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

enter image description here

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!

  • $\begingroup$ How do you calculate $p_k$? $\endgroup$ – Aniko May 4 '12 at 12:42
  • $\begingroup$ It depends on the test. $\endgroup$ – 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.

| cite | improve this answer | |

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

| cite | improve this answer | |
  • $\begingroup$ So? It should be rejected 5% of the time? $\endgroup$ – Fabio F. May 4 '12 at 12:53
  • $\begingroup$ @FabioF, it should rejected $5\%$ of the time when the null hypothesis is true - that's the definition of the significance level, $\alpha$. $\endgroup$ – Macro May 4 '12 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.