Given $n$ bits, how many "truly random" sequences/numbers can be constructed?

Question

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.

Answer 1

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$" < $0.99 * 2^n$

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

Answer 2

The short answer is: given $n$ bits, $2^n$ “truly random” $n$-bit sequences can be constructed — all of them.

Randomness is not a property of a number, nor a property of a sequence of numbers. It's a property of the method that was used to generate that number or sequence. Or, as fgrieu puts it

What matters to entropy is what the sequence could be, not what it happens to be.

You cannot tell from looking at a number whether it is random or not. You cannot even tell for sure from looking at a sequence of numbers whether it is random or not.

Say you roll a coin 10 times and get heads every time. Does that mean the coin is biased? Not necessarily. After all, there is a $2^{-10} \approx 1/1000$ chance to get this sequence from a perfect coin. If you generate random numbers at the speed a computer does, a run of 10 zero random bits happens all the time.

What statistical tests tell you is not whether the sequence is random or not. They give you a level of confidence in the randomness. This level of confidence cannot be precisely quantified in the abstract: it is wholly dependent on what the expected failure properties of the random number generator are.

For example, consider the following two random number generators which generate 128-bit blocks, with $S_i$ being the internal state after $i$ iterations, $R_i$ being the block returned on the $i$th call, and $\bar i$ the number $i$ padded to 128 bits.

1. Let $K$ and $S_0$ be secret 128-bit values, obtained from an unpredictable bit source. Define $R_i = \mathrm{AES}_{K}(\mathrm{AES}_{K}(\bar i) \oplus S_i)$ and $S_{i+1} = \mathrm{AES}_{K}(\mathrm{AES}_{K}(\bar i) \oplus R_i)$.
2. Let $K'= \mathtt{7656f8c8426c5249383b80452b8f7777}_{16}$ and $S'_0 = \mathtt{e0550076e1c7b04f390a43159783c1cf}_{16}$. Define $R'_i = \mathrm{AES}_{K'}(\mathrm{AES}_{K'}(\bar i) \oplus S'_i)$ and $S'_{i+1} = \mathrm{AES}_{K'}(\mathrm{AES}_{K'}(\bar i) \oplus R'_i)$.

These are the same algorithm except for the choice of initial values. Algorithm 1 is a good, widely used PRNG, defined by ANSI X9.31. Algorithm 2 is unsuitable for most uses in cryptography since its output is entirely predictable. Yet any statistical algorithm will be completely unable to distinguish between the two, since the only difference between them is how the initial values were generated and maintained.

Statistical tests are typically designed for the common case where a weakness of the RNG manifests itself in correlations between successive bits or similar “easily observable” properties. A true random sequence would not manifest any correlation with whatever the test implements (a true random sequence is not computable). Of course, the test cannot analyze the full (infinite) sequence, it has to work on a finite prefix. In a nutshell, a statistical test constructs a property of finite sequences that prefixes of random sequences have a very low probability of meeting.

If the test reports a failure, the information is something like “the finite sequence has this property, which a true random sequence has only a $2^{-50}$ probability of having”. Note that this does not give a probability for the (infinite) sequence to be random: to calculate that, we would have to know a probability distribution over RNGs that we might have designed, which is a subset of all possible RNGs. If the test reports a success, this does not translate into any quantifiable probability that the RNG is well-designed: as shown above, cryptography can pass any statistical test that is not designed with these particular cryptographic operations, without the result being a valid cryptographic RNG.

Answer 3

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$?

A statistical randomness test generally (and in the case of the NIST suite) returns a $p$-value indicating how likely that sort of result is with random data. If the $p$-value is out of bounds, the test fails.

For example, the NIST tests use $p \ge 0.01$ as the requirement, so $\sum_{x\in\{0,1\}^n} F(x) \approx 0.99 * 2^n$ for a particular test. That is, ~1% on all $n$-bit bitstrings fail the test, because that's the way it's designed.

The whole NIST suite looks at the distribution of $p$-values for individual sequences, so that expected test failures don't cause the whole test suite to not pass. What would happen in your case depends on what numbers you would actually give the suite (since running it on a single sequence is sort of meaningless).

Answer 4

Well, if you consider a uniform distribution over all $2^n$ different bitstrings, then you have exactly $N$ bits of entropy. If the distribution is not uniform, you "lose entropy". If you use a pseudo random number generator, chances are that not every string can be generated, and thus you don't have the full entropy.

But any of those "structures" like all $1$, repeating $01$ and so on: That matters nothing at all for entropy. Entropy doesn't care about the encoding/ representation. It matters how many different outcomes are and what their probability is.

Finally, the only advantage of having such a "not random looking" number is that you can compress them by using a code specially tailored for this very bitstring.

edit for the updeated question:

Well, that depends on your function $F$ and how exactly you define it. The function will respond to certain structures, and it will ignore other structures. There is no function which can check "Is this true randomness?", it all goes on statistical analysis: E.g. you form a hypothesis and then check the likelihood of your hypothesis being true. And you can assign acceptance rates of your personal choice.

But what it comes down to: There is no "universal test function", but you have to chose yourself which statistical properties you want to check. And no, you can not check all of them. The average value can be chosen from in the entire interval from accepting everything to accepting only one (or even zero) possible inputs. It's a little bit like asking "If my function G(x) is made of multiplications and additions, what is g(0)?"