Nicolas Sendrier Programme Informatique – Th´ ematique S´ ecurit´ e Introductio

Nicolas Sendrier Programme Informatique – Th´ ematique S´ ecurit´ e Introduction la th´ eorie de l’information Cours n◦4 Les s´ equences typiques et l’AEP Processus stochastiques Une source produit une suite de lettres dans l’alphabet X. Pour d´ ecrire cette suite de lettres nous utiliserons une suite de va- riables al´ eatoires X1, X2, . . . ` a valeurs dans X. Ces variables ne sont pas n´ ecessairement ind´ ependantes. On parlera de processus stochas- tique pour d´ ecrire cette suite de variable al´ eatoires. cours n◦4: Les s´ equences typiques et l’AEP 1 Entropie par lettre D´ efinition Un processus stochastique est stationnaire si son com- portement ne varie pas lorsque l’on d´ ecale l’observation dans le temps. Pour tous entiers positifs n et j, et tout (x1, . . . , xn) ∈X n pX1...Xn(x1, . . . , xn) = pX1+j...Xn+j(x1, . . . , xn) Th´ eor` eme Pour tout processus stochastique stationnaire, les li- mites ci-dessous existent et sont ´ egales H(X) = lim n→∞ 1 nH(X1, . . . , Xn) = lim n→∞H(Xn | X1, . . . , Xn−1). La quantit´ e H(X) est appel´ ee entropie par lettre. cours n◦4: Les s´ equences typiques et l’AEP 2 Processus markovien invariant dans le temps D´ efinition Un processus stochastique est dit markovien si pour tout entier positif n et tout (x1, . . . , xn) ∈X n Pr[Xn = xn | X1 = x1, . . . , Xn−1 = Xn−1] = Pr[Xn = xn | Xn−1 = xn−1] Le processus est dit invariant dans le temps si ces probabilit´ es ne d´ ependent pas de n. Nous noterons p(x2 | x1) = Pr[Xn = x2 | Xn−1 = x1]. Th´ eor` eme L’entropie par lettre d’un processus markovien invariant dans le temps (irr´ eductible) est ´ egal ` a H(X) = H(X2|X1) = X x1,x2 −λ(x1)p(x1 | x2) log2 p(x1 | x2) o` u λ(x), x ∈X est la distribution stationnaire. cours n◦4: Les s´ equences typiques et l’AEP 3 AEP D´ efinitions Soit une source (un processus stochastique) constitu´ ee de la suite de variables al´ eatoires X1, X2, . . . , Xn, . . . ` a valeur dans un alphabet X. On suppose que l’entropie par lettre de cette source est d´ efinie H = H(X) = lim n→∞ 1 n log2 H(X1, . . . , Xn) D´ efinition Ensemble de s´ equences typiques (de longueur n) A(n) ε = ( (x1, . . . , xn) ∈X n, 1 n log2 1 p(x1, . . . , xn) −H ≤ε ) D´ efinition (Asymptotic Equipartition Property) Un processus stochastique (une source) v´ erifie l’AEP si : ∀ε > 0, lim n→∞Pr  A(n) ε  = 1. cours n◦4: Les s´ equences typiques et l’AEP 4 Propri´ et´ es des s´ equences typiques Proposition Pour toute source v´ erifiant l’AEP (i) 1 n log2 1 p(x1, . . . , xn) − → n→∞H presque sˆ urement (ii) Pr  A(n) ε  2n(H−ε) ≤|A(n) ε | ≤2n(H+ε) Autrement dit : Il y a 2nH s´ equences typiques, ces s´ equences sont ´ equiprobables de probabilit´ e 2−nH. cours n◦4: Les s´ equences typiques et l’AEP 5 Th´ eor` eme de Shannon D´ efinition Soit ϕ un codage de X, sa longueur moyenne par lettre est d´ efinie par L(ϕ) = lim n→∞ 1 n X x1,...,xn p(x1, . . . , xn)|ϕ(x1, . . . , xn)|, lorsque cette limite existe. Th´ eor` eme (Shannon) Soit une source discr` ete d’alphabet X et d’en- tropie par lettre H qui v´ erifie l’AEP. 1. Tout codage r´ egulier ϕ de X v´ erifie L(ϕ) ≥H. 2. Il existe un codage r´ egulier ϕ de X tel que L(ϕ) ≤H + ε, ∀ε > 0. cours n◦4: Les s´ equences typiques et l’AEP 6 AEP en pratique Proposition Une source sans m´ emoire v´ erifie l’AEP. Proposition Une source markovienne irr´ eductible v´ erifie l’AEP. Proposition Une source stationnaire ergodique v´ erifie l’AEP. cours n◦4: Les s´ equences typiques et l’AEP 7 uploads/Industriel/ statitionnaire-ergodique.pdf

Tags
Industrielequences typiques l’aep processus cours
Documents similaires
  • 28
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager