# Relation between P-value in a randomness test, number of samples, and entropy

Consider tests of randomness of bit sequences of fixed size $n$ bits as in cryptography (e.g. NIST Special Publication 800-22 page 1-4; notice this uses captital-$P$ for p-values). Define such test as any deterministic function $T$ that accepts a vector $V$ of $n$ bits, and outputs a p-value $p$ in $]0\dots1]$ (with null hypothesis that $V$ consists of random independent unbiased bits), that is with the defining property $$\forall\alpha\in[0\dots1],\;\;\Pr\big(T(V)\le\alpha\big)\,\le\,\alpha$$ where the probability is computed with $V$ a vector of random independent unbiased bits (or equivalently, is computed as the proportion of $V$ such that $T(V)\le\alpha$ among the $2^n$ vectors $V$).

Example tests matching this definition are

• True, which always output $p=1$.
• Non-zero, which outputs $p=1/2^n$ if all bits in $V$ are zero, and outputs $p=1$ otherwise.
• Non-stuck, which outputs $p=1/2^{n-1}$ if all bits in $V$ are identical, and outputs $p=1$ otherwise.
• Balanced, which computes the number $s$ of bits set in $V$ (that is the Hamming weight of $V$), and outputs as $p$ the odds that for random $V'$, $|2s'-n|$ is at least $|2s-n|$.
• For $n\le3$, Balanced is the same as Non-stuck.
• For $n=4$, $p=\begin{cases} {1/8}&\text{ if } s\in\{0,4\}&\text{e.g. }V=(0,0,0,0)\\ {5/8}&\text{ if } s\in\{1,3\}&\text{e.g. }V=(1,0,1,1)\\ 1&\text{ otherwise}&\text{e.g. }V=(1,0,0,1)\end{cases}$
• For $n=5$, $p=\begin{cases} {1/16}&\text{ if } s\in\{0,5\}&\text{e.g. }V=(1,1,1,1,1)\\ {3/8}&\text{ if } s\in\{1,4\}&\text{e.g. }V=(0,0,1,0,0)\\ 1&\text{ otherwise}&\text{e.g. }V=(0,1,1,0,1)\end{cases}$

There's a natural partial order relation among tests: $T$ implies $T'$ when $\forall V, T(V)\le T'(V)$. Any test implies True. Balanced implies Non-stuck, but does not imply Non-zero. Some tests, including Balanced and Non-zero, are optimal in the sense that no other test implies them.

Section 2 of the above reference describes 15 tests for large $n$ (thousands bits), that are intended to catch some defects relevant to actual random number generators, and be near-optimal (in the above sense). For example, section 2.1 is an approximation of Balanced for large $n$ using the complementary error function, designated The Frequency (Monobit) Test.

Q1: Assume that all the $n$ bits in a vector $V$ tested are random independent bits having same odds $q={1\over2}+\epsilon$ to be set, with $\epsilon$ unknown (besides being smallish), corresponding to Shannon entropy per bit $$E=-q\log_2(q)-(1-q)\log_2(1-q)=1-{2\over\log2}\epsilon^2+\mathcal O(\epsilon^4)$$

The Balanced test for some (large) number $n$ of such bits is applied once, and outputs a small p-value (say $p\le0.001$). That allows us to reject the null hypothesis $H_0$ that $E=1$ (equivalently, $\epsilon=0$) with high confidence (corresponding to the p-value $p$).

What is a tight function $E(p,n)$ such that we can reject the hypothesis $H_1$ that $E\ge E(p,n)$ with some good confidence (corresponding to some known p-value higher than $p$, perhaps $2p$, or $\sqrt p$, or something on that tune)? By "tight function" I mean that the lowest $E(p,n)$ we manage to prove for some confidence, the better.

Q2: Things are as in Q1, except that the test is unspecified beyond the defining property of p-values. Can we reject the hypothesis $H_1$ that $E\ge E(p,n)$ with good confidence, for whatever $E(p,n)$ and at least the confidence level that was established in Q1? If that conjecture was false, what's a counterexample, or/and is that reparable?

Q3: Things are as in Q2 (or in Q1 if the property thought in Q2 does not apply), except that the bits in the input $V$ might be dependent, but still with Shannon entropy per bit $E$; that is, the distribution of the inputs $V$ is such that $$nE\;=\;-\sum_{V\text{ with }\Pr(V)\ne0}\Pr(V)\log_2(\Pr(V))$$ Can we reject the hypothesis $H_1$ that $E\ge E(p,n)$ with good confidence, for whatever $E(p,n)$ and at least the confidence level that was established in Q1? If that conjecture was false, what's a counterexample, or/and is that reparable?

• The question is an hopefully clearer variant of this question on cse, which has an answer for Q1 that I'm having some difficulty to follow. Mar 7 '17 at 17:29
• The probability that all possible events happen is 1. Can the Balanced Test be stated in this way? Could you give an example of a bit vector for a given $n$? Describe what is meant by "the number s of bits set in V". Does "per bit" imply a value for each binary digit? In statistics, capital $P$ means probability and small $p$ indicates the p-value. $H_0$ is the null hypothesis, $H_1$ is the alternative hypothesis, etc. I suggest this notation. Q1: What is meant by "all bits"? All bits in a byte, word, sample, or the universe? Mar 14 '17 at 22:38
• @noumenal: Following your advise I now use $p$ for p-value, even though my reference uses $P$; $E$ for entropy, leaving $H_0$ for the null hypothesis and $H_1$ for an hypothesis made with knowledge of the p-value. I tried to make the definition of Balanced clearer, including giving alternate definition of "the number $s$ of bits set in $V$", and examples of $V$. I hopefully clarified "all bits" in Q1. Mar 14 '17 at 23:31