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