Speaker : Vladimir Uspensky, Moscow State University
Date: Tuesday Oct 7 2003
Time: 10:30am - 11:30am
Place: ASB 9896

Title:
Four Algorithmic Faces of Randomness.

Abstract
Let us consider infinite sequences of zeros and ones.

The classical probability theory fails to distinguish between random and non-random sequences. The first attempt to do that is due to von Mises (1919) but it suffered some vagueness. The theory of algorithms contributed new ideas to the task of defining what an individual random sequence is.

In fact, a random sequence has at at least four faces. First, it is {\bf stochastic}; that means, the sequence itself as well as any of its reasonable subsequences has the property of freqency stability.Second, it is {\bf chaotic}; that means, it is disordered, i. e. the occurrences of its terms are not governed by any reasonable rule.Third, it is {\bf typical}; that means, it belongs to any reasonable majority.Fourth, it is {\unpredictable}; that means, one who gambles on it cannot win
by using any reasonable strategy.

All the four formulations use the word "reasonable". In each of four cases,the theory of algorithms allows to fill that word with some exact meaning.So four well-defined classes of sequences appear. And each of them claims to be the true class of random sequences, Some of those claims are more justified than others.

References:

1.
A. N. Kolmogorov, and V. A. Uspensky.
Algorithms and randomness
// SIAM J. Theory of Probability and Its Applications, vol. 32 (1987),
pp. 389--412.

2.
V. A. Uspensky, A. L. Semenov, and A. Kh. Shen.
Can an individual sequence of zeros and ones be random?
// Russian Mathematical Survey, vol. 45 (1990), no. 1, pp. 121--189.

3.
V. Uspensky, and A. Semenov. Algorithms: Main Ideas and Applications.
--- Kluwer, 1991. --- 269 pp.

4.
An. A. Muchnik, A. L. Semenov, V. A. Uspensky.
Mathematical metaphysics of randomness
// Theoretical Computer Science, vol. 207 (1998), pp. 263--317.