random

[David C. Ullrich]

On Mon, 4 Jun 2001 12:16:13 +0200, "Alex Martelli" <aleaxit at yahoo.com>
wrote:

>"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
>news:3b19393d.703539923 at news.okstate.edu...
>    ...
[...]
>
>
>Perhaps this subpart is about communication too:
[a]
>> about.) People don't usually try to prove things
>> by saying it's probably in a book somewhere...
>
>Right, but you didn't ask for a PROOF, the way I read
>your question, just:
[b]
>> Could you give us a hint regarding exactly what work
>> of Chaitin's shows we can get "truly random" numbers from
>
>..."shows".  I understand "show" and "prove" can
>be used as synonymous in some contexts, and maybe
>that is how you were using 'show' here -- I had not
>read it as such.  Anyway, you were only asking for
>a _hint_ about exactly what work of Chaitin was the
>relevant one, not the proof itself -- and why isn't it
>correct to 'hint' that his recent book titled "Exploring
>Randomness" looks like the right one?  I couldn't and
>can't be positive, not having received and studied it
>yet, but it seemed a potentially useful pointer to supply
>in response to a request for just a "hint"!

Um, actually (i) when I ask for a hint regarding what
work of Chaitin's shows that JVN was wrong, where _I_
come from it's clear that what I actually want is a
hint regarding _how_ Chaitin shows it's wrong - saying
it's probably in a book somewhere doesn't really say
anything about that. But you're right, when I said
[a] I had forgotten exactly how I'd phrased [b].
(ii) My attitude towards a few things had changed somewhat
between the time I said [b] and the time I said [a];
had to do with some people seeming to be engaged in
some sort of holy crusade, complete with loyalty
oaths... never mind.

>> I hope I've clarified the contradiction you mention
>> in this post - while I don't think it was actually a
>> contradiction, I do agree that seeing it as
>> contradictory is not all that unreasonable, I
>> would have stated things much more carefully
>> if I'd known there was going to be a quiz.
>
>Same here.  I have used sloppy, approximate and
>perhaps misleading wording.  There are enough real
>disagreements without artificially constructing more.
>
>Neither of us was 'all that unreasonable' in taking
>some of the other's words in pretty bad ways
>(including contradictory, ridiculous, offensive, &c),
>and maybe, as we didn't know there was going to
>be a quiz, it was also not totally unreasonable to
>spend 'just' hours rather than entire days in crafting
>our statements.  The overall result _was_ rather
>unreasonable though:-).

That seems like a reasonable way to put it.

>> First, I don't think that it makes
>> sense to talk about a perfectly
>> random _sequence_, any more than
>> it makes sense to talk about a random
>> number. Someone wanted to know
>> how random 6 was.
>
>If you take away the sting of 'perfectly', it
>seems to me that talking about 'how random
>is a number [sequence of bits]' does make
>sense. 

The word "random" means many many different
things. I did not say that talking about a
prefectly random sequence did not make any
sense.

How can I say I didn't say that in the face
of a _quote_ that shows that I said exactly
that? Context. I was replying to your question
about what I meant by "perfect randomness"
or similar constructions. Yes, there are
certainly senses in which one sequence can
be regarded as more random than another.
Those senses are irrelevant to the question
I was trying to answer - when we say one
sequence is more random than another that
simply is not the "random" I was talking
about.

> 6, aka 110, is not very random because
>it can be output by a tiny program indeed in
>any given UTM.  00000000000000000000 is
>several bits, but not very random, as, again,
>the program to output them can be made small.
>000001010011100101110111's structure is
>not quite as evident, but clearly there as soon
>as you cut the string up 3 bits at a time -- again
>a small program is possible.  It starts getting
>harder with 0011101000100001011000100101
>(a string I just input 'at random':-) -- the fact
>I don't see its structure doesn't mean it have
>one (and apparently I have no way in general
>to prove a given long bitstring _doesn't_ have
>"structure" -- to find a lower bound on the
>amount of bits needed to encode it).
>
>But this is close to the way a 'man in the street'
>would use the word 'random' about a sequence
>of bits -- including the possibility that one seems
>random (I haven't noticed its structure == I
>only so far have a program to emit it that is
>large) but really isn't (it does have structure,
>there _is_ a small program generating it).  If
>we can give a useful technical meaning to a
>word that well matches its common-or-garden
>use, why not?

I never said we should not. Although usiing
different words for different things would
be preferable it doesn't always work out
that way.

>But I do agree that JVN was likely not thinking
>of this meaning of 'random' as it was (AFAIK)
>not used in his time.
>

[c]
>> A perfect RNG is one with this property:
>> If you use it to generate N bits then each
>> sequence of N bits appears with probability
>> 1/2^N. It has this property for _every_ N.
>
>So the computation of Omega is a perfect RNG --

No, in the sense that I'm using the words
in [c] the computation of the bits of Omega
is _not_ a perfect RNG. Even ignoring the
question of whether we can call it a
"computation". The first bit of Omega _is_
either 0 or 1. To be a perfect RNG in the
sense in which the words were intenbded
in [c] the first bit would have to be
random, equal to 1 with probability 1/2
and 0 with probabilty 1/2. Since it _is_
a _specific_ well-defined number it simply
is not at all clear what it can possibly
mean to talk about the "probaility" that
the first bit is 1.

>and isn't there an old proof about pi having
>this property too?  (dim memories here...)

The property you're talking about is that
all sequences of N bits appear in the
sequence with frequency 2^(-N) (asymptoticaly).
This is not the same as [c].

The word is "normal". It may well be that
Omega is a normal number. It is _not_
known that pi is normal. It seems pretty
likely because most numbers are normal
(like if you choose a real "at random"
you get a normal number with probability
1) but nobody has a clue how to prove
that pi actually is normal.

>> (Hence an algorithm, as the word is usually
>> defined, cannot be a perfect RNG. Because
>> it has only finitely many states - it must repeat
>> after a while, and hence for large enough
>> values of N it is not true that all sequences
>> of length N are equally likely.)
>
>Sorry, but I must be missing something.  Can't
>I write an algorithm to compute as many bits
>of pi as I want?  Sure, the amount of state it
>will have to save when it has computed K bits
>of pi, in order to compute the next N (the next
>'run'), will grow with K, having no upper bound.
>
>But isn't that the reason we have Turing machines,
>their infinite tape?-) 

Um, you're absolutely right about this. I guess
I was assuming a bounded amount of storage in 
that "proof", and I certainly didn't mean to
assume that; if there's a bound on the storage
space then everything's different.

I still suspect it's true that given anything
which I would call an arithmetic RNG there
exists a "randomness test" that the RNG will
fail, which a "perfectly random" RNG would pass.
But the proof above is nonsense, because I do
mean to allow unbounded storage (otherwise
things are boring).

> Isn't a Turing-machine
>program (even one exploiting the fact that the
>tape is unbounded) "an algorithm", at least when
>it can be proved to run to completion in finite
>time at each run?  Any given run will only use a
>finite portion of the tape, but we don't have to
>know how much in advance, do we?  At each
>successive (finite) run, more and more of the
>tape could be used -- we ain't gonna run out.
>
>In other words, are you saying there cannot
>exist an algorithm that is able to compute any
>arbitrary amount of bits of pi on request, and (having
>computed the first K of them and kept whatever
>other auxiliary state it needs to on the Turing
>machine tape) can at any time be asked for
>"and now the next N please" for any N?  Why
>would this Turing-machine program not be an
>algorithm, by the definition you want to use?
>It seems to me to meet any definition of
>algorithm I have ever encountered, but maybe
>I have not encountered enough?
>
>If you concede such an algorithm is possible,
>then how does it "have only finitely many
>states", and why must it "repeat after a while"?
>Surely it's proven that pi's bits (or digits in
>any integer base of your choice) _don't_ repeat
>after a while -- that's why pi is *irrational*, no?

I've conceded your points in the last three
paragraphs, but:

>Now if my dim memories are correct, wouldn't
>this algorithm be a "perfect RNG" by your
>definition as here given? 

No. First, note that we do not know that
pi _is_ normal. But supposing for the sake
of argument that it is normal (it's not 
hard to give an algorithm that _does_ 
generate the bits of a normal number -
let's call that number pi): It's not
a perfect RNG because there's nothing
random about it. The first digit after the
decimal _is_ 1, and the second digit
_is_ 4. There's nothing at all unpredictable
or incompressible about it - anyone who
knows how to calculuate the digits of
pi can "predict" what the digits are.

To put it another way: Consider the number

0.0123456789101112131415161718192021222324...

consisting of all the natural numbers written
one after the other (took decimal to make 
the pattern more clear). This _is_ a normal
number, which is to say that the digits of
this number _are_ "random" in the sense
that we're assuming the digits of pi are
random. It doesn't really look like a
"random" number, does it? Seems kind of
easy to predict the next digit.

> Or was this definition
>meant to be incomplete, with clauses to be
>added progressively as needed to eliminate
>otherwise uncomfortable algorithms from the
>"perfect RNG" class?-)

The definition I gave _was_ _very_ incomplete,
but nobody's mentioned why. It certainly was
not meant to be incomplete in the sense you
ask about here - if someone pointed out the
actual incompleteness I'd reply that that's
just the way it is...

>Alex
>
>
>



David C. Ullrich
*********************
"Sometimes you can have access violations all the 
time and the program still works." (Michael Caracena, 
comp.lang.pascal.delphi.misc 5/1/01)