\newpage \subsection{Randomness and Complexity.\label{kolm}}

The obvious definition of a random sequence is one that has the same properties
as a sequence of coin flips. But this definition leaves the question, what {\em
are} these properties? Kolmogorov resolved these problems with a new definition
of random sequences: those with no description shorter than their full length.
See survey and history in [Kolmogorov, Uspensky 1987], [Li, Vitanyi 1993].

 \paragraph {Kolmogorov Complexity} $K_A(x/y)$ of the string $x$ given $y$ is
the length of the shortest possible program $p$ which lets algorithm $A$
transform $y$ into $x$: $\min\{(|p|): A(p,y)= x\}$. There exists a Universal
Algorithm $U$ such that, $K_U(x)<K_A(x)+O(1)$, for every algorithm $A$. This
constant $O(1)$ is bounded by the length of the program $U$ needs to simulate
$A$. We abbreviate $K_U(x/y)$ as $K(x/y)$ or $K(x)$, for empty $y$.

An example: For $A: x\mapsto x$, $K_A(x)= |x|$, so $K(x)<K_A(x)+O(1)<|x|+O(1)$.

Can we compute $K(x)$? One could try all programs $p, |p|< |x|+ O(1)$ and find
the shortest one generating $x$. This does not work because some programs
diverge, and the halting problem is unsolvable. In fact, no algorithm can
compute $K$ or even any its lower bounds except $O(1)$.

Consider an old paradox expressed in the following phrase:
	``The smallest integer which cannot be uniquely and clearly defined
	by an English phrase of less than two hundred characters.''
 There are $< 128^{200}$ English phrases of $< 200$ characters. So there must
be integers that cannot be expressed by such phrases. Then there is the
smallest such integer, but isn't it described by the above phrase?

A similar argument proves that $K$ is not computable. Suppose an algorithm
$L(x)\ne O(1)$ computes a lower bound for $K(x)$. We can use it to compute
$f(n)$ that finds $x$ with $n< L(x)< K(x)$, but $K(x)< K_f(x)+ O(1)$ and
$K_f(f(n))\le |n|$, so $n< K(f(n))< |n|+O(1)= \log O(n)\ll n$: a contradiction.
So, $K$ and its non-constant lower bounds are not computable.

A nice application of Kolmogorov Complexity measures the Mutual Information:\\
$I(x:y)= K(x)+ K(y)- K(x,y)$. It has many uses which we cannot consider here.

	\subsubsection*{Deficiency of Randomness.}

There are ways to estimate complexity that are correct in some important cases,
but not always. One such case is when a string $x$ is generated at random. Let
us define $d(x)= |x|-K(x/|x|)$; ($d(x)> -O(1)$).

What is the probability of $d(x)>i$, for $|x|=n$? There are $2^n$ strings $x$
of length $n$. If $d(x)>i$, then $K(x/|x|)< n-i$. There are $<2^{n-i}$ programs
of such length, generating $<2^{n-i}$ strings. So, the probability of such
strings is $<2^{n-i}/2^n= 2^{-i}$ (regardless of $n$)! So even for $n=
1,000,000$, the probability of $d(x)>300$ is absolutely negligible (provided
$x$ was indeed generated by fair coin flips). We call $d(x)$ the {\bf\em
deficiency of randomness} of a string $x$ with respect to the uniform
probability distributions on all strings of that length.

If $d(x)$ is small then $x$ satisfies all other reasonable properties of random
strings. Indeed, consider a property ``$x\not\in P$'' with enumerable $S=\neg
P$ of negligible probability. Let $S_n$ be the number of strings of length $n$,
violating $P$ and $\log(S_n)=s_n $. What can be said about the complexity of
all strings in $S$? $S$ is enumerable and sparse (has only $S_n$ strings). To
generate $x$, using the algorithm enumerating $S$, one needs only the position
$i$ of $x$ in the enumeration of $S$. We know that $i\le S_n\ll2^n$ and, thus,
$|i|\le s_n\ll n$. Then the deficiency of randomness $d(x)> n-s_n$ is large.
Every $x$ which violates $P$ will, thus, also violate the ``small deficiency of
randomness'' requirement. In particular, the small deficiency of randomness
implies unpredictability of random strings: A compact algorithm with frequent
prediction would assure large $d(x)$. Sadly, the randomness can not be
detected: we saw, $K$ and its lower bounds are not computable.

 \paragraph {Rectification of Distributions.} We rarely have a source of
randomness with precisely known distribution. But there are very efficient ways
to convert ``imperfect'' random sources into perfect ones.
 Assume, we have a ``junk-random'' sequence with weird unknown distribution.
 We only know that its long enough ($m$ bits) segments have min-entropy
$>k+i$, i.e. probability $<1/2^{k+i}$, given all previous bits. (Without
such $m$ we would not know a segment needed to extract even one not
fully predictable bit.) We can fold $X$ into an $n\times m$ matrix. No
relation is required between $n,m,i,k$, but useful are small $m,i,k$ and
huge $n=o(2^k/i)$. We also need a small $m\times i$ matrix $Z$,
independent of $X$ and really uniformly random (or random Toeplitz,
i.e.\ with restriction $Z_{a+1,b+1}=Z_{a,b}$). Then the $n\times i$
product $X Z$ has uniform distribution accurate to $O(\sqrt{n i/2^k})$.
This follows from [Goldreich, Levin], which uses earlier ideas of U. and
V. Vazirani.