Estimated entropy per bit given P-value of a statistical test, and number of bits tested? 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 &lt; 0.001, a sequence would be considered to be nonrandom with a confidence of 99.9%.


Correct me if necessary!
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:


There is no dependence whatsoever between the output bits of the random number generator.
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.
$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


Write the bias $\epsilon$ in terms of the entropy $H$.
Compute the probability distribution of the test statistic for the biased RNG.
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)