random

[Darren New]

Tim Peters wrote:
> 
> [Darren New]
> > how random is the binary string "1001010010011100100"? How
> > random is the binary string "0000000000000000000"? Such questions
> > don't make any sense.
> 
> BTW, you can find attempts to answer such questions in Knuth, Vol 2.  The
> questions not only make sense, but finding non-trivial answers is important
> in real life:  even if you have a theoretically perfect physical RNG, how
> can you have confidence in a specific real implementation? 

This is a different question. The point is that the two strings above
are equally probable if they're both generated randomly.  Hence, asking
which is "more random" is asking a different question. They're both
equally probable, and they're both equally random (i.e., not at all,
because I just told you what they are).

As far as "testing for randomness", the point is that a machine
generating a long string of zeros is more likely broken than randomly
generating zeros. If my random number generator started outputting the
ASCII of the Linux kernel sources, I'd start wondering too. If it
started outputting the ASCII of the Linux kernel XOR the source of the
GNU CC compiler, I should be equally worried, yes? But since I might not
notice *that* one, I'd not be worried. Should I be worried if it outputs
exactly the secret message I was about to encrypt, so that the *cypher*
text is all zeros?

Sure, informally speaking, the first string is "more random" than the
second. Or, put another way, the second string is "less random" than the
first, as there are more ways to generate the second string with
non-random generators than there are ways to generate the first string.
It's not "less random", it's "less unusual" or "less surprising". But
that's not a measurement of the string, but rather its relationship to
the people looking at it.

> the hypothesis that the source is truly random.  Saying "well, *any*
> sequence of N bits is equally likely from a truly random source, so they
> both look random enough to me!" should leave you at least a little
> uncomfortable, if not downright embarrassed <wink>.

Indeed, if you block out the possibility of using a long string of
zeros, you weaken the security of a one-time pad encryption mechanism.
It's no longer perfectly secret.

-- 
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
       San Diego, CA, USA (PST).  Cryptokeys on demand.
     This is top-quality raw fish, the Rolls-Rice of Sushi!