\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) -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.