Given $n$ bits, how many "truly random" sequences/numbers can be constructed? Suppose we have $n$ bits, so we can have $2^n$ different bit sequences. Some sequences don't look random, say, all $1$ or $0$. There are also other patterns like $10101010…$, $11001100…$ and such.

I'm not certain but aren't there ways to evaluate a given sequence as random with some given satisfied error? Given $n$ bits, how many "truly random" sequences/numbers can be constructed?

Update: The main question is we have $n$ events (coin flips). $n$ considered to be big enough. Now we want to know are those events random or not and we apply NIST suite for this.

As $n$ events cant be represented as $2^n$ number, we can have a function
$F(n)$, which gives 0 if NIST suite for given bit sequence represented by $n$ fails to satisfy and gives 1 if $n$ looks like random.

Question is what is sum $F(n)$ over all $n$? Approximately, for sure. And yes, NIST is just an example. Take any test which can by applied for given bit sequence.
I'm not certain but aren't there ways to evaluate a given sequence as random with some given satisfied error? Given n bits, how many "truly random" sequences/numbers can be constructed?


If you define "truly random" as meaning prior to generating the sequence, that each bit has an independent 50% chance of being 0 or 1, then all $2^n$ bit strings are equally likely. By that definition you can reject none of them.

So, there is not a way to "evaluate a given sequence as random". However, some random data may contain detectable signals. Good RNGs produce these signals sometimes because they are in the set of all possible results. Badly-constructed software RNGs produce these detectable signals more frequently than by chance. A well-known example of a bad RNG like this is the randu generator.

The NIST tests, and those like it (I've used the Dieharder suite for a PRNG), do not detect randomness. Instead they detect signals in the noise. If a RNG produces a clear "FAIL" signal for every (or nearly every) sequence that it produces, then it is considered a poor RNG, because an attacker who wanted to predict its output could use knowledge of that signal to reduce the amount of guessing they need to do to (to figure out a secret key, for instance).

If a good RNG produces a "FAIL" signal every now and then, then this is  not very meaningful. In fact you normally just set a p-value for the test, and a good RNG will fail with that exact probability each time you use that test against its output. You could even run a meta-test, where a good RNG can be expected to generate a certain number of failures from a test. In that case, you need to define a p-value for the meta test, which of course the generator might fail, and you could have a meta-meta-test . . .

If a specific sequence produces a "FAIL" signal from a test like one of the NIST suite, this is generally meaningless. Ideally, you should go back to your source and generate another sequence to see if that signal is consistently appearing in its output - i.e. you should test your RNG source, not the sequence itself.


You cannot meaningfully say: "This sequence is not random."
You can meaningfully say "This RNG is predictable."


It is still possible to assess a large enough individual sequence against the NIST tests or similar, and to declare it fit for some purpose or other. For instance, perhaps you have an RNG which you don't trust (it could hardware fail, or might be tampered with)? In which case you could decide to reject "suspicious" outputs from it. There is no fixed standard for that. You get to decide where to set the bounds. Worse than that, by filtering out test "FAIL" sequences, you make the output less than truly random. However, as that would be by some small factor - perhaps 5% of sequences might get rejected - it would not give an attacker much of an advantage, so it is something you could consider if you had good reason - such as a real possibility of someone tampering with your system's RNG.

This sort of sequence rejection is close to your proposed $F(n)$. You would have to implement a specific version of it before you could answer "what is sum $F(n)$ over all $n$?". You would want to keep that value as high as you can whilst cleanly rejecting sequences that represented hardware failure, tampering, use of incorrect RNG, or other failure modes that your test was protecting your system against. Allowing a low value - e.g. accepting only 1 in 10 attempts as being "random enough" - would make your RNG process less efficient, and might make your RNG more predictable to an attacker.

You could look at analysis like the Receiver Operating Curve if you need to quantify how well your system disambiguates systemic failure of the RNG compared to normal variation in a good RNG. Optimising the area under the curve would be a sign that you have a good series of tests, then you can set test p-values depending on the risks associated with false positives (rejecting random data) versus false negatives (accepting tampered data, or from a bad RNG).



If we take a very naïve view of the NIST test suite, we can set upper and lower bounds of "Sum $F(n)$ over all $n$" as follows:


There are 15 separate tests listed on NISTs web site.
You arbitrarily set a rejection p-value of 0.01 for your test, and reject any sequence that fails 1 or more tests.
The proportion of sequences that pass any single test is almost exactly 0.99 - by definition, you are rejecting 0.01 of anything that could happen.
A lower bound on your value is when each test finds a mutually-exclusive set of "suspicious" bit strings. That would suggest "Sum $F(n)$ over all $n$" > $0.85 * 2^n$ 


This is not a correct assumption, but it does set a lower bound. This is quite an encouraging value, since rejecting 15% of sequences from a perfect RNG does not give an attacker much to work with, and you have clearly included obvious failure modes such as all bits 0 or 1, and many repeated patterns.

An upper bound on your value is when each test finds the same set of "suspicious" bit strings. That would suggest "Sum $F(n)$ over all $n$" &lt; $0.99 * 2^n$ 


This is not a correct assumption, because otherwise there would be no point in having the separate tests.