13
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ I'm far from a great fan of RNG testing programs in cryptography; and I understand that this question is mainly one of statistics. But I hope it is acceptable, as a positively answerable variant of earlier question Estimating bits of entropy which was deemed on-topic. $\endgroup$ – fgrieu Feb 14 '17 at 22:40
  • 2
    $\begingroup$ IMHO the fact that there are a large number of tests in the scientific field of statistics implies that no single such tests is really "perfect". Further, in statistics an event whose occurence has a probability of 0 doesn't mean that event could strictly never occur (I am a layman in math but I was told that that 0 is to be interpreted in the sense of measure theory and not in the sense of e.g. number theory). So I also tend to think that the "Nothing" of Paul Uszak's answer is right. $\endgroup$ – Mok-Kong Shen Mar 4 '17 at 11:33
  • 2
    $\begingroup$ If you want a hypothesis test on the entropy, it's probably best to use a test which does just that. This test only checks whether it is likely that the RNG generates a sequence has a certain limiting form (normal, because the bits of a TRNG are independent). If the RNG outputs independent but biased bits, it is relatively easy to relate the entropy of the RNG to the $P$-value. However, the general case where the output bits are not independent will be difficult. It seems possible to generalize to martingales and other weakly dependent sequences though (one problem may be slow convergence). $\endgroup$ – Aleph Mar 4 '17 at 13:05
  • 1
    $\begingroup$ @Aleph You beat me to it! Yes I agree, you might be able to show some relationship if you have a specialised test. However there's no chance using generalised tests like Dieharder or just plain Chis which OP was asking for. $\endgroup$ – Paul Uszak Mar 4 '17 at 13:38
  • 1
    $\begingroup$ This is a request for clarification that might benefit other readers... What you you mean by "maximum" entropy? Is this a turn of phrase or are you specifically referring to Hartley entropy? $\endgroup$ – Paul Uszak Mar 4 '17 at 17:57
5
+50
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ But what do we exactly know if this test is directly contradicted by another type of test? And this is highly likely in the question's scenario of a quirky RNG under a randomness test suite such as Dieharder. $\endgroup$ – Paul Uszak Mar 5 '17 at 0:27
  • $\begingroup$ @PaulUszak It depends on the other test (in particular how it depends on $H$). We do expect many tests to fail (after all we're using a biased RNG), but the question is mainly how badly they will fail (observed value $p_n$). In the monobit frequency test, one could derive a hypothesis test on $H$ using $P_n$ as the test statistic. After all, the distribution of $P_n$ is known in terms of $H$. There are no certainties about $H$ here, though, so contradictions between several such hypothesis tests will be possible to some degree. $\endgroup$ – Aleph Mar 5 '17 at 9:20
  • $\begingroup$ @PaulUszak I derived these formulae in my answer. The point is to show that there is a relation between $H$ and the result of the monobit frequency test. Yes, this is not the intention of the test, but that's irrelevant to the analysis. $\endgroup$ – Aleph Mar 5 '17 at 23:20
  • $\begingroup$ @Aleph: Can you please confirm that the $\Phi$ function you use is the the standard normal distribution, with$$\Phi(x)={e^{-{1\over2}x^2}\over\sqrt{2\pi}}$$or if not, define that, perhaps with a reference? $\endgroup$ – fgrieu Mar 7 '17 at 13:33
  • 1
    $\begingroup$ @fgrieu Sorry that I said I could confirm this earlier; I only read "standard normal distribution", but that doesn't match your formula (which is the standard normal probability density function). $\endgroup$ – Aleph Mar 8 '17 at 8:29
1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Some clarifications mostly regarding my own answer from a while back: I don't think this question is a "category error", or at least I don't see how. The question isn't about estimating entropy, and that's not what my answer was about either. In my view, the question is basically about computing the power of a statistical test, where the set of alternatives hypotheses is that of sequences of independent but biased random bits (with some given entropy). Or, if it were feasible, more general hypotheses characterized by an entropy parameter. $\endgroup$ – Aleph Mar 21 at 9:14
  • $\begingroup$ The question title is ‘Estimated entropy per bit given P-value of a statistical test, and number of bits tested?’, so it seems to me like it is very much about estimating entropy! The question doesn't address any family of hypotheses with a variable parameter for entropy. You and I may have inferred independent Bernoulli trials with an unknown parameter, becase that's an obvious model to consider—but the question doesn't specify that at all. (Actually in the Bayesian approach they aren't exactly independent, and that's crucial to doing inference!) $\endgroup$ – Squeamish Ossifrage Mar 21 at 14:28
  • $\begingroup$ Independent trials are actually part of the question (see the part after "update"). Regarding estimation: I understand the confusion. Evidently, measuring P-values is not a good way to estimate entropy. In fact I pointed to this in a comment to the question. My interpretation of the question was "What can we say (roughly) about entropy given the P-value for a test that actually is intended to test some other aspect of a sequence?". $\endgroup$ – Aleph Mar 21 at 14:52
  • 1
    $\begingroup$ So it does say that about independent trials. I can read, sometimes. $\endgroup$ – Squeamish Ossifrage Mar 21 at 14:54
-1
$\begingroup$

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.

walk1

walk2

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.

$\endgroup$
  • 3
    $\begingroup$ I do not follow your reasoning. You seem to posit that the RNG tested is good, when I do not. I tried to alter the question, to make it numerically answerable, at least with the added hypothesis. $\endgroup$ – fgrieu Mar 4 '17 at 10:09
  • 2
    $\begingroup$ The sequence "10101010..." does not have an entropy of 1 bit per bit, because the bits are dependent. In fact, the entropy contained in $n$ such bits converges to 1 as $n \to \infty$. So the average entropy per bit would be zero. (The relationship between $H$ and the $P$-value in my answer assumes a sequence of independent bits.) $\endgroup$ – Aleph Mar 5 '17 at 19:08
  • 2
    $\begingroup$ @PaulUszak You're using the Shannon formula for the probability distribution of individual bits, rather than the joint probability distribution of several consecutive bits. That said, an "online entropy calculator" can never get the correct result here unless it knows the stochastic process (which it can't from only a sample). Again, my answer made an independence assumption that doesn't hold for your example. $\endgroup$ – Aleph Mar 5 '17 at 23:22
  • $\begingroup$ This doesn't address how p-values and entropy are related (not even under any additional premises like a frequentist or Bayesian interpretation of these as hypothesis tests), asserts nonsense about p-values (‘the p score is a group operation’), illustrates a point that has no apparent connection to the question with two graphs of random walks that have no apparent connection to the point, invokes an analogy to parking cars without connecting it to the question, and at the end of this dizzying chain of (dis)connections concludes with declining to answer the question. $\endgroup$ – Squeamish Ossifrage Jun 11 at 1: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.