random

[David C. Ullrich]

On Tue, 5 Jun 2001 18:41:54 +0200, "Alex Martelli" <aleaxit at yahoo.com>
wrote:

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

All I can _guess_ is that you're taking something
about frequencies as the definition of "probability".

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

Yeah, it's someone's constant.

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

Nope. [c] says nothing whatever about frequencies.
If you use a perfect RNG (which I'm taking as
defined by [c]) the ouput _need_ _not_ be normal.
It will be normal with probability 1.

> Now that we agree that
>normalhood (normalance?) of a bitsequence
>is achievable by arithmetic generators,

If you'd asked whether normality could
be achieved by an arithmetic RNG I would
have said "yes of course" at any time
during all this.

Look. Consider the following RNG. At startup
we initialize RandSeed to 0. Now we do this

def rand():
  global RandSeed
  RandSeed = RandSeed + 1
  return RandSeed

That is an RNG that _does_ achieve normality.
Do you _really_ think that JVN _overlooked_
this admittedly tricky algorithm? Like he says
anyone [etc], someone points out the rand()
above, and he replies "Oh, scuse me, sorry."

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

If simply outputting the bits of a normal
number gave something that satisfied [c]
you'd have a point. But it doesn't.

Look. We make an RNG that returns pi in
decimal. If it's an RNG satisfying [c]
then the probability that the first digit
is 3 is supposed to be 1/10. And the
probability that the first digit is 1 is
supposed to be 1/10 as well - that's 
what [c] says. Do you _really_ think it
makes sense to talk about the _probability_
that the first digit of pi is 3?

Answer the question instead of only replying
to the parts you feel like replying to.
_Do_ you think it makes sense to talk about
the probability that the first digit of pi
is 3? (Or rather: Does it really make sense
to say that the probability that the first
digit of pi is 1/10?)

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

You could biject this way between numbers
and _determinisitic_ generators.

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

A test that the bits-of-pi RNG will fail is
this: Reboot and check whether the first
digit returned is 3. Repeat. If you get
3 more than 1/10 of the time after a
large number of trials that's reason to
suspect you do not have a perfect RNG.

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

??? If we're talking about _sequences_ of
bits then I think I know what compressibility
means. I don't know what it means for an
RNG to be incompressible. (You're the only
person here who's insisting that the two
are the same - others have pointed out
more than once that there's simply nothing
"random" about the digits of pi.)

What's good enough depends on what you're
doing. For many purposes outputting the
digits of a normal number _is_ good enough.
But there can be a lot of correlation between
the digits in a normal number, rendering
them not good enough for other purposes.

> But is this
>the definition of 'perfect' you want to use?

I've already given _a_ definition above.
(If you note the definition of the word
"independent" you see that [c] is the
same as saying that the bits returned are
independent, and equal to 0 or 1 with
probability 1/2.)

>Or just a CONSEQUENCE of how you really want
>to define it...?
>
>
>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)