Estimated entropy per bit given P-value of a statistical test, and number of bits tested?

Question

Assume that a certain statistical RNG test (say from the NIST Statistical Test Suite, Dieharder, etc..) gives us a certain P-value (per the definition [*] used in NIST Special Publication 800-22), after testing $n$ bits of a RNG; say, $P=0.001$ (indicative of failure of the test with high confidence) and $n=2^{20}$.

Based on that information alone, what can we say about the (maximum) entropy per bit $H$ of the RNG tested, with some prescribed confidence? By this I mean, more precisely: the hypothesis that the tested generator has at least entropy rate $H$ can be rejected with fair confidence; perhaps, as associated with some P-value (possibly higher than the $P$ obtained in the test, say twice that).

How can we refine this, given P-values $P_i$ for that experiment repeated $k$ times?

Update: if that's not answerable as it, does it remain so when we add some very general hypothesis on the structure of the RNG under test, like: it outputs independent bits with some unknown constant bias? Refine this additional hypothesis as needed to obtain some relation between $P$, $n$ and $H$ !

---

Update: I do realize that if any statistical test RNG pass, that gives no insurance at all about the entropy per bit of the RNG tested; and that if it fails with values as in my numerical example, any hint that it may give in term of entropy per bit will be that it is at most $H$, with that $H$ dangerously close to 1, thus not very telling (even with the now-reduced P-value).

---

[*] My understanding is that the correct definition of the P-value used for statistical RNG test is that the statistical test promises that for any $\alpha$ with $0\le\alpha\le 1$, it outputs a P-value at most $\alpha$ with odds at most $\alpha$ when applied to a perfect TRNG.

Further, I believe only the second sentence is right in this quote of NIST SP 800-22 page 1-4

For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%. For a P-value < 0.001, a sequence would be considered to be nonrandom with a confidence of 99.9%.

Correct me if necessary!

Answer 1

Firstly, the way (if at all) the "$P$-value" depends on $H$ depends (of course) on the statistical test that is being used. For each test, the result will be different and I cannot really give a meaningful general discussion here because different tests consider completely different aspects of the stochastic process of output bits.

In general, indeed, the $P$-value doesn't have to depend on $H$. Originally I (probably incorrectly) thought you were referring only to a particular test (the monobit frequency test), which is what my comment was referring to. I'll use this particular test in my answer to illustrate that the $P$-value can depend on $H$ and hopefully you'll be able to generalize my approach to other tests that are of interest to you. The analysis will be the same for many tests, but it will often be impossible to get any closed-form expressions relating the $P$-value and $H$.

Before I start with the analysis of the monobit frequency test, I'll also answer your question about the truth of the sentence

For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%.

A $P$ value larger than 0.001 means that we cannot reject the hypothesis that the sequence is random at a significance level of 0.001. In this sense the sentence is imprecise: it is not because our test would have produced our observation with high probability that the observation was produced by a TRNG. At all times one should remember that the formula for computing the $P$-value is derived under the assumption that the hypothesis is true.

---

Analysis of the monobit frequency test

I'll now discuss the monobit frequency test, which is defined in NIST SP 800-22 (section 2.1). My notation is a little different sometimes, but I think it should be clear enough (if not, please comment).

In the most general sense, even this analysis would be difficult: at most one can say that the probability distribution of the $P$-value depends on the entropy $H$, but you should probably forget about getting a simple relation (formula of some kind) in the general case.

The following part of your question (applied to the monobit frequency test) has a reasonably "nice" answer though:

If that's not answerable as it, does it remain so when we add some very general hypothesis on the structure of the RNG under test, like: it outputs independent bits with some unknown constant bias? Refine this additional hypothesis as needed to obtain some relation between $P$, $n$ and $H$!

So we've already made the assumption of working with a particular statistical test, because we can't answer the question otherwise. Now I'll make the following assumptions about the RNG:

1. There is no dependence whatsoever between the output bits of the random number generator.
2. The RNG is outputs a $1$ with a fixed probability $q$ and a zero with probability $1-q$. To get a a nice formula, I'll assume $q = 1/2 + \epsilon$ with $\epsilon$ sufficiently small such that $\epsilon^4 \approx 0$. I'll refer to $\epsilon$ as the bias.
3. $n$ is sufficiently large, but this assumption is implicit in the test anyway.

What I will show is that, under these assumptions, the probability distribution of $P_n$ (this is just $P$ for a specific value of $n$) depends on the entropy $H$. Note that I'm going to use $P_n$ as a random variable and $p_n$ for an instantiation of this test statistic. Once the distribution of $P_n$ is known, we can answer the following question:

What is the probability that the source entropy is $H$ given that the observed value of the $P$-statistic is $p_n$?

To obtain an answer to this question, we need to take the following steps

1. Write the bias $\epsilon$ in terms of the entropy $H$.
2. Compute the probability distribution of the test statistic for the biased RNG.
3. Compute the probability distribution of the $P$-value for the biased RNG.

Entropy and bias

The entropy $H$ of one bit of the RNG is given by

$$ H = q \log_2\left(\frac{1}{q}\right) + (1-q)\log_2\left(\frac{1}{1 - q}\right) = 1 - \frac{2\epsilon^2}{\log 2} + \mathcal{O}(\epsilon^4), $$ where $\log$ is the natural logarithm. Hence, we have approximately:

$$\epsilon \approx \pm\sqrt{\frac{\log 2}{2}(1 - H)}.$$

It shouldn't be surprising that there are two biases corresponding to the same entropy. For convenience, I'll use the positive value in the remainder of this answer. This means I assume that it is known that the RNG is positively biased.

Test-statistic

Let's call our sequence of output bits $X_i$. We're looking for the distribution of the following sum:

$$S_n = \sum_{i = 1}^n (-1) ^ {X_i} = 2\left[\sum_{i = 1}^n X_i\right] - n$$

Since the $X_i$ are assumed to be i.i.d. we have, asymptotically as $n \to \infty$:

$$S_n \sim \mathcal{N}\left(\epsilon \, n, 4p(1 - p) \, n\right).$$

Both the mean and the variance can then be rewritten in terms of the entropy $H$ (recall that for the mean, there are actually two possibilities). To express the variance in terms of $H$, note that

$$p(1 - p) = 1/4 - \epsilon^2 \approx 1/4 - \frac{\log 2}{2} (1 - H).$$

$P$-value

The $P_n$-value for our test can be computed as

$$P_n = 2\Phi\left(\frac{-S_n}{\sqrt{n}}\right).$$

So we can compute the probability that $P_n \le p_n$ for some value $p_n$:

$$ \Pr[P_n \le p_n] = \Pr\left[2\Phi\left(\frac{-S_n}{\sqrt{n}}\right) \le p_n\right] = \Pr\left[S_n \ge -\sqrt{n}\Phi^{-1}(p_n/2)\right]. $$

Now we can use the distribution of $S_n$ which we derived earlier:

$$\Pr[S_n \le s_n] = \Phi\left(\frac{s_n/\sqrt{n} - \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H)\log 2}}\right).$$

So we get

$$ \Pr[P_n \le p_n] = \Phi\left(\frac{\Phi^{-1}(p_n/2) + \sqrt{\frac{n\log 2}{2}(1 - H)}}{\sqrt{1 - 2(1 - H) \log 2}}\right) $$

(in the somewhat unlikely case that my calculations contain no errors, I'll check them later).

Note that as $n \to \infty$, the above probability goes to $1$ (for $H \neq 1$) so given enough sample bits we'll eventually conclude that the sequence isn't random. So that should also answer your question

How can we refine this, given $P$-values $P_i$ for that experiment repeated $k$ times?

(at least in this specific case)

Answer 2

Mu. This question is a category error, at least without the updates (addressed below).

Let's review the things in your possession:

• You have a generator, which is a black box with a crank you can turn to dribble out a stream of bits. Examples:

  1. a box that turns out 01010101...
  2. a box that turns out 10101010...
  3. a box that turns out $\operatorname{AES}_0(0) \mathbin\| \operatorname{AES}_0(1) \mathbin\| \cdots$
  4. a box with a gremlin who flips two coins and turns out 1 if they're both heads, or 0 if one is tails

• You have a (statistical) test, which is a procedure that examines a stream of bits and sometimes raises an alarm. This is usually a deterministic procedure. Examples:

  1. draw 100 bits, count the fraction of 0 bits, and raise alarm if it is below $\alpha_0$
  2. draw 100 bits, and raise an alarm if there's no contiguous sequence of at least six heads or at least six tails
  3. draw 8 000 000 bits, separate them into octets, count the number of occurrences $O_i$ of each octet $i \in \{0,1,2,\dots,254,255\}$, and raise an alarm if $$14.067 < \sum_{i=0}^{255} \frac{(O_i - 1\,000\,000/256)^2}{1\,000\,000/256}$$

• You also have a null hypothesis, which is a probabilistic model for how you hope the generator works—that is, a probability distribution on possible outputs of the generator each time you run it. Examples:

  1. every length-$n$ bit string has equal probability $1/n$
  2. every length-$2n$ bit string has probability $1/n$ if every consecutive pair of bits is the same like 001100000011, and probability zero if not
  3. the binary expansion of $\pi$ has probability 1 and every other bit string has probability zero
  4. every bit string of the form $\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1) \mathbin\| \cdots$ for 256-bit $k$ has probability $2^{-256}$ and every other bit string has probability zero
  5. the probability distribution induced by any procedure given in the examples of generators above

Whatever null hypothesis you have in mind has a particular fixed entropy. Given only these objects—a physical generator, a test, and a null hypothesis—running the test on the output of the generator only raises an alarm or not; it can't affect the entropy of the null hypothesis, which is fixed by definition. That is why the question as posed is a category error.

• Exercise: Compute the entropy of every (finite truncation of every) probability distribution listed above.
• Exercise: Find a generator or null hypothesis listed above which has zero entropy, and a test which, if repeated on that generator, will sometimes pass and sometimes raise an alarm.

Tests are designed so that if the generator is distributed according to the null hypothesis, i.e. everything is working as intended, then the test has a prescribed small rate of raising an alarm in spite of this, like 5% or .1%. Some tests—though not all—are structured as a method for converting a generator into a d20, rolling it, and raising an alarm if it comes up 1. In statistics jargon, the number that came up from the putative d20 roll (suitably scaled) is the $p$-value; the false alarm rate of the test is confusingly called the significance level or type I error rate.

• Exercise: Compute or estimate the false alarm rate of every test listed above for every hypothesis listed above as a null hypothesis.

What is the significance of rolling a 1 on a d20, besides scoring a critical hit on a troll in a pseudonymous internet message board? Not much alone, but usually tests are also designed with an alternative hypothesis in mind: another probability distribution on possible outputs of the generator, under which the test has a different alarm rate—higher than the test's alarm rate under the null hypothesis, we might hope.

The probability of an alarm under any alternative hypothesis is the statistical power of the test to detect that alternative hypothesis. The complement of the statistical power—that is, the probability of failure to raise an alarm under an alternative hypothesis—is sometimes confusingly called the type II error rate. (Raise your wing if, like me, you can never remember which is which between type I and type II errors.)

• Exercise: Compute or estimate the statistical power of every test listed above to detect every hypothesis listed above as an alternative hypothesis. Is this different from the previous exercise?

---

If you specified an alternative hypothesis, the test might lead to a decision rule about what hypothesis or hypotheses to proceed with given the outcome of the test. How you proceed might depend on whether you're doing development or deployment: do you change the engineering of the device, read up on more physics, craft the device more carefully during development; or do you raise an alarm and shut the system down during deployment?

So, maybe you have the following family of alternative hypotheses, parametrized by $\theta \in [0,1]$, as in the update:

• a box with a gremlin who flips a coin with a bias toward heads with probability $\theta = 1/2 + \varepsilon$ and turns out 1 if heads

In that case, intuitively, if you see lots of 1 bits you might find larger values of $\theta$ more plausible than smaller values of $\theta$. However, you asked about examining tests with $p$-values, not about examining the output of the generator. This restricts how we can proceed to make decisions about what hypotheses to work with. You also asked not about choosing hypotheses, but about estimating entropy, which for the specific family of alternative distributions in the $\theta$-biased gremlin is $$H = -\theta \log \theta - (1 - \theta) \log (1 - \theta).$$ Of course, if we add a hypothesis about a gremlin who gets tired and sometimes starts repeating a past coin flip rather than make a new one, the story gets much more complicated!

So what do the $p$-values tell you about the entropy of alternative hypotheses?

• In the frequentist framework—which covers most 20th-century statistics, like you will find in an undergraduate science education—there is no notion of ‘probability of a hypothesis’, $P(\theta)$; there is only probability of observed data $x$ under a hypothesis $\theta$, $P(x; \theta)$, like the sum of $n$ independent Bernoulli trials weighted by $\theta$ with $P(k; \theta) = \binom{n}{k} \theta^k (1 - \theta)^{n - k}$, a distribution which has (Shannon) entropy $\frac{1}{2} \log \bigl(2\pi e n \theta (1 - \theta)\bigr) + O(1/n)$. Consequently, there is no notion of the ‘probability that a hypothesis has a certain entropy’, because entropy is a (deterministic) function of the hypothesis itself—a kind of parameter, if you will—and there is no notion of probabilities of hypotheses or hypothesis parameters.

  • In the frequentist framework of binary hypothesis testing, the $p$-values are just intermediate quantities in a decision rule: During development, do we decide that the device is behaving as we expect, or do we have to calibrate it some more? During deployment, do we raise an alarm that the device is broken, or do we continue to use it?

    The $p$-values in this framework are connected to entropy only insofar as you use a decision rule based on the $p$-values to decide which hypothesis you like, and the choice of hypothesis determines entropy. You don't actually need $p$-values here—none of the example tests above even uses $p$-values directly. Tests that work via $p$-values are just convenient because the false alarm rate can be adjusted directly.

    Alone, this framework doesn't actually tell us anything about what hypothesis to proceed with if we reject the null hypothesis—it only tells us which one not to proceed with.

  • In the frequentist framework of parameter estimation, if you limit your hypotheses to a particular family of distributions like independent Bernoulli trials $P(B_i; \theta) = \theta$ with unknown parameter $\theta$, you could use the same computation as a hypothesis test involving a $p$-value—but instead of making a decision based on a cutoff, you could make an estimate for $\theta$, or for the entropy of the distribution, using the $p$-values of the test.

    For example, if you invert Aleph's formula for $P_n$ to recover $S_n$, use that to estimate $\theta$, and thereby compute $H$, what you get is an estimator for the entropy—that is, a procedure which, given data, prints a candidate value for a parameter. It's a rather unorthodox way to do things, of course, and it's not a priori clear to me what frequentist properties it has: Is it unbiased? Is its distance from the ‘true’ value bounded with high probability?

    Nothing about the nature of the quantities computed as $p$-values is relevant here; it just happens that the formula for the monobit test $p$-value can be inverted to solve for $H$. A much simpler way would to estimate $H$ would be to estimate $\theta$ directly by counting the fraction of one bits, and to derive $H$ from that—this gives a maximum likelihood estimator. This works for many repetitions of the test, too, whereas there's no obvious way to aggregate multiple $p$-values into a single estimator for $H$ short of reconstructing the fraction of one bits from the $p$-value and number of samples.

• In the Bayesian framework, the $p$-values could be used to determine a posterior probability density $\rho(\theta \mid p, C)$, where $\theta$ is a hypothesis, $p$ is a $p$-value, and $C$ is all your other knowledge including your prior probability density $\rho(\theta \mid C)$ on hypotheses. By computing $\rho(p \mid \theta, C)$, you can use Bayes' theorem to derive $$\rho(\theta \mid p, C) = \frac{\rho(p \mid \theta, C) \rho(\theta \mid C)}{\int \rho(p \mid \theta', C) \rho(\theta' \mid C) \,d\theta'}.$$ Again, this would be a rather unorthodox way to do things—and it would be much more efficient to use the original data from the test rather than compress them into a $p$-value first.

  If in your initial state of knowledge $C$ you are willing to consider only conditionally independent Bernoulli trials $P(B_i \mid \theta, C) = \theta$ for an unknown but fixed parameter $\theta$, and if your prior on $\theta \in [0,1]$ is Beta-distributed with density $$\rho(\theta \mid C) = B(\theta; \alpha, \beta) = \frac{\theta^{\alpha - 1} (1 - \theta)^{\beta - 1}}{B(\alpha, \beta)} = \frac{\theta^{\alpha - 1} (1 - \theta)^{\beta - 1}}{\Gamma(\alpha) \, \Gamma(\beta) / \Gamma(\alpha + \beta)},$$ then there's a much simpler way to analytically compute the entropy of the next observation given past observations: by standard properties of the Beta and Bernoulli distributions, after $h$ heads and $t$ tails, the posterior probability density on the parameter is $$\rho(\theta \mid h, t, C) = B(\theta; \alpha + h, \beta + t),$$ so the conditional probability that the next observation comes up heads is

  \begin{align} P(B_{h + t + 1} \mid h, t, C) &= \int P(B_{h + t + 1} \mid \theta, h, t, C) \, \rho(\theta \mid h, t, C) \;d\theta \\ &= \int P(B_{h + t + 1} \mid \theta, C) \, B(\theta; \alpha + h, \beta + t) \;d\theta \\ &= \int \theta \cdot B(\theta; \alpha + h, \beta + t) \;d\theta \\ &= \int \theta \cdot \frac{\theta^{\alpha + h} (1 - \theta)^{\beta + t}}{B(\alpha, \beta)} \;d\theta \\ &= \int \frac{\theta^{\alpha + h + 1} (1 - \theta)^{\beta + t}}{B(\alpha, \beta)} \;d\theta \\ &= \int B(\theta; \alpha + h + 1, \beta + t) \;d\theta \\ &= \frac{\alpha + h + 1}{\alpha + h + 1 + \beta + t}, \end{align}

  and likewise for tails. In general, after seeing $h$ heads and $t$ tails, the Shannon entropy of the conditional distribution on future outputs is $H = -\theta \log \theta - (1 - \theta) \log (1 - \theta)$ where $$\theta = \frac{\alpha + h}{\alpha + h + \beta + t}.$$ (Computing the min-entropy left as an easy exercise for the reader.) The $B(\alpha, \beta)$ distribution on $\theta$ in a sense represents having seen $\alpha$ heads so far and $\beta$ tails so far. This is not just a stochastic estimate; this is analytically the exact entropy of the conditional distribution.

  How to choose $\alpha$ and $\beta$ depends on what style of Bayesian you are: the naive Bayesians will start with the flat prior $\alpha = \beta = 1$ which coincides with the uniform distribution on $[0,1]$, the objective Bayesians will start with $\alpha = \beta = 1/2$ or $\alpha = \beta = 0$ if they're edgy, the subjective Bayesians will pull numbers out of their cloacas, the empirical Bayesians don't really care as long as the number of samples is large enough and might let $\alpha$ and $\beta$ have exponential or Gamma distribution, etc.

  Of course, this analytical approach goes out the window as soon as your hypothesis space includes more complicated hypotheses, like a decaying blob of polonium-210 which behaves differently over time. But the point is that when you are navigating a space of hypotheses, specific knowledge of the hypotheses will often naturally give you a much more precise picture of what to do with data than you can get out of generic application of frequentist binary hypothesis tests built out of $p$-values.

  If the picture seems too simple as in the Beta-Bernoulli above, that's not because you're doing the computation wrong but because your hypothesis space was too narrow. This perspective is explored in much greater depth by Edwin T. Jaynes, Probability Theory: The Logic of Science, Cambridge University Press, 2003. You can even use the Bayesian framework during development to study the physics, and later derive a frequentist hypothesis test with good statistical power and prescribed false alarm rate for use in deployment!

Answer 3

Nothing.

Unless you have a bad RNG, your 1 million bits will in all likelihood (99.999999999%) have a entropy of virtually 1 bit /bit. This is the ent output for 1GB of good random data:-

Entropy = 1.000000 bits per bit

Similarly, this is for a source with exactly 7 bits /byte of entropy. The p value = 0.

Entropy = 7.000000 bits per byte.

Chi square distribution for 1000000000 samples is 1000000238.08, and randomly would exceed this value less than 0.01 percent of the times.

This doesn't really tell you anything useful. The entropy calculation is too lossy to be useful. The min-entropy will be a bit lower. You'll just be left with a few decimal places of difference, perhaps. You'd be splitting very thin hairs.

The two following random walks are from a good true random number generator. Clearly the p scores for each will be different. The first might get p << 0.05. The p score is a group operation and is only valid for that block. So the p score will vastly vary over the whole data. You might then amalgamate all the p scores together with a KS test, but then you're averaging an average and so on.

Further I don't think that anyone has studied how many ways you can park a car in a car park with that kind of focus. This test is in Diehard and only works due to computer simulation of the expected results. There may not be any simple linear relationship between car positions and entropy. It isn't a simple chi square comparison of byte values, but one of actual parked cars which have little direct relation to a p value.

Some of the other tests will be similar with mathematical simulation so the p scores relationships will be dependant on the type of test. There probably isn't the academic imperative to study this much as I'm not sure what the benefit would be.

The monobit test shows this futility. The sequence "10101010..." will be identified as a perfect source of entropy according to the monobit test. Entropy is 1 bit /bit resulting in a p of 0.5. A compression test will reduce this sequence to effectively zero length however, giving a p ≈ 0 or 1. So we'd have:-

Monobit. H = 1, p = 0.5 (optimal pass)

Compression. H ≈ 0, p ≈ 0 or 1 (absolute failure)

And this would be for the same block of data, so what can be inferred as one test directly contradicts the other to the greatest possible degree? Nothing.

The output function of RC4 (my favourite PRNG) passes all general statistical randomness tests averaging a H ≈ 1 bit /bit. Yet specialised distinguishers can spot it's long run output from a random sequence to the extent that it is not recommended for new implementations. So again nothing is learnt from a rigorous analysis of any single randomness test type and it's corresponding p value.