Probability statement of a 16-bit random number generator.

Question

I am trying to understand the actual implications for the following statement regarding a 16-bit random number generator for the tag from the EPC Generation 2, UHF RFID specification, section 6.3.2.7. that states:

Probability of a single RN16: The probability that any RN16 drawn from the RNG has value RN16 = j, for any j, shall be bounded by $$0.8/2^{16} < P(RN16 = j) < 1.25/2^{16}$$

I realized this morning that I actually have no idea what that statement really means, but it seems one can have less than random, random number generator.

I made a 16-bit random number generator on silicon that passed statistical tests; however, looking back at the specification, it seems that I probably could have saved some power and cut some corners, but I honestly don't know how I would have turned those parameters into an engineering decision.

This gets me to the question: How does the above equation affect an allowable decrease in randomness from a truly random number generator?

edit: That statement is just so weird. If I counted up from 0 to 65535 and wrapped around to 0 again, I'd satisfy that condition, and that's not random at all.

Answer 1

All the comments are spot on. The statement is simply about the "probability" of each 16 bit output, say $X$, from the RNG. Something of the form $$ (1-\epsilon)2^{-16} \leq \Pr(X=x) \leq (1+\epsilon)2^{-16}, \quad \forall x \in \{0,1\}^{16}. $$ This can only be tested empirically but tests do not prove randomness, they can indicate nonrandomness due to failure of outputs.

In crypto literature and standards there are other tests, which attempt to evaluate aspects of randomness such as independence of consecutive (or non consecutive) samples such as "Runs Test", "overlapping Windows test", "non overlapping Windows test".

So this test you mention simply corresponds to what's called "frequency test" in cryptographic literature. The weakest, the simplest, but if it fails then one can strongly suspect something is wrong with the generator.

There is also whole field of computer science and mathematics focused on defining and measuring randomness. Martin-Lof and Kolmogorov have worked (among many others) in this area,

There is no way this test can prove any substantial randomness property.