How to evaluate chi squared result?

Question

I've been recently working on a (supposedly) TRNG. I'm still at the beginning of the project, so it is certainly not cryptographically secure yet, for now I'm just playing around. In fact, I've already discussed the project and the chi square results here in question: Random number generator issue.

At this early stage I'm using ent to see if there is any gross issue, later I'll move to a more accurate test suite.

One of the ent measured parameters draw my attention: the chi-squared. After doing some research I've understood that this value basically says how much, in a set of values, their frequencies match with the theoretical expected frequency. $$\chi^2=\sum_{i=1}^n\frac{(o_i-e_i)^2}{e_i}$$ where $o_i$ is the actual frequency and $e_i$ is the theoretical frequency.

And that's fine, but how do I understand which would be my optimal value? For my particular case (values ranging from 0 to 255, uniform distribution) I'm using 254.3 as a reference "optimal value" from ent's manual. (I could be wrong on this, ent manual explicitly states only that for true randomness i should expect my percentage value to be between 10 and 90%, which is centered to 50%, which gives a value of 254.3)

Let's say everything is perfect, I'd have $o_i$ which is equal to $e_i$, so the difference would be 0 for every $i$, they should add up to 0 and my optimal chi-squared would be 0.

But according to ent my optimal chi-squared is the above mentioned 254.3.

How I should calculate my optimal chi-squared for a different distribution (e.g. the normal distribution) or for a different range of values (e.g. 0 to 65535) ?

Answer 1

Testing the frequency of bytes produced by an ideal (uniform) random generator per question's method with $1200$ samples or more gives a $\chi^2$ that varies typically by few dozens around the average, $255$. It should be below $254.334$ for 50% of experiments, and the most likely values those closest to $253$.

---

For a good uniform random sequence of bytes, and "enough" samples, the distribution of $\chi^2$ computed as in the question has a well-studied distribution: the $\chi^2$ distribution with $2^8-1=255$ degrees of freedom, with this Probability Density Function:

The mean is $255$ (that's what you obtain by averaging the $\chi^2$ of many experiments). The median is $\approx254.334$ (the $\chi^2$ is less than this for 50% of experiments). The mode is $253$ (that's the most likely value, maximizing the PDF).

The standard deviation is $\sigma=\sqrt{510}\approx22.58$. Because the PDF is close to a normal, the 68–95–99.7 rule applies: that gives the probability (in percent) to be one, two and three $\sigma$ from the mean. Again that's with "enough" samples. A rule of thumb tells that about $5$ samples per expected value (thus like $1200$ samples) starts to be enough when reasoning at up to $2\sigma$. More sample usually help (I wish I knew how to more rigorously choose the minimum number of samples).

The Cumulative Density Function $\displaystyle\operatorname{CDF}(x)=\int_0^x\operatorname{PDF}(u)\ du$ is:

That tells the expected proportion of experiments (for a uniform random sequence) where the computed $\chi^2$ is less than a certain value.

We have a 0.05% chance that the $\chi^2$ is less than $187.171$, and 0.05% chance that it is above $335.917$. Thus in only about one experiment out of 1000 will the $\chi^2$ will be out of that range, for a truly uniform random sequence, and "enough" samples.

In particular, a generator that consistently gives low $\chi^2$ is not random!

---

When we generalize to different tests with a random variable taking one out of $n\ge2$ different outcomes with expected frequencies $e_i$ and $\displaystyle1=\sum e_i$, and the number of samples is at least about $5/\min(e_i)$ (enough for a minimum of $5$ expected samples for each value), then the distribution of $\chi^2$ is the $\chi^2$ distribution with $k=n-1$ degree(s) of liberty.

The shape of the Probability Density Function vary with $k$.

The mean is $k$, the median is about $k(1-2/9k)^3$, the mode is $\max(0, k-2)$.
The variance is $\sigma=\sqrt{2k}$, but for low $k$ computations or tables (rather than estimations based on $\sigma$ and a normal approximation) are necessary.

The shape of the Cumulative Density Function vary with $k$:

Answer 2

Here's a procedure to sample an integer in {1, 2, 3, ..., 20} uniformly at random:

Procedure A:

1. Fairly roll a d20.
2. Read the face.

This is a standard technique taught to children early in their initiation into the satanic rituals of Dungeons and Dragons.

Here's another procedure to sample an integer in {1, 2, 3, ..., 20} uniformly at random:

Procedure B:

1. Fairly roll two d6's; call the faces $f_0$ and $f_1$.
2. Compute $r = f_0 + 6 (f_1 - 1)$.
3. If $r > 20$, go back to step (1).

This is an instance of a slightly more advanced technique called rejection sampling. It is a popular technique among teenagers seeking mates under 20, and while it is not guaranteed to complete in finite time, the average number of trials this instance takes to complete is less than two, and the probability of success after $n$ trials is exponential in $n$, though in cases of high rejection rates it occasionally does lead some of the teenagers away from normal society into the aforementioned satanic rituals.

Here's another procedure to sample an integer in {1, 2, 3, ..., 20} uniformly at random:

Procedure C:

1. Fairly flip a coin $n = 10000$ times.
2. Count the numbers $n_0$ of heads and $n_1$ of tails.
3. Compute $$\chi^2 = \frac{(n_0 - n/2)^2}{n/2} + \frac{(n_1 - n/2)^2}{n/2}.$$
4. Round $20\cdot F(\chi^2)$ up to the next integer, where $F$ is the cumulative distribution function of the $\chi^2$ distribution with one degree of freedom.

This last procedure may appear to be a bit of a head-scratcher. But I assure you that these all have the same distribution—in the frequentist sense that the expected fraction of each outcome in an iterated experiment is always 1/20, and in the Bayesian sense that from the information I have given you about how I produce a single outcome, your state of knowledge weighs each option with equal probability 1/20.

Now consider a variant of the third procedure, where instead of flipping a coin, we do:

Procedure D:

1. Fairly roll a d6 $n = 10000$ times.
2. Count the numbers $n_0$ of outcomes that are 6, and $n_1$ of outcomes that are less than 6.
3. Compute $$\chi^2 = \frac{(n_0 - n/2)^2}{n/2} + \frac{(n_1 - n/2)^2}{n/2}.$$
4. Round $20\cdot F(\chi^2)$ up to the next integer, where $F$ is the cumulative distribution function of the $\chi^2$ distribution with one degree of freedom.

This is not a procedure to sample an integer in {1, 2, 3, ..., 20} uniformly at random—it is strongly biased toward giving 20. (Try it! Unless your name is Raphael Weldon, however, I suggest you write a computer program to simulate it.)

Note that steps C3/C4 are the same as steps D3/D4. These steps are part of what is called a $\chi^2$ test. We can use this to try distinguish a black box containing uniform gremlins who perform steps C1 and C2, reporting 0 for each heads and 1 for each tails, from a black box containing biased gremlins who perform steps D1 and D2, reporting 0 for each 6 and 1 for each non-6, as follows:

$\chi^2$ test to distinguish uniform from biased gremlin boxes:

1. Count the number $n_0$ of times the gremlins report 0, and the number $n_1$ of times the gremlins report 1.
2. Compute $$\chi^2 = \frac{(n_0 - n/2)^2}{n/2} + \frac{(n_1 - n/2)^2}{n/2}.$$
3. Round $20\cdot F(\chi^2)$ up to the next integer $d$, where $F$ is the cumulative distribution function of the $\chi^2$ distribution with one degree of freedom.
4. If $d = 20$, guess that it is a box of biased gremlins. If $d \ne 20$, guess that it is a box of uniform gremlins.

How do we assess how well this test distinguishes the two hypothesis of uniform vs. biased gremlins? We compute or estimate:

• The probability that we guess uniform gremlins when the test is given uniform gremlins. (This is 19/20. Why? Remember the procedure of computing $d$ is like—i.e., has the same distribution as—fairly rolling a d20. What's the probability that you get anything other than 20 out of a fair d20 roll? 19/20, obviously.)
• The probability that we guess biased gremlins when the test is given uniform gremlins. (This is 1/20, by reason of reading the above parenthesis while standing on your head.)
• The probability that we guess uniform gremlins when the test is given biased gremlins. (This is a pain to compute, so I inflict it as an exercise on the reader.)
• The probability that we guess biased gremlins when the test is given biased gremlins. (This is one minus the last one, so it should be an easy exercise for you, dear reader.)

A traditional statistidigitator might prestidigitate this in statistics jargon as follows:

We are trying to find whether the gremlins seem to be biased. If they are, we will report an effect and get a publication for our CV in the highest-impact journal whose editors don't look too closely at our ideas about gremlins.

• Our null hypothesis is that the box contains uniform gremlins.
• Our alternative hypothesis is that the box contains biased gremlins.
• We report an effect if $d = 20$. We chose this criterion because $d = 20$ is more probable under the hypothesis of biased gremlins than it is under the hypothesis of uniform gremlins.
• The statistical significance is the probability, given uniform gremlins, that we spuriously report an effect, i.e. guess biased gremlins because we got $d = 20$ by a fluke of fate. (The statistical significance is sometimes also called the false positive rate. In extra-obfuscated statistics jargon, it is called the type I error rate.)
• The statistical power is the probability, given biased gremlins, that we correctly report an effect, i.e. guess biased gremlins because we got $d = 20$. This depends on how much the gremlins are biased in the alternative hypothesis, called the effect size: we could imagine differently biased gremlins than the ones in procedure D, and the statistical power would be different. For smaller effect sizes, we need to draw more samples to attain the same statistical power. (The statistical power is sometimes also called the true positive rate. In extra-obfuscated statistics jargon, it is called one minus the type II error rate. This is usually a pain to compute, so authors on a deadline for publish-or-perish tenure tracks may just omit this, and ‘statistical significance’ grabs popular science journalists' attention better anyway.)
• The $p$-value from a run of the test is $1 - F(\chi^2)$, and $d = 20$ means $p < 0.05$, because what good is statistidigitation without bringing up $p$-values?

Suppose you write this $\chi^2$ test down as a computer program, and run it on a black box containing not gremlins flipping coins but rather your TRNG hardware. How do you interpret the outcome of the test?

• If your TRNG hardware is a truly uniform random source of bits, then there's a 1/20 chance it will raise the alarm that your TRNG hardware is made of biased gremlins, and a 19/20 chance that it will guess your TRNG hardware is made of good old uniform gremlins.

• If your TRNG hardware is a source of bits that behaves just like our friends the biased gremlins above, then there's a much higher than 1/20 chance it will raise the alarm that your TRNG hardware is made of biased gremlins, and a very small chance that it will guess your TRNG hardware is made of good old uniform gremlins.

An orthodox frequentist analyst would just use this test as a criterion for accepting or rejecting papers in their journal, so that they don't get criticized for more than a 5% rate of spurious alarms raised about biased gremlins in the population, until a replication crisis arises in your field owing to the devious phenomenon of unwitting $p$-value hackers in the garden of forking paths. An orthodox Bayesian analyst might further ask you to quantify in your prior state of knowledge the probabilities that your TRNG hardware behaves like uniform or biased gremlins, and will tell you what probabilities those options should have in your posterior state of knowledge.

None of this can tell you that your TRNG hardware is uniform. Critically, all we can do is apply tests that probably distinguish different models for how the box works. As the saying goes, all models are wrong, but some models are useful. In this case, the model of gremlins is wrong because, despite what your mother may have told you to make you clean your room, gremlins don't actually exist.

Exercise. Consider the box of flip-flopping gremlins that do the following:

1. Fairly flip a coin and record the outcome.
2. If the coin came up heads, report 0, 1, 0, 1, 0, 1, etc.; if the coin came up tails, instead report 1, 0, 1, 0, 1, 0, etc.

Say your null hypothesis is uniform gremlins, and your alternative hypothesis is flip-flopping gremlins. Say you apply the $\chi^2$ test, as written above, to a box either of uniform gremlins or of flip-flopping gremlins.

• What is the statistical significance of this test—the rate at which it wrongly guesses that uniform gremlins are flip-flopping gremlins?
• What is the statistical power of this test—the rate at which it correctly guesses that flip-flopping gremlins are flip-flopping gremlins?
• Is this $\chi^2$ test useful to distinguish uniform gremlins from flip-flopping gremlins? Why or why not?

Conclusion. So what do you do?

First, there's no ‘optimal $\chi^2$ value’. There's a distribution of test statistics, like $\chi^2$, from tests like the above procedure. There's decisions you can make based on the outcomes of the test, which have distributions of consequences in each model of the world, some of which are better than others. If you design your test so that it reports biased gremlins with 99% probability when you are given uniform gremlins, your test is not really very useful.

Second, the $\chi^2$ test doesn't mean much here. In a sense it is about the dumbest test you can perform, because it ignores relevant information. For a physical TRNG, you should study the physics of the device as much as you can, and formulate hypotheses not about biased gremlins playing Dungeons and Dragons but about plausible defects in the design and manufacture of your physical TRNG. (Can it ever get stuck in an alternating state? Will a $\chi^2$ test detect that?) For a PRNG with a uniform random key, you should at the very least figure the PRNG algorithm itself into your test!

Finally, there is no finally. The world is a complex place. There's always more to understand about it, and new models that can change your way of thinking. This may be one of them, even if I haven't quantified any prior probabilities or likelihoods about it!

Answer 3

Unfortunately, randomness is never optimal. It wouldn't be random then.

You don't normally consider the chi value itself. You transform it to a probability p based on the chi distribution and the number of degrees of freedom (255 in a byte's case). The p is then expected to be uniformly distributed between 0 and 1. Herein lies the problem. So one value doesn't really mean anything. A p of 0.01 is perfectly acceptable with a single run. If it's 0.01 over many runs, then your data isn't as expected. You should get all sorts of values up to 1. It's common then to perform a Kolmogorov–Smirnov (KS) test on the ps. You can use R, Python or code it yourself. I use Java's commons.math.

A note. If your chi = 0, your generator is broken as you never ever get a uniform distribution of bytes. Never. Interestingly, the chi for 2.5 billion decimal $ \pi $ digits is 12 which gives a p of ~0.2. Similarly, there is no such thing as an optimal chi value for IID bytes. That would be too easy. But also consider that it would be too easy for an attacker too if they knew exactly the distribution of bytes in a cipher. So what makes it hard for you to confirm randomness, is exactly the same thing that keeps a cipher secure. That's why they say that you can't mathematically prove randomness. You have to use the "duck" test.

The best way to visualise randomness is with the following random walk over 22 trillion $ \pi $ digits. Consider what the bias and chi values might be for the contents of the two boxes. They'd be wildly different, but both are perfectly correct as $ \pi $ is perfectly random. Your 254.3 value simple means that, meh, it's exactly 50/50 that your particular sequence is random. One value like that has little statistical significance.

Normal distributions or those based on a larger range are exactly the same method, with different numbers of degrees of freedom, but. Have a look here. But of course a TRNG doesn't output different distributions natively. All randomness extraction techniques output uniformly distributed bytes. And you can't have a normal distribution for discrete data like quantisized RNG bytes anyway. That would be a Binomial distribution with p $ \neq $ 0.5.