3
$\begingroup$

The question arises in a cryptographic context where one wants to check a source for randomness. In an experiment it is taken $n$ discrete values among $m$ (e.g. $n=128$, $m=16$ ). The null hypothesis is that these values drawn are independent and uniformly distributed.

It is counted the number $O_i$ of occurrences of each of the $m$ values. It thus holds $n=\sum O_i$. A test is built from the values of the $O_i$ alone (which implies that the test mostly is about "uniformly distributed" rather than about "independent").

We are interested only in tests parametrized for low probability $\epsilon$ of wrongful rejection when the null hypothesis holds, e.g. $10^{-12}\le\epsilon\le10^{-6}$.

In the Pearson's test, it is computed the quantity: $$\chi^2=\sum\frac mn\left(O_i-\frac nm\right)^2$$ and the null hypothesis is rejected when $\chi^2$ is above some bound. How to choose that bound for low $\epsilon$ is discussed there.


Instead, assume it is used something inspired by the formula for Shannon entropy per bit (with confusion between probability and observed frequency): $$H=\frac1{\log_2(m)}\sum_{O_i\ne0}\frac{O_i}n\,\log_2\left(\frac n{O_i}\right)$$ and the null hypothesis is rejected when $H$ is below some bound $x$ slightly below $1$, e.g. $x=0.9$ (notice that should it happen $O_i=n/m$ for all $i$, then $H=1$ and that's its maximum).

  1. Has that test been studied?
  2. How does it qualitatively compare to Pearson's test?
  3. What's a relation between $\epsilon$ and $x$?
$\endgroup$
1
  • 1
    $\begingroup$ Just as a minor correction, the concept of "one-sided" vs "two-sided" does not apply to Pearson's goodness of fit test. The null hypothesis is rejected for large (not small) values of $\chi^2$, but the alternative hypothesis being tested is completely generally in terms of the parameters being compared (multi-sided one might say). $\endgroup$ Jun 29, 2020 at 0:32

1 Answer 1

9
+100
$\begingroup$

I think you are trying to rediscover the G-test or likelihood ratio test. Your $H$ is a scaled version of the G statistic, which is defined as $$G=2\sum_{i=1}^m O_i \log(O_i/E_i)$$ with $E_i=n/m$.

$G$ has been studied as a statistical test since Fisher's work on maximum likelihood estimation in the 1930s, although it has only been called "G" since 1957 (Woolf, 1957). $G$ can be derived as the likelihood ratio test statistic for the null hypothesis that all the categories have equal probabilities vs the alternative that all or some probabilities are unequal. The observed counts $O_i$ can be viewed as independent Poisson variables or as a multinomial vector---both models lead to the same likelihood ratio test.

$G$ is asymptotically equal to the Pearson $\chi^2$ statistic given in your question but is sometimes preferred when the counts are small. Simulations show that the choice between the two isn't clear.

$G$ is asymptotically $\chi^2_{m-1}$ distributed under the null hypothesis of uniformity as $n\rightarrow\infty$ for fixed $m$. Dunn & Smyth (2018) show that the asymptotic distribution for $G$ can be proved either by the Central Limit Theorem (CLT) applied to the individual counts $O_i$ or by an alternative theorem derived from the saddlepoint approximation.

You are correct that $G$ is related to Kullback–Leibler divergence or Shannon entropy.

$G$ is also known as the deviance in generalized linear model theory. For example, in this simulation, the value of G is 13.964.

> set.seed(20200628)
> m <- 16
> n <- 128
> y <- sample(1:m, n, replace=TRUE)
> O <- tabulate(y)
> fit <- glm(O~1, family=poisson)
> anova(fit)
Analysis of Deviance Table

Model: poisson, link: log

Response: O

Terms added sequentially (first to last)


     Df Deviance Resid. Df Resid. Dev
NULL                    15     13.964

Alternatively, here is an extreme example where $O_{16}$ is ten times ther other counts, so the null hypothesis should clearly be rejected:

> O <- rep(10,16)
> O[16] <- 100
> n <- sum(O)
> E <- n/16
> G <- 2*sum(O*log(O/E))
> G
[1] 237.3735
> pchisq(G, df=15, lower.tail=FALSE)
[1] 4.90601e-42

In this case, G$=$237, which yields the tiny p-value $4.9\times 10^{-42}$.

Tail probabilities

You seem to interested in decisions using extremely small $\alpha$-levels (type I error rates) below $10^{-6}$, far beyond what would be used in most statistical contexts. For $m=16$ and $n=128$, the $\chi^2_{m-1}$ distributional approximation for G is excellent by normal statistical standards but will still underestimate the very small tail probabilities. You could improve the approximation materially by computing the null expectation of $G$ numerically and replacing $G$ by $G^*=[(m-1)/E(G)]G$. This idea is my own research, based on the idea of Bartlett correlations.

If even that approximation is not good enough for your cryptography applications, then I think you would have to explore completely different goodness of fit statistics for which exact probability computations are possible. Exact probability calculations are not at all tractable for the $G$ statistic.

References

Woolf, B. (1957). The log likelihood ratio test (the G-test). Annals of Human Genetics 21(4), 397-409. [The original paper that introduced the terminology G-test for the likelihood ratio statistic computed from a multinomial random variable.]

Dunn, PK, and Smyth, GK (2018). Generalized linear models with examples in R. Springer, New York, NY. https://doi.org/10.1007/978-1-4419-0118-7 [Proves asymptotic chisquare distribution for $G$ (or any residual deviance) using the saddlepoint approximation.]

https://en.wikipedia.org/wiki/G-test

$\endgroup$
7
  • $\begingroup$ Many thanks. The only point remaining not fully covered is 3: how to set the limit of the test for low probability $\epsilon$ (of $\alpha$, or $p$-value) of wrong rejection. That's not trivial for Pearson's / $\chi^2$ either, and with $\epsilon<10^{-6}$ I'm far off the usual charts. $\endgroup$
    – fgrieu
    Jun 29, 2020 at 10:00
  • $\begingroup$ I'm not following what problem you are seeing here. Any statistics program will do probability calculations for the chisquare distribution. E.g., the $10^{-6}$ p-value cutoff with $m=16$ is given in R by qchisq(1e-6, df=15, lower.tail=FALSE), which is 56.49344. $\endgroup$ Jun 29, 2020 at 11:50
  • $\begingroup$ @fgrieu Or going the other way around, a statistic of $G=70$ (say) would correspond a p-value of pchisq(70, df=15, lower.tail=FALSE), which is $4.5\times 10^{-9}$. $\endgroup$ Jun 29, 2020 at 11:56
  • $\begingroup$ Using the $\chi^2$ function to decide bounds in the Pearson test is an approximation that becomes seriously invalid for low $\epsilon$ and moderate $n/m$. This is discussed at length in the question's second link (but the $\epsilon$ there is different). I wish I knew if the same curse applies to that test (or the equivalent G-test). $\endgroup$
    – fgrieu
    Jun 29, 2020 at 12:20
  • 1
    $\begingroup$ @fgrieu This is considered an excellent approximation in statistical contexts. As I already, said, there is no exact distribution. Of course the chisquare approximation will beome worse in the extreme tails of the distribution, that is just the reality in asymptotic statistics. All asymptotic approximations become worse in the extreme tails of the distribution. If you're not willing to tolerate approximations, then you need to break up the problem in some way so you can use exact tests like the binomial or hypergeometric distributions. $\endgroup$ Jun 5, 2022 at 20:37

Your Answer

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

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