random

[Tim Peters]

[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?  As you said in
another reply, measurement isn't perfect, and I'll add that the person
implementing it may have made mistakes, misundertood the theory, or
overlooked a source of gross physical interference, or malfunctioning
equipment.  Before deciding to use it or not, all you can do is sample some
finite number of outputs and decide whether or not they're consistent with
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>.

[Nick Perkins]
> They do make sense, according to Chaitin.

[back to Darren]
> Well, sure, with Chaitin's definition (redefinition?) of the word
> "random", that makes sense. But in what sense is Chaitin's "random"
> different from "compressible"?

Given suitable pages of preliminary definitions, none.

> Why does he use a different word when we already have a perfectly
> good word for it?

"random"?  But you know that's used to mean different things by different
people.  This whole thread is a long demonstration of that <0.5 wink>.  At
the start of the field, they didn't know that "compressibility" would be a
good measure of randomness, but they *suspected* it.  It wasn't proved until
later, and it turns out that "a random sequence" (according to the
compressibility view) passes all computable tests for randomness (according
to the view of randomness that falls out of statistical testing).  I'm not
sure whether that matches your view today, but since computable statistical
testing is all I can *do*, if it doesn't match your view I'll never be able
to detect the difference.

> It sounds wierd to me to say "'Pi' is more random than 'e'."  Even
> stranger to say "'Pi' is more random than 'e' *because* they are both
> algorithmically calculable."

Does it sound wierd to say that the decimal digits of pi are more random
than the decimal digits of sqrt(2)?  Of 1/7?  Of 42?  Such statements make
plain sense to most people on first hearing, although making precise just
what that sense consists of isn't so easy.  Tossing it aside as meaningless
may be convenient but isn't compelling.

> But if that's how you want to redefine the word "random" then go
> for it.:-)
>
> This is obviously not the sense of "random" that JVN was talking about.

Indeed it was not.  In context, JVN's quip was very funny at the time.  But
most jokes lose their power to tickle after 50,000 words of analysis <wink>.