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,
- Tom Furguson's home page has many relevant "selection" papers as well as an electronic book on optimal stopping.
- There is an extensive literature on Bandit problems, where in the simplest case one make draws from iid device A or iid device B. The goal is to maximize discounted total winnning from sequential play.
- Martin Zinkevich's method for on-line convex programs gives a new approach to bandit problems and the famous Gittins index.
- Other Gittens whizzes: Richard Weber, Bob Vanderbei, Avi Mandelbaum, Nick Frangos, Peter Whittle, and Robert Dalang.
- Berry, Donald and Bert Fristedt (1985). Bandit Problems: Sequential Allocation of Experiments. London: Chapman and Hall. This is unfortunately out of print, but Don Berry kindly provided me a hard copy which I can share if you are interested.
- Who was Gittens? Was the famous paper Gittens and James? Why is James not mentioned these days?
Dynamic Programming, Markov Decision Processes, Stochastic Scheduling
Search Theory
Economics and Search, Hal Varian
Prophet Inequalities
Wanted--And Not Easy to Find
- Robbins and Lai seem to have written the definative bandit paper.
Classic Resources
- David Blackwell does not have an active web page, so I have begun to "archive" some of Blackwell's work on "sequence theory."
- Hannan (1957). This paper disappeared for a while from the collective consciousness, but now it is widely cited --- even though it is still almost impossible to find. Well, thanks to Rick Vohra, here it is in all of its untypset glory. Rumor has it that Hannan once said something like, "I am pleased to hear that people are now refering to my paper, but why do they only mention the results from one section?" My guess is that the idea of that section got passed around, but very few people took the time to find the full paper. Now every one has full and easy access. Blessings on the Web.
Ergodic Theory and Topological Dynamics
Bibiographies
Further Afield