Evènement pour le groupe Séminaire Méthodes Formelles
|Date|| 2019-04-09 11:00-12:00|
|Titre||Selection, Divergence, and Dichotomy |
|Résumé||The Schnorr-Stimm dichotomy theorem concerns finite-state 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 finite-state gambler loses money at an exponential rate betting on S. 2. If S is not normal, then there is a finite-state gambler that wins money at an exponential rate betting on S.
In this paper we use the Kullback-Leibler 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.
|Orateur||Donald Stull |
|Url||Université de Lorraine, LORIA |
Aucun document lié à cet événement.RetourRetour à l'index