The paradigms in the computation, manipulation, and transmission of
information shift increasingly
from being random-variable oriented to individual-outcome oriented.
In theoretical terms, this means a shift
from Shannon's Information Theory to Kolmogorov's
Complexity Theory.
Complex structural data like sound files or video images
are not well modeled by methods that assume they consist
of a typical sequence of uncorollated independent outcomes
of a simple Bernoulli source or stationary  ergodic
source. For example, storing or transmitting the first
$1,000,000,000,000,000$ bits of $\pi = 3.1415 \ldots$ can be
done the hard way using Shannon theory, or the easy way
using a small program incorporating an approximation
algorithm that generates the successive bits $\pi$.
Thus, synthetic structural audio compression can reach
compression ratios of 10,000 to 1. Such structural data
can in principle be modeled by a random source. For example,
Tolstoy's ``War and Piece'' is one element out of the
the set of books or meaningful documents that have been produced
in the history of mankind, say at most one billion. With
every book equally likely, it contains about  30 bits of
information. This way, we can in principle
assume that there is a relevant
random variable that represents the complex structured information
objects appropriately. Practically, however, using Shannon
theory or general purpose compressors,
we estimate the redundancy at about 60\%, achieving
a compression ratio of about 2 to 1. This redundancy estimate
is based on the inherent assumption that the data consists
of uncorrolated items and is typical for a
simple random source like a Bernoulli or Markov
process.  Clever or
special-purpose compressors analyse structural features
of the data to achive better compression. The result is a code
that can be viewed as a Shannon-Fano code
and then translated back into an appropriate highly skewed distribution.
Viewing this as Shannon theory is begging the question.
Ultimately, one wants identify the unique combination of structural
features that characterize the data at hand. One way to do this is by
the Kolmogorov complexity approach. We shall show that, for example, the Shannon
entropy equals the expected Kolmogorov complexity of the outcomes, but only
up to an additive error term that equals the Kolmogorov complexity
of the probability mass function involved. In the limit, where we consider
an individual object, the Shannon view can be taken as concentrating
all probability on the outcome in question.
But then the correspondence breaks down:
the Shannon entropy becomes zero, and the error term becomes the complexity
of the outcome.Shannon ignores the object itself
but considers only the characteristics of the random source of which the
object is one of the possible outcomes, while Kolmogorov considers
only the object itself to determine the number of bits in the ultimate
compressed version irrespective of the manner in which the object arose.
For almost  every Shannon theory notion there turns out to be
a Kolmogorov complexity theory notion that is equivalent
in the sense that the expectation of the latter is
closely related to the former. We will review some of these relations.
This is joint work with Peter Gruenwald.