3
$\begingroup$

I have a third party random number generator with a period approximately greater than $63*(2^{63} - 1)$ which generates numbers in the range $[0,2^{32}-1]$, ie $2^{32}$ different numbers. I've made some slight modifications and wish to verify its distribution remains uniform. I am using Pearson's chi-squared test for fit of a distribution, hopefully correctly, without knowing much about it:

  1. Divide $1000*2^{32}$ observations across $2^{32}$ different discrete cells (I figure the number of observations $n$ should be $5*2^{32} \lt n \lt 63*(2^{63} - 1)$, or, $5*\text{range} \lt n \lt \text{periodicity}$, using the five-or-more-rule, to gain decent confidence). The expected theoretical frequency $E_i = 1000*2^{32} / 2^{32} = 1000$.

  2. the reduction in degrees of freedom is 1.

  3. $x^2 = \sum_{i=0}^{2^{32}-1}(O_i - E_i)^2/E_i$.

  4. degrees of freedom = $2^{32} - 1$.

  5. lookup the p-value of a chi-squared ($x^2$) distribution given $2^{32} - 1$ degrees of freedom.

    As far as I can tell, no chi-squared distribution exists for that many degrees of freedom. What should I do?

  6. select a confidence significance value $c$ such that $p > c$ signifies the distribution is probably uniform. I have a large sample size but since I'm unsure of its relation to p-value (increased sampling reduces errors but significance value represents a ratio in the types of errors) I think I'll just stick with the standard value 0.05.

Edit: actual questions italicized above, and enumerated below:

  1. How to get a p-value?
  2. How to select a significance value?

Edit:

I've asked a follow-up question at chi-squared goodness-of-fit: effect size and power.

$\endgroup$
6
  • 1
    $\begingroup$ A chi-square distribution exists for any positive degrees of freedom. Do you mean "I can't find tables for really large d.f." or "some function I want to call won't take arguments that large" or something else? Note that failing to reject the null doesn't of itself imply that "the distribution is probably uniform" $\endgroup$
    – Glen_b
    Dec 27, 2015 at 6:29
  • $\begingroup$ I can't find tables for really large d.f. $\endgroup$
    – user19087
    Dec 27, 2015 at 7:40
  • $\begingroup$ Isn't there little difference between the two? A p-value reflects how well the null fits, and though it doesn't imply another hypothesis won't fit better, its point is to highlight observations which probably don't fit the null (though not necessarily; could be an outlier). So conversely, for the sake of practicality I have to assume that all other observations (failing to reject the null) do imply "the distribution is probably (though not necessarily; could be an outlier) uniform". $\endgroup$
    – user19087
    Dec 27, 2015 at 8:20
  • $\begingroup$ I'm just pointing out there is not a "maybe" middle ground in an either-or test, nor does either rejecting or failing to reject imply any hypothesis is true. And changing the confidence level just changes the ratio of false positives and false negatives. $\endgroup$
    – user19087
    Dec 27, 2015 at 8:20
  • $\begingroup$ If the number of degrees of freedom is ''very large'' then $\chi^2$ can be approximated by a normal random variable. $\endgroup$
    – user83346
    Dec 27, 2015 at 8:38

1 Answer 1

7
$\begingroup$

A chi-square with large degrees of freedom $\nu$ is approximately normal with mean $\nu$ and variance $2\nu$.

In this case, ten billion degrees of freedom is plenty; unless you're interested in high accuracy at extreme p-values (very far from 0.05), the normal approximation of the chi-square will be fine.

Here's a comparison at a mere $\nu=2^{12}$ -- you can see that the normal approximation (dotted blue curve) is almost indistinguishable from the chi-square (solid dark red curve).

enter image description here

The approximation is far better at much larger df.

$\endgroup$
15
  • 1
    $\begingroup$ That's a graph of $x^2$ and not $x$, right? And with such small p-values, what confidence level should I choose? $\endgroup$
    – user19087
    Dec 28, 2015 at 18:32
  • $\begingroup$ The drawing is simply the density of a chi-square random variate ($X$), which density is a function of $x$. You're doing a hypothesis test, so you don't have a confidence level. You do have a significance level but you don't choose that after you see a p-value, you choose that before you start. $\endgroup$
    – Glen_b
    Dec 28, 2015 at 23:56
  • 1
    $\begingroup$ Yes, that is the graph of the PDF of the $x^2_k$ distribution. Given the name of Pearson's test statistic ($x^2$), I wasn't sure if $x$ references the x-axis (in which case I should take the square root of the statistic first) or the distribution name (in which case the statistic maps directly to the axis). Empirical testing of $\text{p-value} = 1 - CDF$ compared to tables confirms the latter. $\endgroup$
    – user19087
    Dec 30, 2015 at 2:37
  • $\begingroup$ The p-value of $x^2_k$ is calculated via the CDF using: $1 - \frac{1}{\Gamma(\frac{k}{2})} * \gamma(\frac{k}{2}, \frac{x}{2})$, which involves computing a power series with extremely large numbers. $\endgroup$
    – user19087
    Dec 30, 2015 at 2:38
  • $\begingroup$ At large k-values, the $x^2_k$ distributions approximates the normal distribution, so the CDF of the normal distribution is used: $1 - \frac{1}{2} \left[ 1 + \text{erf$\left( \frac{x - k}{2 * \sqrt{k}} \right) $} \right]$ as described by the answer ($\sigma$ and $\mu$ substituted as required). This involves computing a power series as well, though smaller numbers are involved and erf is a standard component of many standard libraries. $\endgroup$
    – user19087
    Dec 30, 2015 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.