Re: definition of statistical test for randomness



"asdf" <qjohnny2000@xxxxxxxxx> wrote in message
news:1170421318.473941.109440@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Is there such a thing as a "valid" test for non-randomness - a
test that can be used to give you confidence.

No there isn't. The reason is very simple, in a true balanced coin flip
you
are just as likely to have
0000000000000000000000000000000000000000000000000000000000000000000000000000000
as
0101000110010101001001001110110100100100110110010010101001001001011010101010101
or
1111111111111111111111111111111111111111111111111111111111111111111111111111111
or any other pattern so no test on the output can ever test for
randomness.

- Suppose though that these 0's went on forever - then you could say
the string was not random.

No you couldn't, it is still a perfectly valid output from a random bit
generator.

- But if the number of 0's went above the number or 1's and below the
number of 1's an infinite amount
of times I'm not sure if this says the sequence is not random.

It means nothing compared to a perfect random bit generator.

Basically what I'm trying to figure out is why Martin-Lof definition
is a good definition for randomness of
infinite sequences.

It isn't. At best it is an attempt to quantify the apparent randomness of
the bit stream, this is radically different from the actual randomness of
the bit stream.

There simply cannot exist a test of actual randomness/entropy of a bit
stream. For apparent randomness/apparent entropy there are an infinite
number of them.
Joe


.



Relevant Pages

  • Re: It Has to be Contextual Randomness.
    ... Many ciphers can use raw random bits as a key (but usually a fixed ... infinite randomness" it means that the size of the shared keys are ... Two things - the key space of position vectors that comprise the keys ...
    (sci.crypt)
  • Re: Raatikainens critique of Chaitin
    ... You said that Omega is Chaitin ... and therefore its information content is infinite. ... identical to my mental irreducibility argument, ... There is also a nice section on Randomness in "The Unknowable", ...
    (comp.theory)
  • Re: Raatikainens critique of Chaitin
    ... You said that Omega is Chaitin ... and therefore its information content is infinite. ... identical to my mental irreducibility argument, ... There is also a nice section on Randomness in "The Unknowable", ...
    (sci.math)
  • Re: It Has to be Contextual Randomness.
    ... independent of computer power for all time. ... "Randomness at an infinite level" means this, ... amount of randomness, it's not "randomness at an infinite level". ... If your key generation methods are ...
    (sci.crypt)
  • Re: Anyone wanna help with a compression routine (new type)
    ... Pi is an infinite pseudorandom string. ... we would believe in its randomness and its infinite information ... But this sort rule has a very low information contents ...
    (sci.math.research)