off on a tangent...

[Terence D. Sanger]

David Wolpert writes:

> To illustrate just one of the possible objections to measuring
> randomness with Kolmogorov complexity: Would you say that a
> macroscopic gas with a specified temperature is "random"? To describe
> it exactly takes a huge Kolmogorov complexity. And certainly in many
> regards its position in phase space is "nothing but noise". (Indeed,
> in a formal sense, its position is a random sample of the Boltzmann
> distribution.) Yet Physicists can (and do) make extraordinarilly
> accurate predictions about such creatures with ease.

In thinking about this, it seems that David is right: the gas is, in some
important sense, highly structured.  In particular, its *statistics* are
stationary no matter how they are sampled.  This means that a temperature
sample from any part of the gas will predict temperatures in other parts of
the gas, according to the law of large numbers.

Consider a different statistical model:

Choose a random number to be the mean of a distribution on a finite set of
random variables. Divide the set in half, choose a new random number and
add it to the left half's mean and subtract it from the right half's mean.
Divide the half-sets in half, choose two new random numbers, and continue
to split each half by adding and subtracting random numbers until no more  
splits are possible. 

Now we have:

1) All random variables are independent and identically distributed (this
is basically a random walk).

2) The mean of the distribution is equal to the first random number chosen
(at each step, the mean does not change).

3) The mean of any "binary" region (half, quarter, eighth, etc.) is 
a poor predictor of the means of neighboring regions.

4) Sample means do not converge uniformly to the ensemble mean, unless
samples are chosen randomly across region boundaries.

In some sense, this is a very highly structured field of random variables.
Yet prediction is much harder than for the random gas.

(In case anyone is interested, this distribution arises as a model for
genetic diseases of mitochondria.  If a cell has N mitochondria, M of which
are defective, then at cell division it will pass a random number of normal
and defective mitochondria to each daughter cell, where the total number of
defective ones passed on is conserved and is equal to 2M.  The daughter
cells, in turn, will do the same thing.  The problem is that a local biopsy
to count the number of defective mitochondria will not predict biopsy
results from other sites.) 

Terry Sanger
tds at ai.mit.edu