Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Statitionnaire ergodique Nicolas Sendrier Programme Informatique ?? Th ?ematique S ?ecurit ?e Introduction la th ?eorie de l ? information Cours n Les s ?equences typiques et l ? AEP CProcessus stochastiques Une source produit une suite de lettres dans l

Nicolas Sendrier Programme Informatique ?? Th ?ematique S ?ecurit ?e Introduction la th ?eorie de l ? information Cours n Les s ?equences typiques et l ? AEP CProcessus stochastiques Une source produit une suite de lettres dans l ? alphabet X Pour d ?ecrire cette suite de lettres nous utiliserons une suite de variables al ?eatoires X X a valeurs dans X Ces variables ne sont pas n ?ecessairement ind ?ependantes On parlera de processus stochastique pour d ?ecrire cette suite de variable al ?eatoires cours n Les s ?equences typiques et l ? AEP CEntropie par lettre D ?e ?nition Un processus stochastique est stationnaire si son comportement ne varie pas lorsque l ? on d ?ecale l ? observation dans le temps Pour tous entiers positifs n et j et tout x xn ?? X n pX Xn x xn pX j Xn j x xn Th ?eor eme Pour tout processus stochastique stationnaire les limites ci- dessous existent et sont ?egales H X nl ?im ? nH X Xn nl ?im ? H Xn X Xn ?? La quantit ?e H X est appel ?ee entropie par lettre cours n Les s ?equences typiques et l ? AEP CProcessus markovien invariant dans le temps D ?e ?nition Un processus stochastique est dit markovien si pour tout entier positif n et tout x xn ?? X n Pr Xn xn X x Xn ?? Xn ?? Pr Xn xn Xn ?? xn ?? Le processus est dit invariant dans le temps si ces probabilit ?es ne d ?ependent pas de n Nous noterons p x x Pr Xn x Xn ?? x Th ?eoreme L ? entropie par lettre d ? un processus markovien invariant dans le temps irr ?eductible est ?egala H X H X X ?? ? x p x x log p x x x x ou ? x x ?? X est la distribution stationnaire cours n Les s ?equences typiques et l ? AEP CAEP D ?e ?nitions Soit une source un processus stochastique constitu ?ee de la suite de variables al ?eatoires X X Xn a valeur dans un alphabet X On suppose que l ? entropie par lettre de cette source est d ?e ?nie H H X nl ?im ? n log H X Xn D ?e ?nition Ensemble de s ?equences typiques de longueur n A n x xn ?? X n n log p x xn ?? H ? D ?e ?nition Asymptotic Equipartition Property Un processus stochastique une source v ?eri ?e l ? AEP si ?? nl ?im ? Pr A n cours n Les s ?equences typiques et l ? AEP CPropri ?et ?es des s ?equences typiques Proposition Pour toute source v ?eri ?ant l ? AEP i n log p x xn n ?? ? ? ? H presque su rement ii Pr A n n H ?? ? A n ? n H Autrement dit Il y a nH s ?equences