The Scary Sequences Project (Scarier than Blair Witch!)

Motivating Observations

The key observation is that there is an evolving body of knowledge that leads to statements that remind us of probabilistic statements yet which apply to all sequences, or at least those that satisfy certain calibration properties.

For example, the Limpel-Ziv algorithm stands ready to tell us about any sequence at all. On the other hand, Shafer-Vovk theory and Foster-Vohra theory make assumptions and draw conclusions which --- although not always overtly probabilistic --- still capture probabilistic effects. There are also connections to on-line learning, learning in games, competitive algorithms, self-orgainizing list, and perhaps too much more.

Organization and Plan

At first it seems useful to cast a wide net. This is the taxonomical step, which will probably lead to focusing on a subset of what we turn up.The next step might be to write a piece for the Monthly or the Mathematical Inteligencer that would exposit one of the manageable sub-themes. The broad hope is that this might be a theme that can be pursued to a considerable length.

Interconnected Topics on "Sequences" (or, better, Sequential Decisions)

Learning in Games, Applications of Approachability, Universal Forcasting, Regret (Internal, External)

Problem of the Experts (including Univesal Forecasting)

On Prediction of Individual Sequences by Cesa-Bianchi and Lugosi. The authors are well informed with the theory of probability inequalities. They seem to have pushed many of the "CS level" results into their final form. This is a benchmark paper.

Machine Learning (with Weight on Sequences)

Yohav Freund's Home Page and his many nice papers.

Schapire's Home Page and his many nice papers.

Universal Portfolio Theory

Competitive Algorithms/On-line Algorithms

Shafer-Vovk Theory

Universal Data Compression

Multi-armed Bandit Problems, Optimal Stopping,

Dynamic Programming, Markov Decision Processes, Stochastic Scheduling

Search Theory

Economics and Search, Hal Varian

Prophet Inequalities

Wanted--And Not Easy to Find

Classic Resources

Ergodic Theory and Topological Dynamics


Further Afield