We discuss the game of sequentially assigning probabilities to symbols in a sequence. A cumulative logarithmic (entropic) loss may be interpreted as the codelength for the sequence. We give general upper and lower bounds on the cumulative minimax regret (redundany) for two scenarios: In the random case, the data are generated independently from an unknown distribution from a given family and the player tries to minimize the expected loss for the worst distribution in this family. In the worst case over sequence scenario, NO probabilistic assumption about the generation of the data is made. The player compares her loss with the the loss of an adversary who knows the entire sequence in advance and uses always the best distribution from the family for each given sequence. In both cases it is possible two bound the cumulative regret in terms of a metric entropy for the family of distributions.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing