random

[Darren New]

Alex Martelli wrote:
> > Yep. The fun thing about quantum physics is that *complete* information
> > is available about the state of the generator, and you *still* don't
> 
> Except it's not -- you can't be told position AND momentum
> of the particles (either, but not both). 

But that's not the kind of information you get about the system.
Understand that the problem is that you can't determine both momentum
and position. The problem is that both don't exist at the same time.
"Complete information about the system" is the probabilities that the
particles are in certain states. Because the particles really aren't in
any particular state, the "complete information" *is* the probabilities.
That's 100% of the information. It's not that there's information there
you can't get. The information just plain isn't there.

Again, I can give you complete information on a fair die, and it doesn't
give you any information that would allow you to predict which number
comes up next.

> The information isn't
> (and presumably can't) be complete.

No, the information *is* complete. It's just not sufficient to tell you
what you want to know. That's the *reason* why it's random.

> > No. The point I'm discussing is that an algorithm cannot generate
> > randomness.
> 
> Maybe it can't "generate" the randomness, but it can "unearth"
> it if it's hidden in the underlying "deep truth of mathematics".
> Which seems to be a way in which one can read C's thesis.

If two people can each generate exactly the same sequence of bits, given
a description of what to do to generate them, then the bits aren't
random.

> > No matter how much complexity you add to a mathematical
> > formula, it's still 100% predictable if you know what the formula is.
> 
> So the _amount_ of randomness is constrained by 'program
> size'.  Thus, it's finite for a finite-size program (program size
> being an upper bound, and it being, it seems, impossible to
> get a lower bound).

Well, the way I'm using "random" means "predictable given complete
information". If I can replicate what you do and get exactly the same
results, then the results aren't random. I would imagine that's what JVN
was talking about.

> > This is untrue of physical random number generators.
> 
> I.e., a physical RNG cannot be finitely described?

Err, no. Your interspersing your own comments with mine.

I said, no matter how complex it is, if you know a mathematical formula,
the results of calculating its value are 100% predictable. (You may not
be able to predict it without calculating the value, which is what C is
talking about, but you can certainly predict what someone else will
calculate.)

This is untrue of a true (not pseudo) random number generator based on
(say) quantum effects. I can build two RNGs that are identical 100%, and
they'll generate different random numbers.

> Dice that are massive enough may presumably be similarly
> finitized -- give me the initial state (position & momentum)
> accurately, and in principle I can apply classical mechanics
> and compute the positions at rest. 

Except that quantum physics says this doesn't work.

Sure, *if* the universe were Newtonian, then physical RNGs would be no
better than algorithmic RNGs with lots of seed bits. But the universe
isn't Newtonian.

> Even if the dice are thus
> predictable-in-principle, it doesn't mean they aren't a RNG --
> maybe not a 'perfect' one if you include the condition about
> being given ALL information (or all AVAILABLE information
> for a good-enough value of 'available':-).

Again, you're missing the point of 'available'. It's not that you can't
measure the value. It's that the value isn't there. That's the funky
part of quantum physics. 

It's like, if you go to the sink and close your eyes and turn on one
tap, you'd expect the water to be hot or cold. But in quantum physics,
it's not. It's just luke warm. It's not that you don't *know* whether
it's hot or cold. It's that the water doesn't behave like it's hot, and
doesn't behave like it's cold, *unless* you stick a thermometer in it.
 
> But that doesn't mean that suddenly card decks or dice
> "aren't random" any more (or that they never were).  For
> all "finite-randomness generators", the interesting issue
> becomes "how much randomness".

They're random. They're physical systems. I don't know why you think
they're not.

What's not random is algorithms that take a seed value (or a key) and
generate lots of hard-to-predict-without-the-seed numbers.

> > In an algorithm, it's never going to be bigger than your seed.
> 
> Not sure what you mean by "seed" in the general case of
> any algorithm whatsoever. 

The "seed" is the part that's different the second time you run the
algorithm. 

> Even assuming the algorithm
> has to have an input and we must call the initial input
> value 'seed', what can you predict if all I tell you is that
> "the seed" is 32304823408349093?  Nothing, it seems to
> me, unless the information you receive also includes the
> program that's going to much this "seed".

That's not how you measure randomness. The way you measure randomness is
to say "given as much output as I like, what's the probability that I
can accurately predict the next output value." Hence, if you shuffle a
deck of cards and deal out 51 of them, how random is the value of the
last card? Answer: not at all. This is how "card counting" works at
casinos, and why they shuffle the cards well before they're all used up.

> So, why confuse
> things by putting "seeds" into the picture?  Let's just say
> that amount of randomness (as measured in bits) can never
> be greater than the size of the program -- it's easier to
> account for any literal constants as part of the program's
> size than vice versa, isn't it?

Fine. Then you're counting the entire program as a "seed" for the
computer it's running on. That's just another way to look at it. :-)
Then the "seed" is the program and the "algorithm" is the microcode
that's in the CPU. :-)

> Well, Chaitin's approach boils
> down to defining amount of randomness as _minimal_
> programsize to generate a sequence (which turns out to
> be undecidable in general, if I understand him correctly:
> any actual program that does the generation gives me an
> upper bound on the randomness of its output, but in
> general I have no way to prove a lower bound).

But that's not the "randomness" that JVN was talking about. 
 
> > You don't get randomness from a deck of cards. You get randomness from
> > *shuffling* a deck of cards. The randomness comes from not knowing
> > exactly what the fingers were doing.
> 
> Ah, from lack of information?  The information is apparently
> not-available because nobody bothered to notice it?-)
> 
> So is lack of information randomness?-)

No. 
 
> > If you shuffled the cards algorithmically (e.g., with a mechanical card
> > shuffler that very reliably put them in the same order) then they
> > wouldn't be random at all, *if* you knew exactly how the mechanical card
> > shuffler worked. That's the equivalent of using an algorithm to generate
> > pseudo-random numbers.
> 
> And it turns out to be a good approximation of what happens when
> a human being shuffles cards in practice -- he or she tends to give
> a finite (and small) number of riffles that are rather predictable.

Which is why cards are a *poor* source of randomness.

> Saying that the resulting deck-order "isn't random at all if you
> knew" again seems to consider randomness totally congruent to
> lack of information.

There are lots of meanings of the word "random". There are many ways for
things to *not* be random. Knowing exactly  the sequence of a deck of
cards means the cards aren't in a random order, as far as you're
concerned.

On the other hand, with quantum physics, the lack of information is
built into the system. There's no information there for you to discover
if you just looked hard enough. Hence it's "truly random."

>  It isn't *perfectly* random, sure, but that's
> a long way from saying it isn't random *at all*.

Right. That means you have a greater-than-chance method for predicting
the next card as you deal them out, but a less-than-perfect chance.

On the other hand, if I know the program you're running, I have a
perfect chance of predicting the next output from it, assuming your
hardware correctly interprets the algorithm.

> A shuffled deck of cards may be very far from your Platonic
> ideal of "a physical RNG", but it's pretty physical, has been
> used as a RNG for centuries, and (as any card-player can
> attest) generates or unearths or whatever SOME amount of
> randomness.  Maybe those who shuffle card decks to get
> randomness are "in a state of sin" (those who call that deck
> "the Devil's Picture Book" would no doubt agree:-), but they
> do get (finite amounts of) randomness, not 'none at all'.

Again, I'm not sure why you think shuffling cards gives you no
randomness. I don't think I ever said anything to imply this.


> > > It seems more fruitful to me to consider the amount
> > > of information, i.e., a quantitative assessment of randomness,
> > > rather than claim that only if that amount is 'infinite' can
> > > the word 'randomness' be properly used.
> >
> > It depends, again, on which meaning of "random" you want to use. For
> > some folks, "unpredictable" and "random" are two different things.
> 
> And "random" means instead...?  Didn't you also define it as such?

Errr, no. It's not the "amount of randomness" that's infinitely
unpredictable. It's the size of the object being studied that is
infinite. It's hard to talk about the randomness of a single finite
string, because once you tell me what string you're talking about, it's
not random any more. 
 
> I'm not particularly interested (in this thread) to understand JVN,
> I _am_ interested in applying the word "randomness" to the
> breaking of structure and *difficulty* of prediction that I can
> study in finite systems, rather than have it reserved for some
> kind of *impossibility* (infinite difficulty) of prediction.

It's not "inifinite difficulty", but "infinite string". In other words,
how random is the binary string "1001010010011100100"? How random is the
binary string "0000000000000000000"? Such questions don't make any
sense.
 
> > > If you have COMPLETE information about the dice &c (taking
> > > a HUGE number of bits, no doubt) you can predict their
> > > trajectories, bounces (if allowed), rolls, AND final results.
> >
> > No. Quantum effects will screw that up.
> 
> Aren't dice (by far) massive enough to avoid that?

No. The die as a whole will not show quantum effects. The die as a whole
is too big to ever expect it to disappear from one place and reappear at
another. But every time it hits the table, it has a quantum interaction
between the atoms in the die and atoms in the table.
 
> > If you start with a pooltable with perfect spheres for poolballs,
> > perfectly racked, you cannot sink all 15 balls with your eyes closed.
> > The probability cloud for the location of the last ball will be larger
> > than the pooltable.
> 
> Interesting -- I can't refute this claim as I wouldn't know how
> to go about it.  Is this result independent of the masses and
> diameters of the balls, temperature, &c, or does it specifically
> hold for the actual average sizes/temperatures/&c as used in
> pool?  Unfortunately, pool is definitely not among my skills.

I don't know. I wasn't the one that did the math. And it was a long time
ago. If I recall correctly, it assumed normal poolballs perfectly
manufactured. The trick is that since the balls are round, every little
error is going to get magnified.
 
> > > If you have complete information about the algorithm and
> > > the relevant part of the state of the computer where it
> > > runs, again you have predictability.
> >
> > And that's why VN said calling it "random" is sinful.
> 
> Aha, I knew it would get to attaching sinfulness to the way one
> uses words -- and, wouldn't you know it, exactly the word-use
> I care about in the context of this thread: what's now being
> directly attacked (by your interpretation of VN's words -- I do
> not know how demonstrable this interpretation is) is the attempt
> to measure the *amount* of randomness... the amount of
> information that would minimally afford prediction about the
> random phenomenon. If anything AT ALL predictable cannot
> "by definition" be random AT ALL, then "amount of randomness"
> becomes a meaningless, self-contradictory phrase.  Which is
> exactly what I think is unsupportable...

Err, no. If you have complete information about the algorithm, including
the seed, then the output of the algorithm is 100% predictable. That's
kind of the definition of an algorithm. And I'd chance to say that
anything that's 100% predictable is not "random" in any sense of the
word at all. I'm not sure how you'd go about making a list of random
predictable numbers.

Now, if you *don't* tell me the algorithm, it's not the algorithm that's
making the random numbers. It's you making up a random algorithm. But
that's no more "random" than your age. The age you'll be five years from
now is five years older than today. That I don't know how old you are
today doesn't mean your age five years from now is "random". 

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