
Evènement pour le groupe Séminaire Méthodes Formelles
Date  20190409 11:0012:00 
Titre  Selection, Divergence, and Dichotomy 
Résumé  The SchnorrStimm dichotomy theorem concerns finitestate gamblers that bet on infinite sequences of symbols taken from a finite alphabet. The theorem asserts that, for each such sequence S, the following two things are true. 1. If S is normal in the sense of Borel (meaning that any two strings of equal length appear with equal asymptotic frequency in S), then every finitestate gambler loses money at an exponential rate betting on S. 2. If S is not normal, then there is a finitestate gambler that wins money at an exponential rate betting on S.
In this paper we use the KullbackLeibler divergence (also known as the relative entropy) to generalize the dichotomy theorem to arbitrary probability measures on the alphabet and to quantify the exponential rates of winning and losing on the two sides of the dichotomy.

Lieu  178 
Orateur  Donald Stull 
Email  http://web.cs.iastate.edu/~dstull/ 
Url  Université de Lorraine, LORIA 
Aucun document lié à cet événement. RetourRetour à l'index
 