@inproceedings{e7ea2ec223e04fc4954c1f4bf762cdf8,

title = "Strong entropy concentration, game theory and algorithmic randomness",

abstract = "We give a characterization of Maximum Entropy/Minimum Relative Entropy inference by providing two {\textquoteleft}strong entropy concentration{\textquoteright} theorems. These theorems unify and generalize Jaynes{\textquoteright} {\textquoteleft}concentration phenomenon{\textquoteright} and Van Campenhout and Cover{\textquoteright}s {\textquoteleft}conditional limit theorem{\textquoteright}. The theorems characterize exactly in what sense a {\textquoteleft}prior{\textquoteright} distribution Q conditioned on a given constraint and the distribution P minimizing D(P//Q) over all P satisfyingthe constraint are {\textquoteleft}close{\textquoteright} to each other. We show how our theorems are related to {\textquoteleft}universal models{\textquoteright} for exponential families, thereby establishinga link with Rissanen{\textquoteright}s MDL/stochastic complexity. We then apply our theorems to establish the relationship (A) between entropy concentration and a game-theoretic characterization of Maximum Entropy Inference due to Tops{\o}e and others; (B) between maximum entropy distributions and sequences that are random (in the sense of Martin-L{\"o}f/Kolmogorov) with respect to the given constraint. These two applications have strong implications for the use of Maximum Entropy distributions in sequential prediction tasks, both for the logarithmic loss and for general loss functions. We identify circumstances under which Maximum Entropy predictions are almost optimal.",

author = "P.D. Gr{\"u}nwald",

year = "2001",

doi = "10.1007/3-540-44581-1_21",

language = "English",

isbn = "3-540-42343-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "320--336",

editor = "D.P. Helmbold and B. Williamson",

booktitle = "Computational learning theory : proceedings 14th annual conference on computational learning theory, COLT 2001, and 5th European conference on computational learning theory, EuroCOLT 2001, Amsterdam, The Netherlands, july 16-19, 2001",

address = "Germany",

}