Re: Predicting the Future and Kolmogorov Complexity

On Mar 15, 5:06 pm, "R. Baldwin" <res0k...@xxxxxxxxxxxxxxxxxxxx>
wrote:

It's a very minor point that is pretty much irrelevant to the main
issue of determining non-randomness. Martin Lof's take on randomness,
which is based on gambling, has been shown to be "equivalent" to the
Kolmogorov approach.

http://www.dartmouth.edu/~chance/chance_news/recent_news/chance_news_...

I haven't pulled Martin Löf's 1966 article yet, but none of the articles I
have read about it support your idea that Martin Löf's take on randomness is
based on gambling.

Yes, it is - - The same is true of Chaitin's take on algorithmic
information theory:

And there is a connection between my ideas and Boltzmann's, because
looking at the size of computer programs is very similar to this
notion of the degree of disorder of a physical system. A gas takes a
large program to say where all its atoms are, but a crystal doesn't
take as big a program, because of its regular structure. Entropy and
program-size complexity are closely related... [Notice the connection
Chaitin draws to entropy and how that relates to time and
predictability]

But if you look at how a roulette wheel behaves, then there is no
pattern, the series of outcomes cannot be compressed. Because if there
were a pattern, then people could use it to win, and having a casino
wouldn't be such a good business! The fact that casinos make lots of
money shows that there is no way to predict what a roulette wheel will
do, there is no pattern---the casinos make it their job to ensure
that! [Notice the connection Chaitin points out to gambling]

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lowell.html

There is a relationship between Kolmogorov randomness and Martin Löf's. They
are not the same. See Schnorr's Theorem.

These concepts are very closely related. To argue that they are not
identical concepts is to miss the point.

However, this isn't the end of the issue. As it turns out, the choice
of the UTM doesn't matter much when it comes to the KCC of longer and
longer sequences. "Suppose that U and U0 are both universal machines.
Then there is a constant k such that for any s, the complexity of s
relative to U never differs from the complexity of s relative to U0 by
more than k. So: fixing U and U0, in the limit as the strings get
larger, the particular choice of UTM matters less and less."

http://www.princeton.edu/~adame/teaching/PHI322_S2003/handout/kolmogo...

Yes, that is true. This is the invariance theorem. Note, however, that
depending on U and U0, k can be very small or very large.

Yes, but whatever k is, it forms an upper limit. Regardless of what
this limit is for a finite portion of a string, it matters less and
less because of its fixed nature as one considers larger portions of
the string.

The constant doesn't matter if we consider infinite length output strings.
When we consider finite length output strings then k becomes important.

The k becomes less and less important as one considers longer and
longer *finite* portions of a particular string.

Try to think about the average length of prefix code for the codeset that
implements all possible Turing Machines on a given Universal Turing Machine.
It is a big number. Which Turing Machines have short codes and which ones
have long codes? That is arbitary. Does the "print X" Turing Machine have a
short code or a long one? That is arbitrary.

Again this matters less and less as you consider longer portions of a
given string.

So, you see, if your selected UTM has to increase its size as the size
of the string increases in order to make the string's KCC equal to
zero, then there seems to be a relationship here to predictability.
For example, certain UTMs do not have to increase in size to reproduce
a specific sequence of increasing size. Such a situation is capable
of providing a great deal of predictive value with regard to what will
come next.

There is a relationship between Kolmogorov Complexity and predictability,
but it does not result in "a great deal of predictive value for what will
come next."

How then do you define predictability? Is it not a process by which
you can predict the future more accurately by some measurable degree?

Martingales based on complexity measures use the assumption that if
substrings are observed earlier in the string, they will occur later in the
string at some frequency, and you can eventually make money by covering bets
on all the substrings based on their frequency of occurence. They don't
predict what will come next.

The odds that some particular sequence will come next over some other
potential sequence is what is being bet on here. That's predicting
the future of what will come next with greater predictive value than a
purely random sequence without evident bias would allow.

"Pi has low Kolmogorov complexity as it can be specified by a short
algorithm, whether it's Gauss's summation or one of the newer digit-
specifying algorithms. On the other side of the spectrum, the million
random digits can't be derived in any other way besides specifying
them in their entirety. The algorithm used to compute pi doesn't
change in size depending on how many digits are needed, it has a
constant Kolmogorov complexity. Since the algorithm used to determine
the random digits is in fact the digits themselves, it gets larger
with each additional digit -- it has a linearly increasing Kolmogorov
complexity."

http://everything2.com/index.pl?node_id=763572&lastnode_id=0

"Algorithmic complexity: A.K.A. Kolmogorov-Chaitin-Solomonov
complexity.

I'm not sure what point you are trying to make here.

If the algorithm increases linearly with increasing sequence length,
you can't use the algorithm to predict what will come next. On the
other hand, if the algorithm does not increase with increasing
sequence length, you can use it to predict what will come next with a
very high degree of accuracy - i.e., pi.

Given that certain assumptions about the string hold true, that is correct.
The assumptions do not hold for all strings.

That's true. Nothing is absolutely certain. That's one of the points
of algorithmic information theory. A prediction of the future could
always be mistaken. However, given the success of the past, the
predictive value of the hypothesis continues to increase with each
additional success.

All that is needed to use KCC for prediction is knowledge that the UTM
size doesn't need to be increased in order to keep the KCC of a
growing sequence the same. I'd say that is a very fine hair you are
splitting. MML, though not exactly the same as KCC, seems very
closely related.

I just said MML is related to Kolmogorov Complexity! That isn't the
point.
Suppose we have a string S with a complexity K of 10 bits on machine U.
What
is the next symbol in the string? If your idea is correct, you can tell
me.

The point is that if chosen algorithm does not increase with
increasing string length, it offers a high degree of predictive
value. In other words, one is able to demonstrate that the string is
less and less likely the result of random generation. That's the
point.

In the articles I've read, the martingales do not rely on K remaining
constant with increasing output string length. They rely on averaging K as
new outputs appear, which tends to converge to Shannon's entropy. Such
Martingales involve a weaker version of random than Martin Löf'.

Algorithmic randomness avoids the issue of whether the string resulted from
a non-deterministic source.

Not true. Algorithmic randomness is all about detecting a real bias
in the source of a string. The ability to average k without it
constantly increasing is what allows the hypothesis to gain predictive
value of what will come next. Without this ability of knowing, with
at least greater certainty than 50/50 if a 0 or 1 will come next in a
supposedly fair coin toss, there would be no martingale predictability
at all and the source would be assumed to be "random".

Sean Pitman
www.DetectingDesign.com



.

Relevant Pages

  • Re: Long body guitars
    ... The original dreadnought guitar design was done by a foreman at Oliver ... That same body shape was used for the ukuleles which Martin made for Ditson ... I am having Scott Baxendale build me a 12 string ...
    (rec.music.makers.guitar.acoustic)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.math.research)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.physics.research)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... said you know that Chaitin was influenced by concepts of randomness ... there actually exists the potential for predictability. ... depending entirely on the choice of UTM. ... "For any string S, there is a universal machine Us such that the complexity ...
    (talk.origins)
  • Re: Regular Expression for validating a url field
    ... (Do not use the tab character for indentation, ... against a supposed string value, and since you do not do perform a strict ... If x is NaN, return false. ... `false' is returned to the calling algorithm, ...
    (comp.lang.javascript)