Re: Complexity; was: SQL


Daniel Parker wrote:
> Mikito Harakiri wrote:
> > Oliver Wong wrote:
> >
> > > > Random sequence is defined as
> > > > the one that can withstand all possible statistics tests.
> > >
> > > I haven't heard of this definition before. What does it mean for a
> > > sequence to "withstand" a test? Is a test a boolean function, and returning
> > > 'false' implies not-withstanding?
> >
> > One such test would be measuring frequency of 1s and 0s. If we get
> > frequency other that 1/2, then the sequence is not random.
> >
> I'm not sure that I fully understand this, but let's say that we have a
> uniform random process that results in the sequence
>
> 11111111111111111111111111111111111111111111111111111111111111
>
> This becomes a realization, the realized sequence is no longer random.
> This particular realization is no less likely to occur than this one
>
> 00101010101000101010101010101010101010111010111010101010101010
>
> They both have the same probability of occuring. It's not meaningful
> to say that one is more random than the other.

Your observation is correct. In fact, many papers on this topic (which
I fail to locate on the web) begin with something like this:

You gamble by tossing a coin and bet on heads (assume 1s). Your
opponent bets on 0s. He tosses a coin repeatedly and the output is

0000000000000000

You accuse him of cheating (implying that the coin is defect, or that
he has a sophisticated way how to throw a coin, etc). What is the basis
for your accusation? Well, the probability of this outcome is
2^(-length). But so is the probability of any other outcome of the same
lengh! E.g.

1001001100111001

This is why all this unsatisfaction with "standard" probability theory
as applied measure theory. Von Mises asked a question if randomness can
be defined in terms of frequences

http://user.it.uu.se/~vorobyov/Courses/KC/2000/l8.ps

and this was actually the beginning of the theory evolved through the
chain of contributions by Kolmogorov, Martin Loef, and then Chaitin and
others.

.

Relevant Pages

  • Re: Coin tossing guessing strategy...
    ... You need a precise string in exactly one order, ... with respect to sequences of n flips, is to note that if some sequence ... In fact, assuming a fair coin, all 10 coin sequences are equally ... probability distribution for the _difference_ between the number of ...
    (sci.math)
  • Re: Raatikainens critique of Chaitin
    ... >> should mention sequences of coin flips. ... >> Flip a coin any finite number of times and the resulting sequence has ... >> Flip a coin an infinite number of times and the probability that the ...
    (sci.math)
  • Re: How to determine causation?
    ... with 100% probability, but A also causes C with 100% ... and, for the second coin, the sequence is... ... Is there a causal relationship? ...
    (comp.soft-sys.matlab)
  • Re: Statistics question
    ... If somebody told me they flipped a coin and got 17 straight heads, ... How was the sequence determined? ... exactly where probability calculations applied to evolution fail. ...
    (talk.origins)
  • Re: Philosophical questions concerning physical Markov chains
    ... The realization is a variable that contains all ... but is an actualization of real potentials. ... constraints and the future exists in the present as a probability ... rather than causality. ...
    (sci.physics)