random

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b1ce391.2243151 at nntp.sprynet.com...
    ...
> [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.
    ...
> The property you're talking about is that
> all sequences of N bits appear in the
> sequence with frequency 2^(-N) (asymptoticaly).

Thanks!

> This is not the same as [c].

I fail to see the difference, when I use
my hypothetical normal-but-computable number
(thanks for informing me that pi is not known
to be, just so hypothesized, but that there are
others that are known to be -- and the vaguely
Cantorian construction of just writing the
integers in sequence one after the other, that
you use later, sounds quite a simple example
and rings some vague bell...) as a 'generator',
by asking about its next N bits each time.

I agree there need be nothing random or
non-compressible about the hypothetical
number -- (c) didn't mention anything about
that, just "normality" (normalness?) of
the bitsequence.  Now that we agree that
normalhood (normalance?) of a bitsequence
is achievable by arithmetic generators,
we can presumably lay this sub-sub-sub-part
of the discussion aside (but meanwhile I
have refreshed my dim memories and thereby
benefited -- thanks).


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

If you look at the way disk prices are going,
we might be there: place a sum in a bank, each
time the disk is close to running out take some
of the interest and use it to go buy a new disk...
as long as you only use a finite amount _at a
time_, you're approaching UTM's unboundedness:-).
(hot-swap RAID controllers assumed of course:-).


> 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).

And we still need the "perfectly random RNG"
definition to allow us to see if we can prove
we can't do it arithmetically, since [c],
while part of that definition, is not sufficient
for such proof (nor, in fact, to meet what _I_,
with my much-weaker intuitive criteria, would
deem 'random enough for me' -- pi, or whatever
normal number must take its place, being all
too predictable).


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

Yep, it has lot of structure and can in fact
be generated by a very small program (as can
pi, but this one looks like I can make an
even smaller program).

So what is "perfect" in a "perfectly random"
normal real number?  I realize you don't
want to talk about random NUMBERS (or
sequences) but random GENERATORS, but if
I have a number I can make a generator and
vv from the actual sequence of bits a
generator gives me I can make a number --
say there is no "rewind", no time machine
(Guido has the only one and he ain't gonna
lend it to us), so that all we can do is
ask the generator, a black box, for "N
more bits please" and it will comply,
now couldn't we biject between generators
seen this way and real numbers?

Maybe we can't, but if so I fail to see
why.  How should we define a "generator"
in a way that's general enough to let us
study under the same hat very different-
nature ones (so we can't peek under the
hood, just look at the output) if not as
a machine that gives me "N more bits" when
I ask for them?  Now we can maybe devise a
test that we can prove the machine will
fail if it is generating by using arithmetic
while the "perfect" generator will pass?

I don't think it needs to be a finite-time
test, either (else the 'perfect' part
seems to have little use:-).  Compressibility
looks nice to me here.  No compressibility in
the 'perfect' generator, surely.  But is this
the definition of 'perfect' you want to use?
Or just a CONSEQUENCE of how you really want
to define it...?


Alex