Biomedical Engineering Reference
In-Depth Information
is the same as maximizing the extra information about the initial condition
x
provided by each symbol of the sequence '(
x
).
14. Quantum versions of CA are an active topic of investigation, but
unlikely to be of biological relevance (246).
15. In a talk at the Santa Fe Institute, summer of 2000; the formula does not
seem to have been published.
16. A simple argument just invokes the central limit theorem. The number
of points falling within the shaded region has a binomial distribution,
with success parameter
p
, so asymptotically
x/n
has a Gaussian distribution
with mean
p
and standard deviation
. A nonasymptotic result
comes from Chernoff's inequality (281), which tells us that, for all
n
, we have
Pr(|
x/n
-
p
| F) < 2
e
-2n
F
2
.
17. The chain needs to be irreducible, meaning one can go from any point to
any other point, and positive recurrent, meaning that there's a positive probabil-
ity of returning to any point infinitely often.
18. Unless our choices for the transition probabilities are fairly perverse, the
central limit theorem still holds, so asymptotically our estimate still has a Gaus-
sian distribution around the true value, and still converges as
N
-1/2
for large
enough
N
, but determining what's "large enough" is trickier.
19. An important exception is the case of equilibrium statistical mechanics,
where the dynamics under the Metropolis algorithm
are
like the real dynamics.
20. For a pedagogical discussion, with examples, of how compression algo-
rithms may be misused, see http://bactra.org/notebooks/cep-gzip.html.
21. The issue of what language to write the program in is secondary; writing
a program to convert from one language to another just adds on a constant to the
length of the overall program, and we will shortly see why additive constants are
not important here.
22. Very short programs can calculate Q to arbitrary accuracy, and the
length of these programs does not grow as the number of digits calculated does.
So one could run one of these programs until it had produced the first two quad-
rillion digits, and then erase the first half of the output, and stop.
23. (167) is perhaps the most notorious; see (168) and especially (169) for
critiques.
24. It is certainly legitimate to regard any dynamical process as also a com-
putational process, (284-286,195), so one could argue that the data
are
produced
by some kind of program. But even so, this computational process generally
does not resemble that of the minimal Kolmogorov program at all.
25. It is important to note (185, ch. 3) that if we allowed any possible model
in 2, finding the minimum would, once again, be incomputable. This restriction
to a definite, perhaps hierarchically organized, class of models is vitally impor-
tant.
26. Take our favorite class of models, and add on deterministic models that
produce particular fixed blocks of data with probability 1. For any of these mod-
ppn
(1
) /
