Evènement pour le groupe Séminaire Méthodes Formelles

Date 2019-04-09  11:00-12:00
TitreSelection, 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.  
OrateurDonald Stull 
UrlUniversité de Lorraine, LORIA 

Aucun document lié à cet événement.

Retour à l'index