random

[Darren New]

Alex Martelli wrote:
> But why should "perfect information" about the dice tell me only
> that they're perfect, and not their state?

Because "the state" is that they're perfect. I.e., "the state" of a
radioactive atom is that it has decayed, or hasn't decayed, and the
half-life of the atom. There *is* *no* *state* to tell you when it
*will* decay. It's just not there. 100% of the information about the
atom is probabilistic. You don't know where it is. You only know that
it's *there* with 99.9999% probability. It might not even be there when
you look.

> That's like saying that
> "perfect information" about an algorithm tells me only it's a good
> one, and gives me no information about the state it starts in.

No, it's not. I'm not sure why you assert this. An algorithm is a
mathematical concept, and hence fully defined.

> > > I still haven't heard your definition of
> > > 'perfect' randomness, for example.
> >
> > Generally, this is something along the lines of:
> > Given all available information about the mechanism used to generate the
> 
> "available" seems to play a rather crucial role here, then.

No. "available" means "possible to be obtained in any way." What you
seem to be missing is that in the world of quantum physics, the
information just plain isn't there. You can go so far as to measure the
fact that it isn't there.
 
> > bits, and an arbitrarily long sequence of generated bits, it's
> > impossible to predict with >50% accuracy what the next bit in the
> > sequence will be.
> >
> > I'm not sure it always includes the first condition.
> 
> That would only leave the arbitrarily long sequence of generated
> bits and no other info?  Fine, then:

> > I don't think Chaitin's Omega meets this definition, since it is by
> > definition a single number than anyone can calculate equally well.
> 
> But from Omega's first N bits, you get no hint at all that lets
> you predict its N+1-th bit "with > 50% accuracy". 

How did you get the first N bits? If you can calculate them, so can I.

> So, if the
> definition does not include the first condition, from the bits
> only you're not going to get any farther than from N tosses
> of an idealized coin.

Sure. *I* can write an algorithm to calculate the bits of Omega. Then I
run my algorithm, see that the first N bits of its output matches the
first N bits of your sequence, and predict with very high probability
what the next bit is, right? If you calculate the first 100,000 bits of
Omega and give it to me, and you don't tell me that it's the first
100,000 bits of Omega, and I think to try calculating the first 100,000
bits of Omega and they match, then I guess the 100,001'st bit of Omega,
then I have a >50% chance of getting the next bit right.

If, on the other hand, you run a random number generator based on
quantum radioactive decay, or you flip a coin 100,000 times, and it just
*happens* to match the first 100,000 bits of Omega, and I notice that,
and I guess the 100,001'st bit of Omega, then I have still only a 50%
probability of being right.

This is why some people say that any given finite string cannot be
considered random or non-random by itself, without knowing how it's
generated.

-- 
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!