Probabilités et Statistique en Cryptographie
Probabilités et Statistique en Cryptographie
Probabilités et statistique
pour la théorie de l’information
Notes de cours
Dimitri Petritis
2012
c – 2019 D. Petritis
Table des matières
1 Aléa et information 1
1.1 Rôle de l’aléa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Probabilités et intuition aléatoire . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Esquisse du problème d’estimation statistique . . . . . . . . . . . . . . . 3
1.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
iii
TABLE DES MATIÈRES TABLE DES MATIÈRES
6 Notions de statistique 63
6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 Estimation paramétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2.1 Estimation ponctuelle . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.2.2 Estimation d’intervalles de confiance . . . . . . . . . . . . . . . . 66
6.2.3 Tests d’hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3 Estimation non paramétrique . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
II Théorie de l’information 71
7 Quantification de l’information 73
7.1 Postulats d’une quantité d’incertitude, entropie . . . . . . . . . . . . . . . 73
7.2 Trois interprétations de l’entropie . . . . . . . . . . . . . . . . . . . . . . . 78
7.2.1 H est une espérance (qui nous fait vieillir !) . . . . . . . . . . . . . 78
7.2.2 H est le nombre moyen de questions nécessaires pour déterminer
la valeur que prend une variable aléatoire . . . . . . . . . . . . . . 78
7.2.3 H est le rapport des logarithmes du volume des configurations
typiques sur celui de toutes les configurations . . . . . . . . . . . 80
7.3 Propriétés de la fonction entropie, entropie relative . . . . . . . . . . . . 84
7.4 Entropie des évolutions markoviennes . . . . . . . . . . . . . . . . . . . . 85
7.5 Couples de variables aléatoires . . . . . . . . . . . . . . . . . . . . . . . . 86
7.5.1 Entropie conjointe . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.5.2 Entropie conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . 87
7.5.3 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.6 Registres de stockage de l’information . . . . . . . . . . . . . . . . . . . . 89
7.6.1 Propriétés des registres . . . . . . . . . . . . . . . . . . . . . . . . 89
7.6.2 Deuxième loi de la thermodynamique, principe de Landauer . . 91
7.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
/Users/dp/a/ens/[Link] iv
2019-10-18 • 18:08:44.
TABLE DES MATIÈRES TABLE DES MATIÈRES
10 Chiffrement 133
10.1 Sécurité des communications . . . . . . . . . . . . . . . . . . . . . . . . . 133
10.1.1 Le chiffrement comme code . . . . . . . . . . . . . . . . . . . . . . 133
10.1.2 Les niveaux de sécurité . . . . . . . . . . . . . . . . . . . . . . . . 134
10.2 Code de Vernam (one-time pad) . . . . . . . . . . . . . . . . . . . . . . . . 136
10.3 Authentification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
10.3.1 Illustration du problème et notation . . . . . . . . . . . . . . . . . 139
10.3.2 Minoration de la probabilité de fraude . . . . . . . . . . . . . . . . 140
10.4 Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
10.5 Qu’est-ce la cryptographie post-quantique ? . . . . . . . . . . . . . . . . . 141
10.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Références 146
Index 150
/Users/dp/a/ens/[Link] v
2019-10-18 • 18:08:44.
TABLE DES MATIÈRES TABLE DES MATIÈRES
/Users/dp/a/ens/[Link] vi
2019-10-18 • 18:08:44.
Aléa et information
1
Des nos jours, le codage, le stockage, la transmission, le traitement, l’extraction et le
chiffrement de l’information se font de manière algorithmique sur des messages numé-
riques que nous pouvons toujours considérer comme des suites de bits. On peut donc
légitimement s’interroger qu’ont à faire les probabilités et la statistique — branches
mathématiques étudiant le caractère aléatoire des phénomènes — dans cet univers al-
gorithmique.
1
1.1. Rôle de l’aléa Aléa et information
que le résultat nous soit révélé, l’incertitude est nulle. L’information contenue
dans le bit correspondant au résultat du lancer d’une pièce honnête est égale à
la réduction de l’incertitude après révélation du résultat. Nous verrons au cha-
pitre 7 que pour une pièce arbitraire, donnant face avec probabilité p ∈ [0, 1],
l’information contenue dans le bit codant le résultat du lancer est la quantité
P(bit transmis = 1|bit émis = 0) = P(bit transmis = 0|bit émis = 1) = p ∈ [0, 1],
/Users/dp/a/ens/[Link] 2
2019-08-09 • 14:52:34.
Aléa et information 1.2. Probabilités et intuition aléatoire
/Users/dp/a/ens/[Link] 3
2019-08-09 • 14:52:34.
1.4. Exercices Aléa et information
1.4 Exercices
Le premier exercice est purement combinatoire ; nous introduisons les 4 types de
dénombrement. Pour les exercices sur les probabilités élémentaires de ce chapitre, nous
laissons de côté les questions de définition de la notion de probabilité en nous limitant
à la définition empirique (fréquentielle) des probabilités exposée plus haut. Dans ce
contexte, les probabilités de ces exercices se calculent comme des rapports de cardi-
naux.
cardΩ2 = ( MM!
−n)!
.
— n tirages indiscernables à choisir parmi M possibilités sans remise (0 < n ≤
M) :
Événements et ensembles
2. Sous quelles conditions les événements A et B satisfont l’égalité A = A ∪ B ?
L’égalité A = A ∩ B ?
3. Soit ( Ai )i∈ I une collection d’ensembles. Déterminer (∪i∈ I Ai )c et (∩i∈ I Ai )c .
4. La figure suivante décrit un circuit électrique entre les points 1 et 2 comportant
les fusibles a, b1 , b2 et b3 qui peuvent tomber en panne.
/Users/dp/a/ens/[Link] 4
2019-09-11 • 21:15:57.
Aléa et information 1.4. Exercices
b1
1 a b2 2
b3
Probabilités élémentaires
7. Un ouvrage de 4 volumes est placé dans un ordre aléatoire sur le rayonnage
d’une bibliothèque. Quelle est la probabilité que les 4 volumes soient placés
dans l’ordre (ascendant ou descendant) ? Rép. : 1/12.
8. Toutes les faces d’un cube en bois sont peintes. Ensuite le cube est découpé (se-
lon des plans parallèles à ses faces) en 1000 cubes identiques. Un petit cube
est choisi au hasard ; quelle est la probabilité qu’il comporte exactement 2 faces
peintes ? Rép. : 0,096.
9. Dix livres sont placés dans un ordre aléatoire sur un rayonnage. Quelle est la
probabilité que trois livres spécifiques se retrouvent côte-à-côte ? Rép. : 1/15.
10. Un sac contient 5 bâtonnets de longueurs 1, 3, 5, 7 et 9. On en extrait 3. Quelle est
la probabilité que l’on puisse construire un triangle ayant ces bâtonnets comme
côtés ? Rappel : La longueur d’un côté d’un triangle ne peut pas excéder la somme des
longueurs des autres côtés.
11. Supposons qu’un entier entre 1 et 1000 est choisi au hasard. Quelle est la pro-
babilité que les 2 derniers digits décimaux de son cube soient 1 ? Suggestion : Il
n’est pas nécessaire de consulter une table des cubes des tous les entiers entre 1 et 1000.
Rép. : 0,01.
12. Quelle est la probabilité qu’au moins deux étudiants suivant un cours auquel
N étudiants sont inscrits (N ≥ 2) aient leur anniversaire le même jour ? On
néglige les années bissextiles et on suppose que tous les jours de l’année sont
équiprobables en tant que jour de naissance.
13. Une tombola comporte M tickets dont n (avec M ≥ 2n) sont gagnants. Une
personne achète n tickets. Quelle est la probabilité pour qu’elle gagne au moins
un lot ?
/Users/dp/a/ens/[Link] 5
2019-09-11 • 21:15:57.
1.4. Exercices Aléa et information
14. On gagne (au premier rang) une loterie si l’on coche 6 bons numéros parmi les
49 que comporte une grille. Quelle est la probabilité de gagner cette loterie au
premier rang ?
/Users/dp/a/ens/[Link] 6
2019-08-09 • 14:52:34.
Première partie
7
Théorie élémentaire des probabilités
2
Nous présentons la théorie telle qu’elle a été formulée par Kolmogorov [33] et nous
nous inspirons librement des exposés pédagogiques [24, 51, 55, 59], en particulier pour
le choix de certains exemples. Les livres [2, 6, 43] peuvent utilement être consultés mais
sont mathématiquement plus exigeants.
La formulation de Kolmogorov est une construction mathématique abstraite. Ce-
pendant, déjà dans l’œuvre originale [33] transparaît une forte intuition expérimen-
tale ; pour comprendre les notions de base de la théorie, il est très utile de nous servir
des modèles venant d’autres domaines de mathématiques ou de la physique.
La présentation naturelle de la théorie requiert la théorie de la mesure. Dans la suite
nous essaierons de donner une présentation élémentaire i.e. qui ne fait pas appel à la
théorie de la mesure.
Événements
Les parties de Ω — plus précisément certaines parties de Ω — sont appelés évé-
nements ; Ω lui-même est toujours un événement (l’événement certain) ainsi que ∅
(l’événement impossible). Intuitivement, un événement est un ensemble d’épreuves
qui vérifient une propriété. Si la famille A ⊆ P (Ω) est une famille d’événements, il est
naturel de demander qu’elle constitue une algèbre.
9
2.1. Espace de probabilité Théorie élémentaire des probabilités
Exemple 2.1.3 (Pile ou face). L’espace des épreuves pour le lancer d’une pièce est
Ω = {pile, face} ≡ {0, 1}. La famille A = P (Ω) est une algèbre qui correspond à tous
les événements possibles.
Exemple 2.1.4 (Pile ou face répété n fois). L’espace des épreuves pour cette expérience
est Ω = {ω = (ω1 , . . . , ωn ) : ωi ∈ {0, 1}, i = 1, . . . , n} ≡ {0, 1}n . On remarque que
cardΩ = 2n . La famille A = P (Ω) est une algèbre qui correspond à tous les événements
n
possibles ; elle a cardA = 22 .
Exemple 2.1.5 (Pile ou face répété indéfiniment). Parfois on s’intéresse à des suites
infinies d’expériences (par exemple une suite de bits indéfiniment longue). L’espace
des épreuves pour cette expérience est Ω = {ω = (ω1 , ω2 , . . .) : ωi ∈ {0, 1}, i ∈ N} ≡
{0, 1}N . On remarque que cardΩ = 2ℵ0 = c (donc Ω ∼= R).
Remarque 2.1.6. Le dernier exemple établit que si nous voulons considérer des limites
de suites — considérer la suite donc dans son intégralité — nous sommes obligés de
sortir du cadre discret.
Lorsque l’espace Ω est dénombrable infini (ou a fortiori non dénombrable), il est na-
turel de demander la stabilité de la famille des événements aux réunions (intersections)
dénombrables. Ceci nous amène à la
Définition 2.1.7. Une famille F de parties de Ω est dite une tribu (ou σ-algèbre) si elle
est une algèbre et vérifie la propriété de stabilité aux intersections dénombrables :
[∀n ∈ N, An ∈ F ] ⇒ [∪n∈N An ∈ F ].
Définition 2.1.9. Soit Ω un espace des épreuves et F une tribu sur Ω. Le couple (Ω, F )
est appelé espace des événements (ou espace mesurable dans la terminologie de la
théorie de la mesure).
/Users/dp/a/ens/[Link] 10
2019-09-19 • 10:40:09.
Théorie élémentaire des probabilités 2.1. Espace de probabilité
2.1.2 Probabilisation
Définition 2.1.10. Soit (Ω, F ) un espace des événements. Supposons qu’il existe une
application P : F → [0, 1] vérifiant
1. P(Ω) = 1 (normalisation de la masse totale) et
2. [∀n ∈ N, An ∈ F et Am ∩ Fn = ∅, m 6= n] ⇒ [P(∪n∈N An ) = ∑n∈N P( An )]
(additivité dénombrable disjointe dite aussi σ-additivité disjointe).
Alors P est appelée (mesure de) probabilité sur (Ω, F ) et le triplet (Ω, F , P) est alors
appelé espace probabilisé.
Proposition 2.1.11. Supposons que Ω est dénombrable (fini ou infini) et qu’il existe une
application ρ : Ω → [0, 1] telle que ∑ω ∈Ω ρ(ω ) = 1. Alors ρ définit une mesure de probabilité
P sur (Ω, F ), où F = P (Ω), par
Reciproquement, si P est une probabilité sur (Ω, P (Ω)) et Ω est dénombrable, alors il existe
ρ : Ω → [0, 1] telle que ∑ω ∈Ω ρ(ω ) = 1 permettant de définir P comme ci-dessus. (En fait
ρ(ω ) = P({ω }) pour tout ω ∈ Ω).
L’exercice 21 montre que l’ensemble fini Ω = {0, 1}n peut être probabilisé par un
vecteur de probabilité vérifiant en outre la propriété d’invariance à l’application Tk
« renversement du ke bit » définie par
Cette construction ne peut pas s’étendre au cas Ω = {0, 1}N comme le montre le
Théorème 2.1.13 (Vitali 1905). Soit Ω = {0, 1}N l’ensemble des suites infinies de bits. Il
n’existe pas d’application P : P (Ω) → [0, 1] vérifiant sumultanément
— (normalisation) : P(Ω) = 1,
/Users/dp/a/ens/[Link] 11
2019-09-19 • 10:40:09.
2.1. Espace de probabilité Théorie élémentaire des probabilités
Dans l’exercice 18 nous introduisons la notion de tribu engendrée par une famille
arbitraire (non-vide) A de parties de P (Ω) comme étant la plus petite tribu qui contient
A — notée σ(A).
d
R d = { ∏ [ a i , bi ] : a i < bi , a i , bi ∈ Q } ,
i =1
le système de pavés rectangulaires avec des arêtes parallèles aux axes et sommets avec
des coordonnées rationnelles. La tribu σ (Rd ) engendrée par cette famille est appelée
tribu borélienne sur Rd et notée Bd := B(Rd ). (Lorsque d = 1, nous abrégeons la
notation en B ). Les événements de Bd sont appelés boréliens.
Remarque 2.1.16. La tribu Bd est beaucoup plus grosse que l’on pouvait supposer à
première vue. En particulier elle contient les classes
— des ouverts ;
— des fermés ;
— Gδ (intersections dénombrables d’ouverts) ;
— Fσ (réunion dénombrables de fermés) ;
— Gδσ (réunions dénombrables d’éléments de Gδ ) ;
— Fσδ (réunions dénombrables d’éléments de Fσ )
— ...
Pour les besoins de ce cours il est suffisant de connaître que toutes les parties de Rd
que nous rencontrons en pratique sont boréliennes. Montrer l’existence de parties non-
boréliennes n’est pas tâche aisée, il faut recourir à l’axiome du choix (cf. [6, pp. 24–28]
par exemple).
Définition 2.1.17 (Tribu produit). Soient (Ωn , Fn )n∈N une suite d’espaces mesurables,
Ω = ×n∈N Ωn et R = ×n∈N Fn . La tribu F = σ(R) sur Ω, engendrée par le produit
cartésien R de tribus est appelée tribu produit et notée F = ⊗n∈N Fn .
Théorème 2.1.18 (Propriétés de P). Toute mesure de probabilité P sur un espace d’événe-
ments (Ω, F ) vérifie les propriétés suivantes pour des événements arbitraires A, B, A1 , A2 , . . . ∈
F:
1. P(∅) = 0.
/Users/dp/a/ens/[Link] 12
2019-09-19 • 10:40:09.
Théorie élémentaire des probabilités 2.1. Espace de probabilité
P( ∅ ) = P( ∅ ∪ ∅ ∪ . . . ) = ∑ P( ∅ ).
n ∈N
P( A ∪ B ) = P( A ∪ B ∪ ∅ ∪ ∅ ∪ . . . ) = P( A ) + P( B ) + 0 + 0 + . . . .
P( A ∪ B) + P( A ∩ B) = P( A \ B) + P( B \ A) + 2P( A ∩ B) = P( A) + P( B).
P( A) = P(tn≥1 ( An \ An−1 )) = ∑ P ( A n \ A n −1 )
n ≥1
N
= lim
N →∞
∑ P( An \ An−1 ) = Nlim
→∞
P( A N ).
n =1
Pour montrer que deux probabilités P et P0 sur (Ω, F ) coïncident, il faut montrer
qu’elles coïncident sur tous les éléments de la tribu F . Or, nous avons vu que les tribus
sont des objets compliqués, difficilement maniables. Le théorème suivant nous donne
un moyen très efficace de montrer plusieurs propriétés de probabilités sans avoir re-
cours explicitement à la tribu sous-jacente.
/Users/dp/a/ens/[Link] 13
2019-09-19 • 10:40:09.
2.1. Espace de probabilité Théorie élémentaire des probabilités
/Users/dp/a/ens/[Link] 14
2019-09-19 • 10:40:09.
Théorie élémentaire des probabilités 2.2. Variables aléatoires
ω2
1
√ exp − 2
2πσ 2σ
34%34%
0.1% 2% 14% 14% 2% 0.1%
ω
−3σ −2σ −σ σ 2σ 3σ
Figure 2.1 – La masse de la loi gaussienne s’étend sur tout l’axe R. Cependant, elle reste essentiel-
lement concentrée sur l’intervalle [−3σ, 3σ].
Il n’est pas vrai en général qu’un événement négligeable est vide ; ni qu’un ensemble
presque sûr coïncide avec l’univers tout entier comme le contre-exemple suivant nous
enseigne.
Contre-exemple 2.1.24. Soient (Ω, F , P) = ([0, 1], B([0, 1]), λ), N = [0, 1] ∩ Q et S =
[0, 1] \ Q. Alors P( N ) = 0 et P(S) = 1 − P( N ) = 1. Pourtant, N n’est pas vide (il est
même dense dans [0, 1]) et S = [0, 1] \ Q (il manque à S une infinité de points pour
qu’il devienne égal à Ω).
/Users/dp/a/ens/[Link] 15
2019-09-19 • 10:40:09.
2.2. Variables aléatoires Théorie élémentaire des probabilités
/Users/dp/a/ens/[Link] 16
2019-09-19 • 10:40:09.
Théorie élémentaire des probabilités 2.3. Exercices
v
Figure 2.2 – L’espace de phases (v, M ) (sous quelques conditions simplificatrices), où v désigne la
vitesse verticale et M le moment angulaire, est stratifié en régions rouges et bleues selon les résultats
possibles (pile ou face). Seulement les premières strates sont présentées ; cependant, la stratification
couvre tout le quadrant.
où PX ({ xi }) = ρ X ( xi ) = ∆FX ( xi ) := FX ( xi ) − FX ( xi −).
2.3 Exercices
Algèbres, tribus, espaces probabilisés
15. Soit A une algèbre sur Ω (fini) et soient A, B et C trois événements quelconques
de A. Exprimer les événements suivants. Parmi A, B, C
(a) A seul se produit,
(b) A et B se produisent et C ne se produit pas,
/Users/dp/a/ens/[Link] 17
2019-09-22 • 21:40:45.
2.3. Exercices Théorie élémentaire des probabilités
0.8
0.6
0.4
0.2
0
−6 −4 −2 0 2 4 6
Figure 2.3 – Fonction de répartition de la loi sur X = {0, 1, 2} définie par le vecteur de probabilité
p := (0.2, 0.5, 0.3).
1. Attention : La réunion ∪i∈ I Fi n’est pas, en général, une tribu. Même dans le cas où (Fi )i∈N est
une filtration dénombrable (i.e. une suite des tribus strictement emboîtées Fi ⊂ Fi+1 , pour i ∈ N), la
réunion ∪i∈N Fi n’est jamais une tribu ; cf. [10]. La réunion engendre cependant une tribu par le procédé
décrit dans cet exercice, notée ∨i∈N Fi .
/Users/dp/a/ens/[Link] 18
2019-09-22 • 21:40:45.
Théorie élémentaire des probabilités 2.3. Exercices
Ω 3 ω = (ω1 , . . . , ωk , . . . , ωn ) 7→ Tk ω := (ω1 , . . . , 1 − ωk , . . . , ωn ) ∈ Ω.
/Users/dp/a/ens/[Link] 19
2019-09-22 • 21:40:45.
2.3. Exercices Théorie élémentaire des probabilités
24. Montrer que si F est une fonction de répartition, elle a au plus une infinité dé-
nombrable de discontinuités. Suggestion : étant donné que F est continue à droite,
un point x est une discontinuité s’il est une discontinuité gauche, i.e. si DF ( x ) =
F ( x ) − F ( x −) > 0. Écrire alors { x ∈ R : DF ( x ) > 0} comme une réunion dénom-
brable de parties de R et . . . réfléchir un peu sur le cardinal de chacun de ces ensembles.
25. Soient (Ω, F , P) = ([0, 1], B([0, 1]), λ) et X : Ω → R une application continue.
Suppposons que l’espace image R est muni de sa tribu borélienne. Montrer que
X est une variable aléatoire.
26. Soit F : R → [0, 1] une fonction croissante, continue à droite, vérifiant limx→−∞ F ( x ) =
0 et limx→+∞ F ( x ) = 1. Montrer qu’il existe un espace de probabilité (Ω, F , P)
et une variable aléatoire réelle X sur cet espace ayant F comme fonction de ré-
partition.
27. Soit X une variable aléatoire réelle dont la loi admet une densité ρ X (par rap-
port à la mesure de Lebesgue) sur R. Montrer que sa fonction de répartition FX
s’exprime comme l’intégrale
Z
FX ( x ) = ρ X (t)λ(dt).
]−∞,x ]
Noter que si FX a une densité comme ci-dessus, alors FX est continue et diffé-
rentiable avec FX0 = ρ X .
/Users/dp/a/ens/[Link] 20
2019-09-19 • 10:40:09.
Probabilité conditionnelle et
3
indépendance
3.1 Conditionnement
Revenons pour l’instant à l’interprétation fréquentielle de la probabilité, présentée
dans le chapitre 1, et considérons l’expérience suivante. On jette un dé N fois et on
compte deux grandeurs : le nombre de fois NB que l’événement B = « la face supé-
rieure montre 6 » se réalise et le nombre NA de réalisations de l’événement A = « la
face supérieure porte un numéro pair ». Lorsque N est très grand, nous estimons la
probabilité d’apparition de la face 6 par P( B) ' NB /N ' 1/6 et la probabilité d’appa-
rition d’une face paire par P( A) ' NA /N ' 1/2. Mais supposons que quelqu’un nous
informe que lors de cette expérience une face paire est apparue. En quoi cette informa-
tion va modifier notre estimation de la probabilité d’obtenir 6 ? Un instant de réflexion,
nous indique que la probabilité d’obtenir 6 sachant que le dé montre une face paire est
P A ( B) ' NB /NA ' 1/3 ; la connaissance que l’événement A s’est réalisé a transformé
la probabilité de P en P A qui doit logiquement vérifier les propriétés suivantes :
1. P A ( A) = 1, i.e. l’événement A, sachant que A s’est réalisé, est maintenant cer-
tain,
2. il existe une constante c A > 0 telle que pour tout événement D ⊆ A on ait
P A ( D ) = c A P( D ), i.e. les événements sont répondérés.
Proposition 3.1.1. Soient (Ω, F , P) un espace de probabilité et A ∈ F avec P( A) > 0. Il
existe une unique probabilité P A sur (Ω, F ) vérifiant les deux propriétés ci-dessus, définie par
la formule
P( A ∩ B )
P A ( B) := , ∀B ∈ F .
P( A )
Démonstration. Supposons que P A vérifie les deux propriétés ci-dessus. Pour B ∈ F
arbitraire,
P A ( B ) = P A ( B ∩ A ) + P A ( B \ A ) = P A ( B ∩ A ) + 0 = c A P( B ∩ A ).
21
3.1. Conditionnement Probabilité conditionnelle et indépendance
P( A ∩ B )
P A ( B ) : = P( B | A ) : = .
P( A )
Théorème 3.1.4. Soient (Ω, F , P) un espace de probabilité et ( Bn )n∈ I une partition au plus
dénombrable de Ω) avec Bn ∈ F pour tout n ∈ I. Alors, pour tout A ∈ F on a :
P( A| Bk )P( Bk )
P( Bk | A) = (formule de Bayes).
∑n∈ I P( A| Bn )P( Bn )
Exercice 1. (Important ; résolvez-le avant de continuer). Une urne contient deux pièces
de monnaie. Une honnête et une biaisée qui donne face avec probabilité 1/3. On en
extrait une, on la lance et on obtient face. Quelle est la probabilité qu’il s’agissait de la
pièce honnête ?
P ( A 1 ∩ · · · ∩ A n ) = P ( A 1 )P ( A 2 | A 1 ) · · · P ( A n | A 1 ∩ · · · ∩ A n −1 ).
/Users/dp/a/ens/[Link] 22
2019-09-19 • 11:36:00.
Probabilité conditionnelle et indépendance 3.1. Conditionnement
Nous serons amenés à considérer des suites infinies de variables aléatoires, par
exemple pour étudier les suites de bits générées par une source. Nous avons donc
besoin d’un résultat analogue au théorème 3.1.6 mais pour N = ∞. La difficulté essen-
tielle provient du fait que, même pour une suite (An )n∈N d’alphabets finis, l’espace
Ω = ×n∈N An n’est plus dénombrable. Le théorème 3.1.7 démontré ci-dessous fournit
la généralisation du théorème 3.1.6 dans le cas N = ∞.
Théorème 3.1.7. Soit (An )n∈N une suite d’alphabets dénombrables. On note X = ×n∈N An
le produit cartésien infini des ces alphabets et x = ( x0 , x1 , . . .) ∈ X un mot infini fixé. Sup-
posons que ρ0 est un vecteur de probabilité sur A0 et pour tout k ≥ 1, ρk,xk−1 un vecteur
de probabilité sur Ak . L’espace des événements (Ω, F ) s’obtient par identification Ω = X
et F = ⊗n∈N P (An ). On note X = ( X0 , X1 , . . .) une variable aléatoire sur (Ω, F ) où
Xn : Ω → An est la projection sur la ne lettre. Alors, il existe une unique probabilité P
sur (Ω, F ) vérifiant, pour tout N ∈ N et tout x ∈ X,
P( X0 = x0 , . . . , X N = x N ) = ρ0 ( x0 )ρ1,x0 ( x1 ) · · · ρ N,xN −1 ( x N ).
P( X0 = x0 , . . . , X N = x N ) = ρ0 ( x0 )ρ1,x0 ( x1 ) · · · ρ N,xN −1 ( x N )
= P 0 ( X0 = x 0 , . . . , X N = x N ) ,
/Users/dp/a/ens/[Link] 23
2019-09-19 • 11:36:00.
3.2. Indépendance Probabilité conditionnelle et indépendance
on constate qu’elles coïncident sur G . Comme G engendre F et est fermée par intersec-
tion finie, elles coïncideront sur F .
Existence. Si nous choisissons Ω = I∅ := [0, 1[ muni de la tribu borélienne F =
B([0, 1[), on peut le probabiliser par la mesure de Lebesgue λ. On introduit une par-
tition de I∅ en cardA0 en cardA0 intervalles semi-ouverts contigus I∅ = t x0 ∈A0 Ix0 en
imposant λ( Ix0 ) = ρ0 ( x0 ). Supposons que nous ayons construit une partition à l’ordre
k − 1, i.e. pour x0 · · · xk−1 ∈ A0 × · · · × Ak−1 , nous disposons de la famille exhaustive
d’intervalles disjoints contigus Ix0 ··· xk−1 dont les longueurs vérifient
Nous obtenons une partition à l’ordre k, en écrivant chacun de ceux intervalles comme
une partition plus fine
Ix0 ··· xk−1 = t xk ∈Ak Ix0 ··· xk ,
avec λ( Ix0 ··· xk ) = λ( Ix0 ··· xk−1 )ρk,xk−1 ( xk ). Cette construction peut être répétée ad infini-
tum.
Pour chaque k, la famille ( Ix )x∈A0 ×···×Ak forme une partition de Ω. Il s’ensuit que
pour chaque ω ∈ Ω, il existe un unique intervalle de la génération k qui le contient,
i.e. il existe une suite X (ω ) = ( X0 (ω ), X1 (ω ), . . .) ∈ X ' Ω telle que ω ∈ IX0 (ω )···Xk (ω ) ,
pour tout k ∈ N. L’application X : Ω → X est un variable aléatoire. En effet, pour tout
G = { X0 = x0 , . . . , Xk = xk } ∈ G , on aura X −1 ( G ) = Ix0 (ω )··· xk ∈ F := B([0, 1[). En
outre, λ ◦ X −1 définit bien une probabilité P sur (Ω, F ) ayant les propriétés requises.
Il est évident que l’expression que nous avons établi pour le membre de gauche (i.e.
P( X0 = x0 , . . . , X N = x N )) dans l’expression ci-dessus entraîne que P définit aussi une
probabilité sur A0 × · · · × A N .
Définition 3.1.8. La probabilité P, dont l’existence et l’unicité sont établies dans le
théorème 3.1.6 est appelée loi ou probabilité conjointe de la suite aléatoire ( X0 , X1 , . . . , ).
La probabilité sur A0 × · · · × A N définie par sommation partielle sur toutes les valeurs
x N +1 , x N +2 , . . . non observées est appelée probabilité marginale.
3.2 Indépendance
La signification intuitive de l’indépendance entre deux événements A et B est que
la probabilité de B n’est pas influencée par la révélation que A s’est réalisé (ou vice
versa avec les rôles de A et B interchangés). Ceci nous incite à introduire la notion
d’indépendance par la
Définition 3.2.1. Soit (Ω, F , P) un espace de probabilité. Deux événement A, B ∈ F
sont indépendants par rapport à la probabilité P si
P( A ∩ B ) = P( A )P( B ).
Remarque 3.2.2. — Un fait qui est souvent négligé est que l’indépendance entre
deux événements n’est pas une propriété intrinsèque des événements en consi-
dération mais fait intervenir de manière cruciale la probabilité sous-jacente. (Cf.
/Users/dp/a/ens/[Link] 24
2019-09-19 • 11:36:00.
Probabilité conditionnelle et indépendance 3.2. Indépendance
exercice 37). Deux événements A et B sur (Ω, F ) peuvent être indépendants par
rapport à une probabilité P sur F et dépendants par rapport à une probabilité
P0 .
— L’indépendance définie en 3.2.1, appelée aussi indépendance stochastique, ne
doit pas être confondue avec un autre type d’indépendance, l’indépendance
causale, entre deux événements, signifiant qu’il n’y a pas de relation de cause à
effet entre eux. (Cf. exercice 38).
P ∩ j ∈ J A j = ∏ P( A j ).
j∈ J
2. Soient (Xi , X )i∈ I une famille d’espace d’événements et ( Xi )i∈ I une famille de
variables aléatoires avec Xi : Ω → Xi . La famille est indépendante si pour
tout choix d’événements Bi ∈ Xi , la famille d’événements ({ Xi ∈ Bi })i∈ I est
indépendante, i.e. si pour toute partie finie J avec ∅ 6= J ⊆ I, nous avons
P ∩ j∈ J { X j ∈ Bj } = ∏ P({ X j ∈ Bj }).
j∈ J
(Le cas trivial cardJ = 1 est inclus dans cette définition pour de raisons de simplicité).
Une famille d’événements (ou de variables aléatoires) peut être telle que si l’on
considère deux éléments arbitraires de la famille, ils sont indépendants sans que la
famille soit indépendante comme le montre le
Contre-exemple 3.2.4. On lance une pièce deux fois de suite. L’univers est Ω = {0, 1}2 ;
on probabilise sa tribu exhaustive avec la probabilité uniforme sur Ω. Considérer les
événements
Alors
1 1
P( A ∩ B ∩ C ) =6 = = P( A )P( B )P( C ),
4 8
tandis que les événements pris deux-à-deux sont indépendants.
N N
P ( X1 = x 1 , . . . , X N = x n ) = ∏ P( Xn = x n ) = ∏ ρ n ( x n ).
n =1 n =1
/Users/dp/a/ens/[Link] 25
2019-09-19 • 11:36:00.
3.3. Exercices Probabilité conditionnelle et indépendance
(Étant donné que les ρn ne dépendent pas dex xi , i < n, nous pouvons calculer les
marginales arbitraires). Ceci reste valable même pour des suites infinies ( Xn )n∈N de
variables aléatoires Xn : Ω → An indépendantes, sur des alphabets dénombrables
(An ). Le théorème ?? combiné avec la propriété d’indépendance implique qu’il existe
une suite infinie de vecteurs de probabilité (ρn ) et une unique probabilité P telles que
pour toute partie finie non-vide J ⊆ N, on ait
P ∩ j ∈ J { X j = x j } = ∏ ρ j ( x j ).
j∈ J
3.3 Exercices
Probabilité conditionelle
Dans tout ce paragraphe, on travaille sur un espace probabilité (Ω, A, P). Tous les
événements utilisés, A, B, ( Ak ), . . ., appartiennent à A.
28. Montrer que le formules suivantes :
P( B| A) + P( B| Ac ) = 1 et P( B| A) + P( Bc | Ac ) = 1
sont fausses.
29. Pour une famille d’événements ( Ak )k=1,...,n indépendante, noter pk = P( Ak ).
Calculer la probabilité de l’événement « aucun des ( Ak ) ne se réalise ».
30. Soient A et B deux événements indépendants, avec p = P( A) et q = P( B).
Calculer les probabilités pour que
(a) exactement k,
(b) au moins k,
(c) au plus k,
des événements A et B se réalisent pour k = 0, 1, 2.
31. Exprimer P(∪nk=1 Ak ) lorsque les Ak sont indépendants.
32. Un lot de 100 objets manufacturés subit un contrôle par échantillonnage : un
échantillon de 5 objets est examiné et s’il contient un article défectueux, tout le
lot est rejeté. Quelle est la probabilité qu’un lot soit rejeté s’il contient 5% d’objets
défectueux ?
33. Une personne a oublié le dernier digit du numéro de téléphone de son corres-
pondant ; elle compose donc au hasard. Quelle est la probabilité p qu’elle soit
obligée de composer moins de 3 fois (≤ 3) ? Que devient cette probabilité, si la
personne se souvient que le dernier digit est impair ?
34. Une personne écrit n lettres différentes, chacune destinée a un destinataire spé-
cifique. Elle les a scellées et posées bien rangées en pile sur son bureau afin
d’écrire le lendemain les adresses sur les enveloppes. Un plaisantin est passé
par là, il a renversée la pile par erreur et il a remis les enveloppes sur le bureau
mais dans un ordre aléatoire par rapport à l’ordre correct. Ignorant ce fait, la
personne qui a rédigé les lettres a inscrit le lendemain les adresses. Quelle est la
probabilité qu’une lettre parvienne à la personne à laquelle elle était destinée ?
35. Le circuit électrique suivant comporte 5 interrupteurs, notés a à e ; chacun d’eux
peut être fermé (laisse le courant passer) avec probabilité p ou ouvert (coupe le
courant) avec probabilité q = 1 − p.
/Users/dp/a/ens/[Link]
26
2019-09-02 • 10:27:15.
Probabilité conditionnelle et indépendance 3.3. Exercices
a b
c d
(a) Quelle est la probabilité pour que le courant passe de gauche à droite ?
(b) Sachant que le courant passe de gauche à droite, quelle est la probabilité
pour que l’interrupteur e soit fermé ?
Indépendance
37. Une urne contient n boules noires et r boules rouges et on considère l’espace
Ω = {1, . . . , n + r }2 (qui peut décrire toutes les expériences d’extraction de deux
boules avec ou sans remise). On note
A = {la première boule est rouge} = {ω ∈ Ω : ω1 ∈ {1, . . . , r }}
et
B = {la seconde boule est rouge} = {ω ∈ Ω : ω2 ∈ {1, . . . , r }}.
(a) On en extrait une boule, on la remet dans l’urne et on en extrait une seconde ;
on note P la probabilité uniforme sur Ω. Les événements A et B sont-ils
indépendants (par rapport à P) ?
(b) On extrait une première boule et sans la remettre dans l’urne, on en extrait
une seconde. On note P0 la probabilité uniforme sur
Ω0 = {ω = (ω1 , ω2 ), ωi ∈ {1, . . . , n + r }, ω1 6= ω2 } ⊂ Ω.
La probabilité P0 peut être étendue en une probabilité, aussi notée P0 , sur
Ω chargeant avec le masse 0 les éléments de Ω \ Ω0 . Les événements A et B
sont-ils indépendants (par rapport à P0 ) ?
38. On jette un dé deux fois de suite et on note Ω = {1, . . . , 6}2 l’espace des épreuves
correspondant. On munit la tribu exhaustive de cet espace de la probabilité uni-
forme et on considère les événements A = {la somme est 7} et B = {le premier dé tombe sur 6
(a) Montrer que A et B sont indépendants (sous la probabilité uniforme).
(b) Montrer que A est déterminé de B de manière causale.
/Users/dp/a/ens/[Link] 27
2019-09-19 • 11:36:00.
3.3. Exercices Probabilité conditionnelle et indépendance
/Users/dp/a/ens/[Link] 28
2019-09-19 • 12:12:07.
Espérance, variance ; théorèmes des
4
grands nombres
4.1 Espérance
Soient (Ω, F , P) un espace de probabilité et (X, X ) un espace d’événements avec
X ⊂ R avec cardX = n. Alors, il existe des réels distincts xi , i = 1, . . . , n tels que X =
{ x1 , . . . , xn }. Une variable aléatoire X : Ω → X peut alors s’écrire à l’aide de la partition
Ai = { X = xi }, i = 1, . . . , n comme X (ω ) = ∑in=1 xi 1 Ai (ω ). La loi de X s’exprime en
termes du vecteur de probabilité ρ vérifiant pi := ρ( xi ) = P( X = xi ) = P( Ai ), pour
i = 1, . . . , n. Si nous observons N réalisations de la variable aléatoire X, nous nous
attendons à ce que xi soit obtenu approximativement N pi fois. Si nous exprimons la
moyenne pondérée des N réalisations de X, nous obtenons
n
1
[ N p1 x1 + . . . + N p n x n ] = ∑ p i x i .
N i =1
Définition 4.1.1. 1. Une variable aléatoire réelle discrète X sur (Ω, F , P) est dite
intégrable (plus précisément P-intègrable) si ∑ x∈X (Ω) | x |P({ X = x }) < ∞. On
note alors X ∈ L1 := L1 (Ω, F , P).
29
4.1. Espérance Espérance, variance ; théorèmes des grands nombres
= ∑ xPX ({ x })
x ∈ X (Ω)
= ∑ xρ X ( x )
x ∈ X (Ω)
Démonstration.
/Users/dp/a/ens/[Link] 30
2019-09-19 • 12:12:07.
Espérance, variance ; théorèmes des grands nombres 4.2. Variance et covariance
Il faudrait bien sûr donner un sens aux intégrales (de Lebesgue) qui apparaissent
dans la définition précédente. Cependant, dans tous les cas qui se présenteront dans
ce cours, nous pouvons considérer que ces intégrales sont égales aux intégrales habi-
tuelles (de Riemann).
Cov( X, Y )
r ( X, Y ) = p .
Var( X )Var(Y )
Démonstration. Exercice !
/Users/dp/a/ens/[Link] 31
2019-09-19 • 12:12:07.
4.3. Fonction génératrice Espérance, variance ; théorèmes des grands nombres
La série entière qui définit la fonction G converge lorsque z se trouve dans l’inter-
valle [0, 1] car G (1) = 1. Calculons formellement G 0 (z) = ∑ x≥1 ρ X ( x ) xz x−1 . Mainte-
nant, rien ne garantit plus que G 0 (1) < ∞ ; pour que cela soit le cas, il faut que la série
entière ∑ x≥1 ρ X ( x ) x < ∞. Mais ∑ x≥1 ρ X ( x ) x = E( X ).
Plus généralement, la fonction génératrice contient de manière condensée plusieurs
caractéristiques de la loi de X comme le montre le théorème suivant :
Théorème 4.3.2. Soit X est une variable aléatoire sur (Ω, F , P), à valeurs dans X = N ; on
note ρ X la densité discrète de PX et G la fonction génératrice de X. Alors
n
1. Pour tout n ∈ N, on a ρ X (n) = n! 1 d G
dzn (0). Par conséquent, la fonction génératrice
détermine de manière unique la loi de la variable aléatoire X.
2. E( X ) < ∞ si, et seulement si, G 0 (1−) existe et, dans ce cas, E( X ) = G 0 (1−) =
limz↑1 G 0 (z).
3. Var( X ) < ∞ si, et seulement si, G 00 (1−) existe et, dans ce cas, Var( X ) = G 00 (1−) −
G 0 (1−)2 + G 0 (1−).
3. La fonction caractéristique est réelle si, et seulement si, elle provient d’une loi symé-
trique.
(r )
4. Si pour un entier n ≥ 1 on a E| X |n < ∞, alors χ X existe pour tout entier r ≤ n et
limt→0 ε n (t) = 0.
(r )
— χ X (t) = R (ix )r exp(itx )PX (dx ),
R
/Users/dp/a/ens/[Link] 32
2019-09-19 • 12:12:07.
Espérance, variance ; théorèmes des grands nombres 4.4. Fonction caractéristique
(r )
χ X (0)
— EX r = ir ,
(it)r (it)n
— χ X (t) = (∑rn=0 r! EX r ) + n! ε n (t), où ε n (t) ≤ 3E| X |n et limt→0 ε n (t) = 0.
(2n)
5. Si χ X (0) existe et est finie, alors EX 2n < ∞.
(E| X |n )1/n
6. Si E| X |n < ∞ pour tout n ≥ 1 et lim supn→∞ n
1
= eR < ∞, alors
(it)n
χ X (t) = ∑ n! EX n ,
n ∈N
n n
∑ ∑ χ(t j − tk )z j zk ≥ 0.
j =1 k =1
Théorème 4.4.3 (Critère de Bochner). Une application f : R → C est une fonction ca-
ractéristique si, et seulement si, elle définit un noyau positif, elle est continue en 0 et vérifie
f (0) = 1.
Démonstration. Voir [12, Théorème 6.5.2, page 180] ou [38, Théorème 4.2.1, pp. 71–73]
par exemple.
Comme un cas particulier d’un résultat de Cramér [15] sur la représentation des
certaines fonctions par des intégrales de Fourier, on a aussi le
Théorème 4.4.4 (Critère de Cramér). Une fonction f complexe, bornée, continue sur R est
caractéristique, si et seulement si,
1. f (0) = 1 et
2. la fonction g, définie par
Z AZ A
g( x, A) = f (t − s) exp(i (t − s) x )dtds,
0 0
/Users/dp/a/ens/[Link] 33
2019-09-19 • 12:12:07.
4.5. Théorèmes des grands nombres Espérance, variance ; théorèmes des grands nombres
/Users/dp/a/ens/[Link] 34
2019-09-19 • 12:12:07.
Espérance, variance ; théorèmes des grands nombres 4.5. Théorèmes des grands nombres
E(|ξ |)
P(|ξ | ≥ ε) ≤
ε
E( ξ 2 )
P(|ξ | ≥ ε) ≤
ε2
Var(ξ )
P(|ξ − E(ξ )|) ≥ ε) ≤ (inégalité de Bienaymé-Tchebychev).
ε2
E(Sk ) = km
Var(Sk ) = kσ2 .
Théorème 4.5.7 (Théorème faible des grands nombres). Soit ( Xk )k∈N une suite de va-
riables aléatoires indépendantes et identiquement distribuées, définies sur (Ω, F , P), à valeurs
dans X ⊆ R, telles que E( X12 ) < ∞. Alors
Sn ( ω )
∀ε > 0, lim P ω∈Ω: − E ( X1 ) ≥ ε
= 0.
n→∞ n
/Users/dp/a/ens/[Link] 35
2019-09-19 • 12:12:07.
4.5. Théorèmes des grands nombres Espérance, variance ; théorèmes des grands nombres
σ2
Sn Var(Sn )
P − E( X1 ) ≥ ε = P (|Sn − nE( X1 )| ≥ nε) ≤
= → 0.
n n2 ε nε2
Définition 4.5.8. Soit (ξ n )n∈N une suite de variables aléatoires définies sur un espace
de probabilité (Ω, F , P) et ξ une autre variable sur (Ω, F , P). On dit que la suite (ξ n )
P
converge en probabilité vers ξ, et on note limn→∞ ξ n = ξ, si
Remarque 4.5.9. Le théorème faible des grands nombres établit que pour une suite de
variables aléatoires indépendantes, identiquement distribuées et de carré intégrables,
∑n X P
on a limn→∞ k=n1 k = E( X1 ). Les conditions d’applicabilité du théorème peuvent être
affaiblies de différentes manières.
— Pour des variables aléatoires de carré intégrables, le théorème reste valable pour
des variables qui sont seulement décorrélées au lieu d’être indépendantes ; même
la condition d’équidistribution peut être affaiblie. On a alors limn→∞ n1 ∑nk=1 ( Xk −
P
E( Xk )) = 0.
— La condition de carré-intégrabilité peut être affaiblie en une condition d’intégra-
bilité. La suite doit, dans ce cas, rester indépendante et équidistribuée (voir [55,
P
Théorème 2, §III.3, pp. 325–326]). On a alors limn→∞ 1
n ∑nk=1 Xk = E( X1 ).
Lemme 4.5.10. Soient (ζ n ) et (ξ n ) des suites de variables aléatoires sur (Ω, F , P) et ( an )
une suite numérique. Alors
P P P
1. [limn∈N ζ n = 0] ∧ [limn∈N ξ n = 0] =⇒ [limn∈N (ζ n + ξ n ) = 0].
P P
2. [limn∈N ξ n = 0] ∧ [supn∈N | an | < ∞] =⇒ [limn∈N an ξ n = 0].
Définition 4.5.11. Soit (ξ n )n∈N une suite de variables aléatoires définies sur un espace
de probabilité (Ω, F , P) et ξ une autre variable sur (Ω, F , P). On dit que la suite (ξ n )
p.s.
converge presque sûrement vers ξ, et on note limn→∞ ξ n = ξ, si
Théorème 4.5.12 (Théorème fort des grands nombres). Soit une suite ( Xn ) de variables
aléatoires réelles définies sur un espace de probabilités (Ω, F , P) qui sont deux-à-deux décor-
rélées et vérifiant supn∈N Var( Xn ) < ∞. Alors
1 n p.s.
lim
n→∞ n
∑ ( Xk − E( Xk )) = 0.
k =1
/Users/dp/a/ens/[Link] 36
2019-09-19 • 12:12:07.
Espérance, variance ; théorèmes des grands nombres 4.6. Théorème central limite
Loi X ρ χ
Binomiale Bn,p {0, . . . , n} Cnx p x (1 − p )n− x (1 − peit )n
x
Poisson(λ) N exp(−λ) λx! exp(λ(eit − 1))
1 eitb −eita
Uniforme [ a, b] [ a, b] ⊂ R 1
b− a 1[ a,b] ( x ) b− a it
√ 1 exp(− ( x −m )2
Normale N (m, σ2 ) R 2σ 2 ) exp(itm − t2 σ2 /2)
2πσ
Γ( p, λ) R+ 1
Γ( p)
p
λ x p − 1 exp(−λx ) (1 − itλ )− p
Théorème 4.6.3. (Théorème central limite) Soit ( Xn )n∈N une suite de variables aléatoires
indépendantes et identiquement distribuées avec EX1 = m et VarX1 = σ2 . En notant Sn =
∑nk=1 Xk , on a
Sn − nm
lim P √ ≤ x = Φ0,1 ( x ),
n→∞ σ n
où Φ0,1 désigne la fonction de répartition d’une variable aléatoire normale d’espérance 0 et de
variance 1.
/Users/dp/a/ens/[Link] 37
2019-09-19 • 12:12:07.
4.6. Théorème central limite Espérance, variance ; théorèmes des grands nombres
La convergence établie par ce théorème est une convergence plus faible que la
convergence en probabilité ; on l’appelle convergence en loi.
Définition 4.6.4. Soient (ξ n )n∈N une suite de variables aléatoires réelles sur un espace
(Ω, F , P) et ξ une variable aléatoire réelle sur le même espace. On dit que la suite
(ξ n )n∈N converge en loi vers ξ, et l’on note 1 limn→∞ ξ n = ξ, si, pour tout x ∈ R,
loi
Démonstration du théorème 4.6.3. Puisque pour toute variable aléatoire réelle X et tout
couple de nombres réels a, b on χ aX +b (t) = χ X ( at) exp(itb), on peut sans perte de
généralité, supposer que EX1 = 0.
On utilise l’indépendance des variables et les faits que χ0X1 (0) = EX1 = 0 et
χ00X1 (0) = EX12 = σ2 pour des variables d’espérance nulle et de variance σ2 , pour écrire
n
Sn t
E(exp(it √ ) = χ √ .
σ n σ n
σ2 √
Or, en utilisant la proposition 4.4.2, on a, pour grand n, que χ( σ√t n ) = 1 − t
2 (σ n)
2 +
|t|
o ( σ √ n )2 . Par conséquent,
2 2 ! n
σ2 |t|
Sn t
lim E(exp(it √ )) = 1− √ +o √ = exp(−t2 /2) = χN (0,1) (t), t ∈ R,
n→∞ σ n 2 σ n σ n
où χN (0,1) est la fonction caractéristique de la loi normale centrée (i.e. d’espérance
nulle) réduite (i.e. de variance 1).
Remarque 4.6.5. La condition de carré intégrabilité ne peut pas être affaiblie. Si les
variables aléatoires de la suite sont intégrables mais pas de carré
√ intégrables (i.e. ont
des “queues lourdes”), la bonne normalisation n’est plus en n mais des exposants
déterminés par la puissance des moments fractionnaires qui existent et la convergence
peut avoir lieu vers des lois stables autres que la loi normale.
Dans ce chapitre, nous avons introduit plusieurs notions de convergence : en proba-
bilité, presque sûre, en loi. On peut introduire d’autres, par exemple les convergences
en L p , avec p ∈ [1, ∞[ définies par
Lp
lim ξ n = ξ ⇔ lim kξ n − ξ k p = 0.
n n
La raison d’être de toutes ces définition est qu’elles ne sont pas équivalentes ; nous
avons l’hiérarchie suivante :
p.s.
ξ n −→ ξ
P loi
ξ n −→ ξ ξ n −→ ξ
Lp
ξ n −→ ξ
d
1. Cette convergence est aussi notée limn→∞ ξ n =ξ, surtout dans la littérature anglo-saxonne (pour
convergence in distribution).
/Users/dp/a/ens/[Link]
38
2019-09-02 • 10:29:38.
Espérance, variance ; théorèmes des grands nombres 4.7. Exercices
4.7 Exercices
Lois, espérance, variance
39. Soit α la variable aléatoire définie sur (Ω, F , P) qui prend des valeurs dans X =
{0, π/2, π } avec probabilité uniforme. On note X = sin α et Y = cos α. Calculer
(a) EX,
(b) EY,
(c) Cov( X, Y ),
(d) P( X = 1, Y = 1).
Quelle est votre conclusion ?
40. Soient (ξ k )k=1,...,n des variables aléatoires indépendantes sur (Ω, F , P) prenant
un nombre fini de valeurs réelles. Calculer la loi de X = max ξ k , k = 1, . . . , n et
de Y = min{ξ k , k = 1, . . . , n}.
41. Soient (ξ k )k=1,...,n des variables aléatoires indépendantes sur (Ω, F , P) à valeurs
dans X = {0, 1} et (λk )k=1,...,n une suite de nombres strictement positifs fixés.
On sait que P(ξ k = 1) = λk ∆ avec ∆ un petit nombre réel strictement positif.
(a) Pouvez-vous donner une borne sur ∆ qui traduit proprement la notion de
« petitesse » ?
(b) Estimer P(ξ 1 + . . . + ξ n = 1) en ordre ∆2 .
(c) Estimer P(ξ 1 + . . . + ξ n > 1).
42. Soient X et Y deux variables aléatoires réelles sur (Ω, F , P) avec VarX > 0 et
VarY > 0.
(a) Montrer que |r ( X, Y )| ≤ 1.
(b) Monter que |r ( X, Y )| = 1 si et seulement si X = aY + b.
43. Soit ξ une variable aléatoire réelle avec E(ξ 2 ) < ∞.
(a) Montrer que E(|ξ |) < ∞.
(b) Montrer que infa∈R E((ξ − a)2 ) est atteint pour une valeur a0 ∈ R. Détermi-
ner ce a0 .
(c) Déterminer la valeur de infa∈R E((ξ − a)2 ) en termes d’une caractéristique
de ξ.
44. Soit ξ une variable aléatoire réelle de loi Pξ et fonction de répartition Fξ .
(a) Déterminer Faξ +b pour a > 0 et b ∈ R.
(b) Déterminer Fξ 2 .
45. Soit ξ + = max(ξ, 0). Déterminer Fξ + .
46. Soient ξ, η de variables aléatoires réelles définies sur (Ω, F , P) à valeurs dans
une partie discrète X ⊂ R. On note P(ξ,η ) leur loi conjointe et on suppose que les
marginales unidimensionnelles Pξ et Pη sont symétriques et telles que Varξ =
Varη = 1. On note r := r (ξ, η ) le coefficient de corrélation de ξ et η. Monter que
p
E(max(ξ 2 , η 2 )) ≤ 1 + 1 − r2 .
47. (Identité de Wald). Soient ( Xn )n∈N une suite de variables aléatoires réelles, indé-
pendantes et identiquement distribuées définies sur (Ω, F , P) et τ une variable
aléatoire définie sur le même espace (Ω, F , P), à valeurs dans N. Nous suppo-
sons que E(| X1 |) < ∞, E(τ ) < ∞ et que pour tout n ∈ N, l’événement {τ ≥ n}
/Users/dp/a/ens/[Link]
39
2019-09-02 • 10:29:38.
4.7. Exercices Espérance, variance ; théorèmes des grands nombres
a une espérance et que E(Sτ ) = E(τ )E( X1 ). (La somme Sτ est une somme par-
tielle de la série de terme général Xn comportant un nombre aléatoire de termes).
Fonctions génératrices
48. On rappelle qu’une variable aléatoire X est dite suivre la loi binomiale Bn,p de
paramètres p ∈ [0, 1] et n ≥ 1 si P( X = k ) = Cnk pk (1 − p)n−k , pour k = 1, . . . , n.
(a) Calculer la fonction génératrice G := GBn,p correspondante.
(b) Calculer E( X ) à l’aide de la fonction génératrice.
(c) Calculer Var( X ) à l’aide de la fonction génératrice.
49. On rappelle qu’une variable aléatoire X est dite suivre la loi exponentielle Eλ de
k
paramètre λ > 0 si P( X = k ) = exp(−λ) λk! , pour k ∈ N.
(a) Calculer la fonction génératrice G := GEλ correspondante.
(b) Calculer E( X ) à l’aide de la fonction génératrice.
(c) Calculer Var( X ) à l’aide de la fonction génératrice.
50. Soient X et Y deux variables aléatoires indépendantes sur (Ω, F , P) à valeurs
dans N. Exprimer la fonction génératrice GX +Y de la somme X + Y, en termes
de fonctions génératrices GX et GY des variables individuelles.
51. En se servant du résultat de l’exercice 50, déterminer GBn,p en termes de GB1,p et
comparer avec le résultat direct, obtenu en exercice 48.
52. (Extrait du CC du 16 novembre 2017).
Soit p := ( pn )n∈N la suite définie par
an
pn = , pour n ∈ N et a > 0.
(1 + a ) n +1
(a) Montrer que pour tout a > 0, la suite p est un vecteur de probabilité sur N.
(b) Soit X une variable aléatoire sur un espace probabilisé (Ω, F , P) à valeurs
dans N dont la loi est déterminée par le vecteur de probabilité p. Calculer la
fonction génératrice GX (z) de X pour z ∈ [−1, 1].
(c) Calculer GX0 ( z ) et G 00 ( z ).
X
(d) En déduire E( X ) et Var( X ).
53. Une somme de variables aléatoires comportant un nombre aléatoire de termes.
(Extrait de l’examen du 15 décembre 2018).
Soient ( Xn )n≥1 une suite de variables aléatoires réelles de carré intégrables et
d’espérance nulle et N une variable aléatoire à valeurs dans N, indépendante
de la suite ( Xn ), de loi ν(k) = P( N = k ) = 2k1+1 pour tout k ∈ N. On note
S N = ∑nN=1 Xn et σ2 = var( X1 ).
(a) Calculer la fonction génératrice G (z) = E(z N ) et s’en servir pour calculer
E( N ).
(b) Montrer que E(S N ) = 0.
(c) Calculer var(S N ). (Utiliser l’indépendance !)
/Users/dp/a/ens/[Link]
40
2019-09-02 • 10:29:38.
Espérance, variance ; théorèmes des grands nombres 4.7. Exercices
Eξ
P( ξ ≥ a ) ≤ .
a
(b) Soient a > 0 et f : R → R+ une fonction croissante telle que f ( a) > 0.
Montrer que
E( f (ξ ))
P( ξ ≥ a ) ≤ .
f ( a)
(c) En conclure que
(d) Soit ( Xi )i∈N une suite de variables aléatoires indépendantes à valeurs dans
{0, 1} et de même loi, chargeant 1 avec probabilité p, avec p ∈]0, 1[. Calculer,
pour un s > 0 arbitraire,
!
n
g(s) := E exp(s ∑ Xi )
i =1
a −a
où h( a, p) := − a log p − (1 − a) 11− p.
55. Soit (ξ n )n∈N une suite de variables aléatoires indépendantes réelles et de même
loi, vérifiant P(ξ n = 1) = p = 1 − P(ξ n = −1), pour tout n ∈ N. On note
Sn = ∑in=1 ξ i . Le but de l’exercice est d’établir, dans le cas particulier où p = 1/2,
la formule (valable pour p ∈ [0, 1] arbitraire)
Sn
∀ε > 0, P − (2p − 1) ≥ ε ≤ 2 exp(−αε2 n),
n
/Users/dp/a/ens/[Link]
41
2019-09-02 • 10:29:38.
4.7. Exercices Espérance, variance ; théorèmes des grands nombres
57. Soit (Ψn )n≥1 une suite de variables aléatoires indépendantes, uniformément dis-
tribuées sur [0, 2π [, définies sur (Ω, F , P). Une particule se déplace aléatoire-
ment dans le plan selon la règle suivante : lorsque à l’instant n elle est en posi-
tion ξ n ∈ R2 , à l’instant n + 1 elle sera en une position ξ n+1 ∈ R2 telle que la
longueur du déplacement ξ n+1 − ξ n est une constante r > 0 et l’angle formé par
ce déplacement et l’axe des abscisses est Ψn+1 . Soit Dn2 = kξ n − ξ 0 k2 la distance
entre les positions initiale et au temps n de la particule.
ξ
(a) Calculer limn→∞ nn .
(b) Calculer E( Dn2 ).
Dn2
(c) Calculer limn→∞ n .
58. Soit ( Tn )n∈N une suite de variables aléatoires indépendantes et identiquement
distribuées à valeurs réelles positives, bornées (donc intégrables), définies sur
(Ω, F , P). La variable aléatoire Tn sera interprétée comme représentant la durée
de vie de la ne ampoule changée. Dès qu’une ampoule est grillée on la remplace
aussitôt. Pour tout t > 0, on note
N
Nt = sup{ N ≥ 1 : ∑ Tn ≤ t}
n =1
p.s.
le nombre d’ampoules utilisées jusqu’au temps t. Montrer que limt→∞ Nt t =
1
E( T1 )
.
59. (Extrait du contrôle du 16 novembre 2017).
On considère un espace probabilisé (Ω, F , P) suffisamment grand pour pouvoir
contenir simultanément toutes les variables aléatoire dont on se servira dans cet
exercice.
(a) Soient X et Y deux variables aléatoires sur (Ω, F , P) à valeurs dans X =
{0, 1}. La loi de X est déterminée par le vecteur de probabilité p = ( p, 1 − p)
et celle de Y par le vecteur q = (q, 1 − q), où 0 ≤ p, q ≤ 1. Exprimer la valeur
r := P( X = Y ) en fonction des p et q.
(b) Calculer Var(1{X =Y } ).
(c) On considère maintenant deux suites définies sur (Ω, F , P). La première
est une suite ( Xn )n∈N de copies indépendantes de X (i.e. elle est indépen-
dante et identiquement distribué selon la loi p). La seconde est une suite
(Yn )n∈N de copies indépendantes de Y (i.e. elle est indépendante et iden-
tiquement distribué selon la loi q). La deux suites sont en outre mutuelle-
ment indépendantes. Utiliser un résultat du cours pour montrer que la suite
1 N
N ∑n=1 1{ Xn =Yn } converge en probabilité vers une constante qu’il faudra dé-
terminer.
/Users/dp/a/ens/[Link] 42
2019-09-19 • 12:12:07.
Chaînes de Markov sur des espaces
5
d’états dénombrables
i.e. l’évolution future du système oublie le passé pour ne se souvenir que du présent.
Cette condition de dépendance s’appelle propriété faible de Markov.
Cette évolution est un cas particulier du théorème 3.1.7. Il est évident que ∀ x, y ∈ X,
nous avons Px,y ≥ 0 et ∑z∈X Px,z = 1, i.e. chaque ligne de la matrice P = ( Px,y ) x,y∈X est
un vecteur de probabilité sur X. Une telle matrice est appelée matrice stochastique.
43
5.1. Probabilités de transition, matrices stochastiques Chaînes de Markov
À cause de la forme simplifiée qu’a le second membre, nous pouvons alors calculer la
ne marginale
Pρ0 ( Xn = x n ) = ∑ ρ0 ( x0 ) Px0 ,x1 · · · Pxn−1 ,xn
x0 ,...,xn−1 ∈X
= (ρ0 Pn )( xn ),
où le vecteur de probabilité ρ0 est écrit sous forme de vecteur ligne. On voit donc que
dans l’hiérarchie des modèles décrits par le théorème ??, le modèle de dépendance
markovienne se situe au niveau de complexité juste au dessus du modèle indépendant
introduit en §3.2.
Lorsque le vecteur ρ0 (y) = δx,y pour un x ∈ X donné, nous écrivons Px au lieu de
Pρ0 . Nous avons alors Px ( Xn = y) = Pn ( x, y).
Exemple 5.1.2. On dispose de deux pièces de monnaie, une honnête et une lestée,
donnant « face » avec probabilité 1/3. Si la pièce lancée au ne jeu montre « pile » on
utilise la pièce honnête pour la lancer au (n + 1)e jeu ; si elle montre « face » on utilise
la pièce lestée pour jouer au (n + 1)e jeu. Si on note ( Xn ) la suite de variables aléatoires
dans X = {0, 1} correspondant à ce jeu, elles constituent une chaîne de Markov, avec
probabilité conditionnelle de transition
P( Xn+1 = y| Xn = x ) = Pxy ,
1 1
où la matrice P := ( Pxy ) x,y∈X est égale à P = 22 21 . L’étude du comportement
3 3
asymptotique à grand n de la probabilité Pρ0 ( Xn = x ) = (ρ0 Pn )( x ) peut se faire en
s’inspirant de la méthode développée à l’exercice 63.
Théorème 5.1.3. La définition d’une chaîne de Markov est équivalente à la propriété d’in-
dépendance du futur et du passé, conditionnellement au présent. Plus précisément, en notant
pour 1 < p < n et x1 , . . . , xn ∈ X,
A = { X1 = x 1 , . . . , X p − 1 = x p − 1 } ,
B = { X p = x p },
C = { X p +1 = x p +1 , . . . , X n = x n } ,
/Users/dp/a/ens/[Link] 44
2019-11-03 • 18:29:09.
Chaînes de Markov 5.2. Temps d’arrêt. Propriété forte de Markov
nous avons
P( A ∩ C | B ) = P( A | B )P( C | B ).
Démonstration. Exercice.
Lemme 5.2.5. Les temps τA0 et τA définis dans 5.2.4 sont des temps d’arrêt par rapport à la
(filtration naturelle de) la chaîne.
Supposons que Ω = tn∈N { T = n} (et par conséquent Pρ0 ( T < ∞) = 1). Par
ailleurs, la chaîne arrêtée à l’instant aléatoire T vérifiera :
XT ( ω ) : = XT (ω ) ( ω ) = ∑ X T ( ω ) ( ω )1{ T = n } ( ω ) = ∑ Xn ( ω )1{ T = n } ( ω ).
n ∈N n ∈N
/Users/dp/a/ens/[Link] 45
2019-11-03 • 18:29:09.
5.3. Classification des états. Recurrence, transience Chaînes de Markov
Théorème 5.2.6. Soient ( Xn )n∈N une CM(X, X , ρ), où X est dénombrable (fini ou infini) et
T un temps d’arrêt pour (la filtration naturelle de) la chaîne. On note XT≤ = ( X0 , . . . , XT ) le
passé de la chaîne et XT> = ( XT +1 , XT +2 , . . .) son futur strict (par rapport à l’instant aléatoire
T). Alors, sur l’événement { T < ∞}, la loi conditionnelle conjointe du futur strict de la chaîne
XT> sachant le passé XT≤ est égale à la loi conditionnelle conjointe du futur strict de la XT>
sachant le présent XT ; cette propriété est appelée propriété forte de Markov.
P( XT +1 = y1 , . . . XT +k = yk | T = n; X0 = x0 , . . . , Xn = xn ).
L’événement { T = n} est déterminé par les valeurs que prennent les variables aléa-
toires ( X0 , . . . , Xn ). Lorsque nous considérons les événements { T = n} et { X0 =
x0 , . . . , Xn = xn } des deux choses l’une :
— soit ils sont compatibles et dans ce cas { T = n} ∩ { X0 = x0 , . . . , Xn = xn } =
{ X0 = x 0 , . . . , X n = x n } ,
— soit ils sont incompatibles et dans ce cas { T = n} ∩ { X0 = x0 , . . . , Xn = xn } = ∅,
Dans le premier cas, en utilisant la propriété faible de Markov, on obtient sur { T = n},
P ( X n + 1 = y 1 , . . . X n + k = y k | X0 = x 0 , . . . , X n = x n ) = P ( X n + 1 = y 1 , . . . X n + k = y k | X n = x n ) .
Dans le deuxième cas, l’ensemble par rapport auquel nous conditionnons a une pro-
babilité nulle ; par conséquent, nous pouvons attribuer une valeur arbitraire à la pro-
babilité conditionnelle, par exemple la valeur prise par la probabilité conditionnelle au
premiers cas, à savoir P( Xn+1 = y1 , . . . Xn+k = yk | Xn = xn ).
Remarque 5.3.2. Il est immédiat de constater que x → y si, et seulement si, il existe une
suite finie d’arêtes dirigées composables dans le graphe de P qui forment un chemin
de x à y.
/Users/dp/a/ens/[Link] 46
2019-11-03 • 18:29:09.
Chaînes de Markov 5.3. Classification des états. Recurrence, transience
où [ x ] = {y ∈ Xe : x ↔ y}.
Démonstration. Exercice.
Définition 5.3.5. Soit ( Xn ) ∈ CM(X, P, ρ0 ) définie sur (Ω, F , P). Pour x ∈ X fixé et
tout n ≥ 1, on note qn = Px (τx = n) et q = ∑n≥1 qn = Px (τx < ∞). On dit qu’un état
x ∈ X est
— transient si q < 1,
— récurrent si q = 1,
— récurrent positif si Ex (τx ) < ∞.
Un état récurrent qui n’est pas récurrent positif est appelé récurrent nul.
Il s’avère pratique d’étendre la suite (qn )n≥1 en q0 = 0 et de définir une autre suite
(rn )n≥0 par rn = Px ( Xn = x ) = Pn ( x, x ), n ∈ N, avec bien sûr r0 = 1.
Lemme 5.3.6. Pour une chaîne de Markov et les suites (rn ) et (qn ) définies comme ci-dessus,
on a :
1. Pour tout n ≥ 0, la probabilité rn se décompose en
r n = r 0 q n + r 1 q n −1 + . . . + r n q 0 .
R(z) = ∑ rn zn et Q(z) = ∑ qn zn
n ∈N n ∈N
Démonstration. 1. On décompose
n
r n = P x ( Xn = x ) = ∑ Px (Xn = x|τx = k)Px (τx = k)
k =1
n
= ∑ r n − k q k = r 0 q n + r 1 q n −1 + . . . + r n q 0 , avec la convention q0 ≡ 1.
k =0
/Users/dp/a/ens/[Link] 47
2019-11-03 • 18:29:09.
5.3. Classification des états. Recurrence, transience Chaînes de Markov
2. Les séries définissant R(z) et Q(z) sont absolument convergentes pour |z| < 1.
En effet
1
| R(z)| ≤ ∑ rn |z|n ≤ ∑ |z|n = , et
n ≥0 n ≥0 1 − |z|
| Q(z)| ≤ ∑ qn |z|n ≤ ∑ qn = Px (τx < ∞) ≤ 1.
n ≥0 n ≥0
Démonstration. Immédiate.
Théorème 5.3.8. Un état x ∈ X est récurrent si, et seulement si, ∑n≥0 Px ( Xn = x ) = ∞.
Démonstration. L’état x est récurrent si q := ∑n≥1 qn = Q(1) = limz∈[0,1[,z→1 Q(z) = 1.
En utilisant l’expression pour R(z), établie en lemme 5.3.6, nous obtenons
1
lim R(z) = lim = ∞.
z∈[0,1[,z→1 z∈[0,1[,z→1 1 − Q ( z )
Supposons que ∑n≥0 rn < ∞. Comme tous les termes rn sont positifs, nous avons pour
tout N, ∑nN=1 rn ≤ limz∈[0,1[,z→1 R(z) = ∑n≥0 rn . Or limz∈[0,1[,z→1 R(z) = ∞, il y a donc
contradiction avec l’hypothèse ∑n≥0 rn < ∞.
Remarque 5.3.9. La condition ∑n≥0 rn = ∞ est équivalente à Ex (ηx ) = ∞, où la va-
riable aléatoire η A := ∑n≥0 1 A ( Xn ) dénombre les retours de la chaîne de Markov dans
A. Comme d’habitude, si A = {y}, on allège la notation en ηy au lieu de η{y} .
Théorème 5.3.10. Si l’état x ∈ X est récurrent alors tout état y ∈ X, accessible depuis x, est
aussi récurrent.
Démonstration. Supposons x récurrent, x → y mais y 6→ x. L’accessibilité x → y signifie
qu’il existe un entier M tel que P M ( x, y) = α > 0 ; la non-accessibilité de x à partir de
y signifie donc que Px (τx < ∞) ≤ 1 − α < 1 en contradiction avec l’hypothèse de
récurrence de x. Il existe donc un entier N tel que P N (y, x ) = β > 0. Nous avons donc
pour tout entier n ≥ 0
P M+ N +n (y, y) ≥ P N (y, x ) Pn ( x, x ) P M ( x, y) = βαPn ( x, x )
et
P M+ N +n ( x, x ) ≥ P M ( x, y) Pn (y, y) P N (y, x ) = αβPn (y, y).
Par conséquent, les séries ∑n≥0 Pn ( x, x ) et ∑n≥0 Pn (y, y) soit elles convergent simulta-
nément soit elles divergent simultanément. On conclut par le théorème 5.3.8.
/Users/dp/a/ens/[Link] 48
2019-11-03 • 18:29:09.
Chaînes de Markov 5.4. Probabilité limite, probabilité invariante (stationnaire)
Corollaire 5.3.11. Un chaîne de Markov irréductible sur un ensemble d’états X fini est né-
cessairement récurrente.
mn (y) = min Pn ( x, y)
x ∈X
Mn (y) = max Pn ( x, y)
x ∈X
On a alors
et
Mn+1 (y) = max Pn+1 ( x, y) = max
x ∈X x ∈X z ∈X
∑ P(x, z) Pn (z, y) ≤ Mn (y).
Par conséquent, les suites (mn (y)) et ( Mn (y)) sont adjacentes
∑ P N ( x, y) = ∑ P N ( x 0 , y) = 1.
y ∈X y ∈X
0 = ∑ P N ( x, y) − ∑ P N ( x0 , y)
y ∈X y ∈X
+ −
= ∑ [ P N (x, y) − P N (x0 , y)] + ∑ [ P N (x, y) − P N (x0 , y)]
y ∈X y ∈X
+
où ∑ signifie la somme sur ceux des y ∈ X pour lesquels [ P N ( x, y) − P N ( x 0 , y)] ≥ 0 et
−
pareillement pour ∑. La condition d’irréductibilité renforcée implique qu’il existe un
/Users/dp/a/ens/[Link] 49
2019-11-03 • 18:29:09.
5.4. Probabilité limite, probabilité invariante (stationnaire) Chaînes de Markov
+
réel 0 ≤ d < 1 tel que maxx,x0 ∑ [ P N ( x, y) − P N ( x 0 , y)] = d. On estime maintenant la
y ∈X
différence
Par conséquent, MkN +n (y) − mkN +n (y) ≤ dk , pour k ∈ N arbitraire ; en combinant avec
la propriété d’adjacence pour les suites (mn (y)) et ( Mn (y)), nous concluons qu’elles
convergent vers la même limite π (y) := limn→∞ mn (y) = limn→∞ Mn (y), car d < 1.
Par ailleurs, maxx∈X | Pn ( x, y) − π (y)| ≤ Mn (y) − π (y) ≤ d[n/N ]−1 . L’inégalité est alors
prouvée pour avec C = 1d et D = − lnNd .
Corollaire 5.4.2. Le vecteur (ligne) de probabilité π est un vecteur propre gauche, associé à la
valeur propre 1, de la matrice P.
Démonstration. De l’égalité Pn+1 ( x, y) = ∑z∈X Pn ( x, z) P(z, y), en passant à la limite
n → ∞, nous obtenons π (y) = ∑z∈X π (z) P(z, y).
Définition 5.4.3. La probabilité π (y) = limn→∞ Px ( Xn = y) est appelée probabilité li-
mite. Le vecteur propre gauche de P associé à la valeur propre 1 est appelé probabilité
invariante (ou stationnaire).
On dispose d’une formulation (voir le théorème 5.4.5 ci-dessous) plus complète du
théorème de convergence qui permet de s’affranchir de la l’hypothèse d’irréductibilité
forte.
Définition 5.4.4. Soit x ∈ X un état vérifiant Px (τx < ∞) > 0. On appelle période de
x la quantité
d x = pgcd{n ≥ 1 : Px ( Xn = x ) > 0}.
Lorsque d x = 1, l’état est appelé apériodique.
On peut facilement montrer que la période de x est une propriété de classe, i.e. tous
les états de la classe [ x ] ont la même période.
En tant que matrice, P agit sur l’espace vectoriel CX . Le spectre de la matrice P est
défini comme l’ensemble
/Users/dp/a/ens/[Link] 50
2019-11-03 • 18:29:09.
Chaînes de Markov 5.5. Stationnarité, réversibilité
Puisque la matrice P est stochastique, toutes les valeurs spectrales ont un module
|λ| ≤ 1 ; en outre on a toujours 1 ∈ spec( P). L’ensemble spec( P) \ {1} est appelé spectre
périphérique de P tandis que l’ensemble {λ ∈ spec( P) : |λ| < 1} est le spectre contrac-
tant. Notons que les spectres périphérique ou contractan peuvent être vides.
Soit P une matrice irréductible et d la période d’un état (donc de tous les états) de la
chaîne. La partie du spectre non-contractant (i.e. le spectre périphérique et le singleton
{1}) est égal aux racines d-èmes de l’unité. Par conséquent, le spectre périphérique est
vide si, et seulement si, la chaîne est apériodique.
Théorème 5.4.5. Soit P la matrice de transitions d’une chaîne sur un espace d’états X fini.
On note Eλ le projecteur sur l’espace D λ ( P) = ∪k≥1 ker( P − λI )k .
1. Il existe une constante K1 > 0 telle que pour grand n,
1 n −1 k K
k ∑
n k =0
P − E1 k ≤ 1 .
n
−1
En outre pour toute probabilité initiale ρ (vue comme vecteur ligne), on a k n1 ∑nk= k
0 ρP −
ρE1 k ≤ Kn1 .
2. Si le spectre périphérique est vide (i.e. la chaîne est apériodique), il existe une constante
K2 > 0 et un paramètre r ∈]0, 1[ tels que
k Pn − E1 k ≤ K2 r n .
3. Si la valeur propre 1 est simple (i.e. dim D λ ( P) = 1), le projecteur E1 définit une
unique probabilité invariante π par E1 f = π ( f )1, pour tout f : X → C (mesurable)
bornée.
La démonstration de ce résultat est simple mais longue car elle nécessite une longue
série de lemmes préliminaires ; elle peut être consultée dans [47].
Un autre résultat important est le
Théorème 5.4.6. Soit P la matrice stochastique irréductible d’une chaîne de Markov sur un
espace d’état dénombrable. On a équivalence entre les affirmations suivantes :
1. tout état est récurrent positif,
2. il existe un état récurrent positif,
3. la matrice P possède une probabilité invariante π.
En outre, si 3. est vérifié, alors Ex (τx ) = 1
π (x)
.
/Users/dp/a/ens/[Link] 51
2019-11-03 • 18:29:09.
5.5. Stationnarité, réversibilité Chaînes de Markov
— stationnaire si la loi conjointe de ( XT +t1 , . . . , XT +tn ) est la même pour tous les
T ∈ Z;
— réversible si la loi conjointe de ( Xt1 , . . . , Xtn ) est la même que la loi de ( XT −t1 , . . . , XT −tn ),
pour tout T ∈ Z ;
— markovien si
P ( X t n = x n | X t 1 = x 1 , . . . , X t n −1 = x n −1 ) = P ( X t n = x n | X t n −1 = x n −1 ) .
alors Q est stochastique et irréductible et admet π comme probabilité invariante (i.e. πQ = π).
En outre, elle est la matrice des transitions de la chaîne (Yn ).
Démonstration. — La matrice Q est stochastique car
1 π (y)
∑ Qyx =
π (y) ∑ π ( x ) Pxy =
π (y)
= 1.
x ∈X x ∈X
P(Y0 = y0 , . . . , YN = y N ) = P( X N = y0 , . . . , X0 = y N )
= π (y N ) Py N y N −1 · · · Py1 y0
= π ( y 0 ) Q y 0 y 1 · · · Q y N −1 y N .
/Users/dp/a/ens/[Link] 52
2019-11-03 • 18:29:09.
Chaînes de Markov 5.5. Stationnarité, réversibilité
π (y L )
Q y 0 y 1 · · · Q y L −1 y L = Px x · · · Px1 x0 > 0,
π ( y 0 ) L L −1
ce qui garantit l’irréductibilité de Q.
Théorème 5.5.5. Une chaîne de Markov stationnaire et irréductible est réversible si, et seule-
ment si, la chaîne vérifie la condition de bilan détaillé, i.e. s’il existe un vecteur de probabilité
π := (π ( x )) x∈X tel que
π ( x ) P( x, y) = π (y) P(y, x ), ∀ x, y ∈ X.
π ( x ) P( x, y) = π (y) P(y, x ), ∀ x, y ∈ X.
P ( X t = x 0 , X t +1 = x 1 , . . . , X t + n = x n ) = π ( x 0 ) P ( x 0 , x 1 ) · · · P ( x n −1 , x n ),
P ( X t = x n , X t +1 = x n −1 , . . . , X t + n = x 0 ) = π ( x n ) P ( x n , x n −1 ) · · · P ( x 1 , x 0 ).
Mais la condition de bilan détaillé entraîne que les seconds membres de ces égalités
sont identiques. On conclut alors la réversibilité du processus.
Exemple 5.5.6 (Modèle d’urne de Paul et Tatiana Ehrenfest [19]). Supposons que N
boules discernables (par exemple étiquetées) sont distribuées dans deux urnes no-
tées respectivement urne 0 et urne 1. À chaque instant entier, une étiquette est choi-
sie au hasard et la boule correspondante est transférée dans l’autre urne avec proba-
bilité p ∈]0, 1[ ou laissée sur place avec probabilité 1 − p. On note Xn le nombre de
boules dans l’urne 0 à l’instant n. La suite ( Xn )n∈Z constitue une chaîne de Markov sur
X = {0, . . . , N } qui évolue selon la matrice stochastique
x
pN si x ∈ {1, . . . , N } et y = x − 1,
si x ∈ X et y = x,
1 − p
P( x, y) = x
p(1 − N ) si x ∈ {0, . . . , N − 1} et y = x + 1,
0 sinon.
Cette chaîne est fortement irréductible. Par le théorème ergodique pour les chaînes
de Markov , on conclut que la probabilité limite π (y) = limn→∞ Px ( Xn = y) =
limn→∞ Pn ( x, y) existe et est indépendante de x ; elle est l’unique mesure invariante
Cx
de la chaîne. Par ailleurs, on montre facilement que la probabilité µ( x ) = 2NN , x ∈ X,
vérifie la condition de bilan détaillé ; la chaîne est donc réversible et π = µ. Puisque
µ est la probabilité d’équilibre, après un temps suffisamment long, la probabilité pour
/Users/dp/a/ens/[Link] 53
2019-11-03 • 18:29:09.
5.6. Théorème des grands nombres pour les chaînes de Markov Chaînes de Markov
qu’une boule soit dans l’une ou l’autre urne est 1/2. D’un autre côté, la réversibilité de
la chaîne signifie que (pour T grand)
Pµ ( X0 = N, XT = N/2) = Pµ ( X0 = N/2, XT = N ),
résultat qui peut paraître contre-intuitif de prime abord. (Nous retournerons sur ce
résultat au paragraphe 7.6).
(r ) (r −1)
τx = inf{n > τx : Xn = x }, pour r ≥ 1.
Lemme 5.6.1. Avec les notations et hypothèses précédentes, on introduit la suite ( Zr )r≥1 par
τ r +1
∑
f
Zr := Zr = f ( Xk ), r ≥ 1.
k = τ r +1
Démonstration. La propriété forte de Markov garantit que la loi conjointe du futur strict
à partir de τ r conditionnellement au passé jusqu’au temps τ r est égale à la loi conjointe
du futur strict de τ r conditionnellement au présent. Or à l’instant τ r , la chaîne vaut
Xτr = x. Par conséquent : la loi conjointe de ( Xτr +1 , Xτr +2 , . . .) conditionnellement au
passé est égale à la loi conjointe de ( X1 , X2 , . . .) conditionnellment à X0 = x. On a alors,
pour tout r ≥ 1,
Théorème 5.6.2. Soient ( Xn )n∈N une CM(X, P, ·), x ∈ X un point récurrent positif et
f : X → R telle que
Ex (| f ( X1 )| + . . . + | f ( Xτx1 |) < ∞.
/Users/dp/a/ens/[Link] 54
2019-11-03 • 18:29:09.
Chaînes de Markov 5.6. Théorème des grands nombres pour les chaînes de Markov
Alors
1 n Ex ( f ( X1 ) + . . . + f ( Xτx1 )
∑
n k =0
f ( Xk ) =
Ex τx1
, Px − p.s.
/Users/dp/a/ens/[Link] 55
2019-11-03 • 18:29:09.
5.7. Exemples d’applications algorithmiques Chaînes de Markov
/Users/dp/a/ens/[Link] 56
2019-11-03 • 18:29:09.
Chaînes de Markov 5.7. Exemples d’applications algorithmiques
= Q xx + ∑ (1 − A xz ) Q xz + ∑ A xy Q xy
z∈Ax \{ x } y∈Ax \{ x }
= ∑ Q xz = 1.
z ∈A x
/Users/dp/a/ens/[Link] 57
2019-11-03 • 18:29:09.
5.8. Exercices Chaînes de Markov
A xy π (y) Qyx
= , ∀ x ∈ X, ∀y ∈ Ax \ { x }
Ayx π ( x ) Q xy
π ( x ) Pxy = π ( x ) Q xy A xy
Ayx
= π (y) Qyx A xy
A xy
= π (y) Pyx .
F (z)
Corollaire 5.7.5. Soit F : [0, ∞] → [0, 1] une application telle que F(1/z) = z pour tout
z ∈ [0, ∞]. Si
π (y) Qyx
A xy = F , ∀ x ∈ X, ∀y ∈ Ax \ { x },
π ( x ) Q xy
alors P vérifie la condition de bilan détaillé.
z
Exemple 5.7.6. Les fonctions données par les formules F (z) = 1+ z et F (z) = min(1, z)
vérifient les hypothèses du lemme.
5.8 Exercices
Chaînes de Markov ; matrices stochastiques
60. Soient X = {0, 1, . . . , m} un ensemble fini d’états et une suite indépendante
(Un )n≥1 , identiquement distribuée selon la loi uniforme sur {1, . . . , m}. On in-
troduit la suite ( Xn )n≥0 de variables aléatoires, définies par X0 = 0 et Xn+1 =
max( Xn , Un+1 ), pour n ≥ 0.
(a) Montrer que ( Xn ) est une chaîne de Markov et déterminer sa matrice de
transition P.
(b) Esquisser le graphe de la matrice stochastique lorsque m est petit.
(c) En utilisant des arguments d’estimation directe, indiquer quels états sont
récurrents et quels sont transients.
(d) Pour m = 4, calculer P2 .
/Users/dp/a/ens/[Link]
58
2019-11-02 • 14:22:01.
Chaînes de Markov 5.8. Exercices
(a) Soit p := ( p x ) x≥1 la suite définie par p x = (e−11) x! . Montrer que p est un
vecteur de probabilité sur X.
(b) Montrer que le vecteur de probabilité p est invariant pour P, i.e. le vecteur
ligne p est vecteur propre gauche de P associé à la valeur propre 1). Clin
x 1
d’œil : x+ 1 = 1 − x +1 .
(c) Déterminer la décomposition de X en classes de communication.
63. (Extrait de l’examen du 7 mai 2013).
Soit β ∈]0, 1[. On considère la matrice
1−β β
P := .
β 1−β
(a) On note spec( P) l’ensemble des valeurs propres de P. Vérifier que spec( P) =
{1, 1 − 2β}.
1 −1
(b) Vérifier que les vecteurs D1 = et D1−2β = sont des vecteurs
1 1
propres droits associés aux valeurs propres correspondantes.
/Users/dp/a/ens/[Link]
59
2019-11-02 • 14:22:01.
5.8. Exercices Chaînes de Markov
Dλ Dλ
(c) Pour chaque λ ∈ spec( P), on note dλ = kDλ ksup
et δλ = k D λ k1
, où, pour tout
z ∈ R2 , on note kzk1 = |z1 | + |z2 | et kzksup = max{|z1 |, |z2 |}. Déterminer
0
λ, λ ∈ spec
dλ et δλ , pour (P).
a1 b1 t a1 b1 a1 b2
(d) Pour a = et b = vecteurs arbitraires, on note a ⊗ b = .
a2 b2 a2 b1 a2 b2
Vérifier que P = ∑λ∈spec( P) λEλ , où Eλ = dλ ⊗ δtλ .
(e) Montrer que Eλ Eλ0 = δλ,λ0 Eλ .
(f) En déduire que pour un n ≥ 1 arbitraire,
n pn 1 − pn
P = .
1 − pn pn
(g) On déterminera explicitement pn . Quelle est la valeur de limn→∞ pn ?
(h) On note ( Xn ) la chaîne de Markov sur un espace X à deux états, dont la
matrice de transition est P et la probabilité initiale ρ0 . Déterminer π (y) :=
limn→∞ Pρ0 ( Xn = y), pour y ∈ X.
(i) Montrer que π est une probabilité invariante.
muni de la probabilité uniforme. Ces ensembles, pour N ' 104 , modélisent bien
certains polymères tels que le poly-chloro-éthylène, mais la contrainte géomé-
trique forte de non-recoupement ne nous permet même pas d’estimer le cardinal
de Xmsr
x,N dès que N prenne de valeurs modérément grandes.
On note Gd le sous-groupe discret de transformations orthogonales de Rd qui
laisse Zd invariant. Par exemple, en dimension d = 2, le sous-groupe Gd devient
π
G2 = {e, ± , réflexions/axes Ox, Oy, réflexions/diagonales D1 , D2 }.
2
Soit ρ une probabilité sur Gd telle que
/Users/dp/a/ens/[Link]
60
2019-11-02 • 14:22:01.
Chaînes de Markov 5.8. Exercices
— ρ(e) = 0,
— ρ( g) = ρ( g−1 ), ∀ g ∈ Gd ,
— si g est un générateur de Gd , alors ρ( g) > 0.
Pour k ∈ {1, . . . , N } et g ∈ Gd on introduit la transformation (k, g) : Xmsr
x,N →
Xx,N par
msr
(k, g)y = y0 := (y0 , . . . , yk−1 , yk−1 + g(yk − yk−1 ), . . . , yk−1 + g(y N − yk−1 ), ∀y ∈ Xmsr
x,N .
(a) Montrer que l’algorithme ci-dessus définit une matrice stochastique P sur
Xmsr avec
(
ρ( g)
si z = (k, g)y
P(y, z) = 1N
N ∑k,g ρ ( g )1Xmas \Xmsr (( k, g ) y ) sinon.
/Users/dp/a/ens/[Link] 61
2019-11-03 • 18:29:09.
5.8. Exercices Chaînes de Markov
20
15
10
5
y
−5
−10
−15
−20
Figure 5.1 – Exemple de trajectoire d’une marche sans recoupement sur Z2 partant de l’origine et
de longueur 437.
/Users/dp/a/ens/[Link] 62
2019-11-03 • 18:29:09.
Notions de statistique
6
6.1 Motivation
L’objet de la théorie des probabilités peut se formuler succinctement comme l’étude
de variables aléatoires définies sur un espace abstrait de probabilités (Ω, F , P) et qui
prennent des valeurs dans un espace d’événements (X, X ). Les questions que nous
avons abordées aux chapitres précédents, concernent
— la loi PX sur (X, X ), image de P par X,
— certaines fonctionnelles définies sur l’espace de variables aléatoires à valeurs
dans X, comme l’espérance, la variance,
— le comportement asymptotique des suites de variables aléatoires ( Xn )n∈N , lorsque
celles-ci sont indépendantes ou ont des dépendances moins triviales, des dépen-
dances markoviennes par exemple, etc.
En résumant, la théorie des probabilités permet de répondre à la question suivante :
étant donné un certain procédé de génération de X, que peut-on dire à propos des
observations qui en découlent. Par exemple, quelle est la valeur de P( X = x ) lorsque
x ∈ X, ou quel est le comportement de ∑nk=1 f ( Xk ) à grand n, lorsque f a « des bonnes
propriétés » et ( Xk )k∈N est une suite indépendante ou une suite markovienne, sont des
questions étudiées par la théorie des probabilités.
En statistique mathématique, nous intéressons encore moins à l’espace (Ω, F , P)
qu’en théorie des probabilités. Nous avons un espace d’événements (X, X ) et une fa-
mille spécifique Π ⊂ M1 (X, X ) de probabilités, avec |Π| ≥ 2 pour éviter les trivialités.
Nous disposons d’une variable aléatoire X à valeurs dans X dont la loi est un élément
de l’ensemble Π mais nous ignorons lequel. Nous observons plusieurs réalisations (ob-
servations) de la variable aléatoire X et nous voulons, à partir des observations inférer 1
la loi qui a servi à générer les réalisations de X.
Exemple 6.1.1. On note (X, X , Π) le triplet qui permet de poser le problème d’infé-
rence.
1. INFÉRER, verbe trans. A–(log.) Tirer, d’un fait ou d’une proposition donné(e), la conséquence qui en
résulte. B–(p. ext.) Tirer une conclusion d’un fait ou d’un événement donnés. Trésor de la langue française,
version en ligne (2019).
63
6.1. Motivation Notions de statistique
Ici, la famille Π = (Pθ )θ ∈Θ , avec Θ = [0, 1], et on veut, à partir d’un échantillon
X1 , . . . , Xn inférer la valeur de θ. On peut aussi identifier Pθ avec la densité dis-
crète (par rapport à la mesure de dénombrement) f θ qui vaut
f θ ( x ) = θ x (1 − θ )1− x , x ∈ X, θ ∈ Θ.
( x − m )2
1
Z
Pθ ( B ) = f θ ( x )dx, avec f θ ( x ) = √ exp − , x ∈ R.
B 2πs s2
Dans les deux premiers cas, la famille Π est isomoprhe à un (sous)-espace de Rd pour
un d < ∞. Dans le dernier cas, Π est isomorphe à un espace fonctionnel de dimension
infinie. Dans tous les cas, on peut idenitifier les probabilités qui composent Π avec leur
densité par rapport à une mesure de référence.
Définition 6.1.2. Un modèle statistique est la donnée (X, X , Π), où la famille des
probabilités (ou de leurs densités par rapport à une mesure de référence) Π ⊂ M1 (X )
est appelée population. Lorsque Π est isomorphe à un ensemble de paramètres Θ
d’un espace de dimension finie, on parle de modèle statistique paramétrique, sinon
de modèle statistique non paramétrique.
/Users/dp/a/ens/[Link] 64
2019-12-04 • 14:36:03.
Notions de statistique 6.2. Estimation paramétrique
θ̂n − θ loi
√ −→ N (0, 1).
n
Au delà de l’estimateur de la moyenne empirique, d’autres estimateurs sont cou-
ramment utilisés, comme celui du maximum de vraisemblance.
/Users/dp/a/ens/[Link] 65
2019-12-04 • 14:36:03.
6.2. Estimation paramétrique Notions de statistique
Définition 6.2.9. Une variable aléatoire Z à valeurs dans R≥ dont la loi a comme
densité P( Z ∈ dz) = f k (z)dz, avec
k z
z 2 −1 e 2
f k (z) = k
,
2 2 Γ( 2k )
est dite suivre la loi de χ2k avec k degrés de liberté. La fonction de répartition de cette
loi est
γ(k/2, z/2)
Fk (z) = ,
Γ(k/2)
où γ est la loi gamma incomplète (elle est tabulée).
/Users/dp/a/ens/[Link] 66
2019-12-04 • 14:36:03.
Notions de statistique 6.2. Estimation paramétrique
Exemple 6.2.13. Lors d’une expérience, les valeurs suivantes ont été obtenues lors de 8
réalisations indépendantes d’une variable aléatoire X : 4.4, 4.7, 4.8, 4.5, 4.4, 4.2, 4.2, 4.0.
La moyenne empirique est θ 8 = 4.4 et la variance empirique V = 0.0714. On cherche à
determiner un intervalle de confiance à seuil d’erreur α = 0.1 pour la variance σ2 de la
loi qui a servi pour générer l’échantillon. On sait que 7V/σ2 suit la loi de χ27 . À partir
des tables, on détermine les valeurs z− (α) et z+ (α) telles que la variable Z suivant la
loi de χ27 , vérifie
P( Z ≤ z− (α)) = P( Z ≥ z+ (α)) = α/2.
Par conséquent, l’intervalle de confiance à niveau d’erreur α sera C = [ z 7V , 7V ] et
(α) z (α) + −
on aura que P(σ2 ∈ C ) = 1 − α. Pour α = 0.1, on détermine à partir des tables de F7 que
z− (α) = 2.17 et z+ (α) = 14.1, ce qui conduit à l’estimation P(0.19 ≤ σ ≤ 0.48) = 0.9.
/Users/dp/a/ens/[Link] 67
2019-12-04 • 14:36:03.
6.2. Estimation paramétrique Notions de statistique
mais ce problème est mal posé car il n’y a pas de moyen objectif de déterminer la pro-
babilité notée « P » ci-dessus. Cependant, même si « P » est une quantité subjective, on
exige que « P »( H0 prévaut) + « P »( H1 prévaut) = 1, par conséquent, γ ≤ max(α, β).
La théorie des tests d’hypothèses consiste donc à construire des régions critiques de
taille α fixée qui minimisent β. Le théorème de Neyman-Pearson 6.2.15 nous donne
une méthode de construction explicite de la région d’acceptation de l’hypothèse H1 .
Pour Pθ , θ ∈ Θ ' {0, 1}, on note pθ le vecteur de probabilité correspondant et pour
un n-uplet x = ( x1 , . . . , xn ), on définit la fonction de vraisemblance
L θ ( x ) : = p θ ( x1 ) · · · p θ ( x n ).
On remarque que l’erreur de type I correspondant à une région critique de rejet R est
Z Z
n
α( R) = P0 (( X1 , . . . , Xn ) ∈ R) = p0 ( x1 ) · · · p0 ( x n )d x = L0 (x)dx,
R R
En décomposant
R = ( R ∩ S ) t ( R ∩ S c ),
S = ( S ∩ R ) t ( S ∩ R c ),
nous avons
Z Z Z Z
L0 (x)dx + L0 (x)dx = L0 (x)dx + L0 (x)dx
R∩S R∩Sc R∩S S∩ Rc
ou Z Z
L0 (x)dx = L0 (x)dx.
R∩Sc S∩ Rc
/Users/dp/a/ens/[Link] 68
2019-12-04 • 14:36:03.
Notions de statistique 6.3. Estimation non paramétrique
L0 L0
Par ailleurs, sur R, nous avons L1 ≥ δ tandis que sur Rc , nous avons L1 < δ . On
conclut que
L0 ( x ) L0 ( x )
Z Z Z Z
L1 (x)dx ≥ dx = dx ≥ L1 (x)dx.
R∩Sc R∩Sc δ S∩ Rc δ S∩ Rc
6.4 Exercices
/Users/dp/a/ens/[Link] 69
2019-12-04 • 14:36:03.
6.4. Exercices Notions de statistique
/Users/dp/a/ens/[Link] 70
2019-10-18 • 18:08:44.
Deuxième partie
Théorie de l’information
71
Quantification de l’information
7
Dans le chapitre 1 nous avons présenté les arguments qui nous amènent à mesurer
la quantité d’information en bits. Dans ce chapitre, nous allons formaliser précisément
les propriétés que doit avoir la quantité d’information, démontrer que la seule fonc-
tion qui possède ces propriétés est la fonction introduite en chapitre 1 et donner trois
interprétations différentes de cette notion.
Une fois la notion d’information clarifiée, nous introduirons la notion de registre
de stockage et de ses états (informationnels) comme une abstraction mathématique
d’un dispositif physique dans lequel l’information puisse être stockée et nous allons
décrire son état informationnel comme une représentation abstraite de son contenu à
un instant particulier.
73
7.1. Postulats d’une quantité d’incertitude, entropie Quantification de l’information
La fonction H : l’espérance de h.
La fonction h pouvant varier beaucoup avec p, il est plus raisonnable d’associer
à l’incertitude d’une variable aléatoire X dont la loi est décrite par le vecteur
p = ( p( x )) x∈X la quantité H (p) = ∑ x∈X p( x )h( p( x )) qui représente l’incerti-
tude moyenne de l’observation. Les variables aléatoires étant en bijection avec
les vecteurs de probabilités qui décrivent leurs lois, nous pouvons identifier la
quantité H (p) avec H ( X ) et nous pouvons (provisoirement) noter H M ( X ) où
H M (p) cette espérance lorsque |X| = M.
Supposons que la variable aléatoire X soit uniformément distribuée dans X, i.e.
p( x ) = M 1
, pour tout x = X, où |X| = M, et notons f ( M) = H M (( M 1 1
,..., M )) la
valeur correspondant de l’incertitude moyenne associée. L’incertitude inhérente à une
expérience consistant à choisir entre les valeurs prise par une pièce honnête est plus
petite que l’incertitude consistant à choisir une personne au hasard dans la population
française, i.e. f (2) < f (6 × 107 ). Il est donc intuitivement clair d’exiger comme premier
postulat :
Postulat 7.1.1 (Postulat de monotonie). La fonction f : N → R+ définie par f ( M) :=
1 1
H M (( M ,..., M )) est une fonction strictement croissante de son argument.
Considérons maintenant deux variables aléatoires indépendantes X et Y définies
sur le même espace de probabilité (Ω, F , P) uniformément distribuées respectivement
dans X et Y, avec |X| = L et |Y| = M. L’expérience composite fait intervenir la variable
aléatoire ( X, Y ) à valeurs dans X × Y, dont le cardinal est L × M. Si la valeur prise par
X nous est révélée, l’incertitude de Y n’est pas affectée car Y est indépendante de X.
Cependant, l’incertitude totale f ( LM) est réduite de l’incertitude f ( L) relative à X.
Ceci nous amène donc au deuxième
Postulat 7.1.2 (Postulat d’extensivité). Pour tout L, M ≥ 1, nous avons f ( LM) = f ( L) +
f ( M ).
Nous allons maintenant relaxer la condition de distribution uniforme. Supposons
que p est un vecteur de probabilité arbitraire sur X (de cardinal |X| = M) et que
X prend des valeurs dans X avec probabilité P( X = x ) = p( x ). Considérons une
partition X = X1 t X2 et notons qi = ∑ x∈Xi p( x ), avec |Xi | = Mi , i = 1, 2.
Nous allons considérer l’expérience effectuée en deux étapes : lors de la première
étape, nous nous intéressons à l’événement X ∈ Xi , avec P( X ∈ Xi ) = qi , i = 1, 2
et lors de la deuxième étape nous examinons si la variable aléatoire prend une valeur
précise sachant qu’elle est dans l’un ou l’autre des groupes X1 ou X2 . Plus précisément,
nous calculons
P( X = x ) = P( X = x | X ∈ X1 )P( X ∈ X1 ) + P( X = x | X ∈ X2 )P( X ∈ X2 )
p( x ) p( x )
= q1 1X1 ( x ) + q2 1X2 ( x )
q1 q2
= p ( x ).
Nous formulons alors le troisième postulat de la quantité d’incertitude
/Users/dp/a/ens/[Link] 74
2019-11-03 • 18:19:27.
Quantification de l’information 7.1. Postulats d’une quantité d’incertitude, entropie
Postulat 7.1.3 (Postulat de regroupement). Avec les mêmes notations que ci-dessus,
pX1 pX2
H M (p) = q1 H M1 + q2 HM2 + H2 ((q1 , q2 )).
q1 q2
Finalement, nous introduisons le
Postulat 7.1.4 (Postulat de continuité). La fonction H2 ( p, 1 − p) est continue en p ∈ [0, 1].
Théorème 7.1.5. L’unique fonction (à une constante multiplicative près) qui vérifie les pos-
tulats de monotonie, d’extensivité, de regroupement et de continuité est la fonction
PV M 3 p 7→ H M (p) = −C ∑ p( x ) log p( x ),
x ∈X
f ( M k ) = f ( M · M k −1 ) = f ( M ) + f ( M k −1 ),
Par ailleurs f (1) = 0 tandis que f est strictement croissante, donc f (2) > 0 ; par
conséquent C > 0.
/Users/dp/a/ens/[Link] 75
2019-11-03 • 18:19:27.
7.1. Postulats d’une quantité d’incertitude, entropie Quantification de l’information
4. Nous utilisons maintenant le postulat de continuité pour établir que pour tout
p ∈]0, 1[, nous avons H (( p, 1 − p)) = −C [ p log p + (1 − p) log(1 − p)]. Ceci est
une conséquence immédiate du fait que tout réel p ∈]0, 1[ peut être approximé
par une suite ( pn )n de rationnels pn ∈]0, 1[ pour tout n ∈ N.
5. Il reste à établir la formule pour H M dans le cas général p = ( p1 , . . . , p M ). La
formule H M (p) = −C ∑iM =1 pi log pi est vraie pour M = 1 et M = 2. Pour M >
2, nous supposons la formule vraie jusqu’à l’ordre M − 1 et nous utilisons le
postulat de regroupement pour l’établir dans le cas M. En effet, en notant q =
p1 + . . . + p M−1 et en utilisant le postulat de regroupement, nous obtenons
p p M1
H M (p) = H2 ((q, p M )) + qH M−1 (( 1 , . . . , )) + p M H1 ((1))
q q
" #
M −1
pi pi
= −C q log q + p M log(1 − p M ) + q ∑ log
i =1
q q
M
= −C ∑ pi log pi .
i =1
Remarque 7.1.6. Sauf indication contraire, nous utiliserons des logarithmes en base
2 et la constante de normalisation C = 1. La fonction H mesure alors la réduction de
l’incertitude lorsque la valeur du tirage d’une pièce honnête nous est révélée en une
unité appelée bit. D’autres choix sont possibles, par exemple exprimer le logarithme
en base e et poser C = 1 ; l’unité correspondante est alors appelée nat. En Physique, on
utilise la constante C = 1.3806488 × 10−23 J/K — appelée constante de Boltzmann — et
on exprime le logarithme en base e ; l’unité de H est alors exprimée en J/K (Joules par
degré Kelvin) et la quantité H est alors appelée entropie. Dans la suite de ce cours, log
représentera le logarithme binaire ; nous utiliserons la notation ln pour le logarithme
neperien.
Remarque 7.1.7. L’incertitude associée à l’ignorance des valeurs d’une variable aléa-
toire X avant que l’expérience soit effectuée et la réalisation nous soit relevée, ne dé-
pend pas des valeurs possibles de X mais uniquement des probabilités avec lesquelles
/Users/dp/a/ens/[Link] 76
2019-11-03 • 18:19:27.
Quantification de l’information 7.1. Postulats d’une quantité d’incertitude, entropie
0.8
H2 ( p, 1 − p)
0.6
0.4
0.2
0
0 0.2 0.4 0.6 0.8 1
p
Figure 7.1 – La fonction H joue un rôle capital dans toute la suite de ce cours. Il est donc utile de
garder à l’esprit le comportement qualitatif de H2 ( p, 1 − p) en fonction de p ∈ [0, 1].
ces variables sont prises. Si par exemple X ∈ X = {−1, 1} correspond à une expé-
rience dans laquelle vous perdez un euro si la pièce honnête tombe sur « pile » ou
bien X ∈ Y = {exécution, libération} correspond à l’expérience où un prisonnier est
exécuté si la pièce honnête tombe sur « pile », les deux expériences ont exactement la
même incertitude même si les conséquences sont autrement graves pour le perdant.
Nous écrirons dans la suite indifféremment H ( X ) ou H (p) pour signifier l’entropie
associée à la variable aléatoire X ou à sa loi.
Remarque 7.1.8. Dans ce qui précède, nous avons indiqué H M pour signifier l’entropie
pour une variable aléatoire prenant M valeurs distinctes. Dans la suite nous omettrons
cette dépendance et nous considérerons la fonction H définie sur PV = ∪∞ M=1 PV M où
M
M
PV M = {p := ( p1 , . . . , p M ) ∈ R+ : ∑ p i = 1}.
i =1
En fait, H est une collection dénombrable de fonctions ( H M ) M≥1 . Lorsque nous ap-
pliquons H sur un vecteur de probabilité p ∈ PV, en réalité nous appliquons H M sur
p ∈ PV M pour un certain M. Le résultat est alors calculé par application de la fonction
H M . Finalement, nous simplifierons la notation pour écrire H ( p1 , . . . , p M ) au lieu de
H M (( p1 , . . . , p M )).
/Users/dp/a/ens/[Link] 77
2019-11-03 • 18:19:27.
7.2. Trois interprétations de l’entropie Quantification de l’information
/Users/dp/a/ens/[Link] 78
2019-11-03 • 18:19:27.
Quantification de l’information 7.2. Trois interprétations de l’entropie
,
[Gleich. 35j J;
6. Math. Bedeutung der Grösse H. 41
Z= / «\ , / w \ , u. s. w.
2/ \2
Da nun die Anzahl der Moleküle eine überaus grosse ist,
so sind n^oo, n^w u. s. w. ebenfalls als sehr grosse Zahlen zu
betrachten.
Wir wollen die Annäherungsformel:
p\ = ]/2p;r(
P Y
e
so ergibt sich:
l Z= — (ji[n-^ln^ + n^ln^" .) +C
wobei
C= l{n\)-n{l(ü- l)-4(^w -\-l27i)
Figure 7.2 – Facsimilé de la page 41 du livre de Boltzmann Vorlesungen über Gastheorie [7], où
une définition mathématique de la fonction entropie, identique à la définition 7.1.9, est donnée pour
la première fois. La formule correspondante est encadrée en rouge dans le texte original de Boltzmann
qui est reproduit dans la figure ci-dessus (le logarithme népérien est noté l). Ce livre a été traduit en
français [8].
/Users/dp/a/ens/[Link] 79
2019-11-03 • 18:19:27.
7.2. Trois interprétations de l’entropie Quantification de l’information
/Users/dp/a/ens/[Link] 80
2019-11-03 • 18:19:27.
Quantification de l’information 7.2. Trois interprétations de l’entropie
non (0.5) = x3 ?
X = x4 [3, 0.5 · 0.6 · 0.5]
Figure 7.3 – Le diagramme logique permettant de déterminer la valeur de X. Les étiquettes entre
parenthèse sur les arrêtes du diagramme désignent les probabilités conditionnelles de l’arbre de déci-
sions sachant à quel embranchement on se trouve. Par exemple, l’étiquette en vert sur le diagramme
ci-dessus, correspond à la probabilité conditionnelle P( X 6= x3 | X 6∈ { x1 , x2 }). Les étiquettes de la
forme [N, p] entre crochets désignent les nombres de questions posées N et la probabilité de la feuille
de l’arbre p.
/Users/dp/a/ens/[Link] 81
2019-11-03 • 18:19:27.
7.2. Trois interprétations de l’entropie Quantification de l’information
X = x1 ?
Figure 7.4 – Le diagramme logique permettant de déterminer la valeur de X avec les mêmes
conventions de notation que pour la figure 7.3.
a ∈A
(n)
P νa (X(n) ) =l = Cnl pla (1 − p a )n−l , ∀ a ∈ A, l = 0, . . . , n.
Remarque 7.2.1. Il est nettement plus aisé de travailler avec des suites infinies α ∈
(n)
AN ou avec des suites aléatoires infinies X = ( X1 , X2 , . . .) et de définir νa (α) =
∑nk=1 1{a} (αk ) par la somme tronquée aux n premières lettres de la suite. De même,
nous pouvons utiliser la notation αn ou Xn pour signifier la troncature des suites aux
n premières lettres. On peut aussi remarquer que pour tout n ∈ N> et α ∈ AN , on a :
ν(n) (α) ∈ PVA .
(n)
Nous calculons aisément que E(νa (X)) = np a , pour tout a ∈ A. Il est donc intui-
tivement clair pourquoi nous définissons :
/Users/dp/a/ens/[Link] 82
2019-11-03 • 18:19:27.
Quantification de l’information 7.2. Trois interprétations de l’entropie
Remarque 7.2.3. Dans une suite α, typique pour un vecteur de probabilité p, nous
(n)
ν (α)
avons : | a n − p a | < √ K √1 = O( n−1/2 ), pour toute lettre a ∈ A. Il faut souli-
n
p a (1− p a )
gner que les suites typiques dépendent du vecteur de probabilité p mais ne sont pas elles-mêmes
aléatoires. Il s’agit tout simplement d’une famille de mots à n lettres sur l’alphabet A
dont les lettres apparaissent avec une densité pré-fixée (définie par p).
q
Théorème 7.2.4. Soient ε ∈]0, 1[ et K > cardA ε . Pour tout n ≥ K,
1. P(Xn 6∈ Tn,p,K ) < ε ;
2. ∃c > 0 tel que ∀α ∈ Tn,p,K , nous avons
√ √
2−nH (p)−c n
≤ P(Xn = α) ≤ 2−nH (p)+c n
;
toires ( Xi ) que
− log P(X = α) = − ∑ νa (α) log p a .
(n)
a ∈A
Or, pour α ∈ Tn,p,K , nous avons, pour tout a ∈ A,
q q
(n)
np a − K np a (1 − p a ) ≤ νa (α) ≤ np a + K np a (1 − p a ).
(n)
Remplaçant les encadrements de νa (α) obtenusp dans la dernière formule dans
la pénultième et en définissant c := −K ∑ a∈A p a (1 − p a ) log p a , nous concluons.
3. Par l’affirmation 1 du théorème, nous avons
1 − ε ≤ P(X ∈ Tn,p,K ) ≤ 1.
/Users/dp/a/ens/[Link] 83
2019-11-03 • 18:19:27.
7.3. Propriétés de la fonction entropie, entropie relative Quantification de l’information
√
permettant de minorer card(Tn,p,K ) ≥ 2nH (p)−c n+log(1−ε) . Par ailleurs,
√
card(Tn,p,K )2−nH (p)−c n
≤ ∑ P(X = α) ≤ 1,
α∈Tn,p,K
√
permettant de majorer card(Tn,p,K ) ≤ 2nH (p)+c n . En combinant les deux bornes
nous obtenons
0
2n( H (p)−δn ) ≤ card(Tn,p,K ) ≤ 2n( H (p)+δn ) ,
log(1−ε)
où, δn = √c
n
→ 0 et δn0 = √c
n
− n → 0.
Remarque 7.2.5. Le théorème précédent établit les faits importants suivants. L’affir-
mation 1, établit que si p n’est pas l’équidistribution sur A, parmi les√[card(A)]n suites
possibles une proportion exponentiellement petite (de cardinal 2nH (p)±c n ) supporte pra-
tiquement toute la masse de P. L’affirmation 2 établit que dans ce petit ensemble de
configurations typiques, toutes ont essentiellement la même probabilité, i.e. il y a équi-
distribution sur l’ensemble de configurations typiques.
− ∑ p a log p a ≤ − ∑ p a log q a .
a ∈A a ∈A
/Users/dp/a/ens/[Link] 84
2019-11-03 • 18:19:27.
Quantification de l’information 7.4. Entropie des évolutions markoviennes
/Users/dp/a/ens/[Link] 85
2019-11-03 • 18:19:27.
7.5. Couples de variables aléatoires Quantification de l’information
/Users/dp/a/ens/[Link] 86
2019-11-03 • 18:19:27.
Quantification de l’information 7.5. Couples de variables aléatoires
H ( X, Y ) ≤ H ( X ) + H (Y ),
avec égalité si, et seulement si, les variables aléatoires X et Y sont indépendantes.
H ( X, Y ) = − ∑ κ ( x, y) log κ ( x, y) ≤ − ∑ κ ( x, y) log q( x, y) = H ( X ) + H (Y ),
x ∈X,y∈Y x ∈X,y∈Y
H (Y | X ) = ∑ H (Y | X = x ) P ( X = x ) .
x ∈X
/Users/dp/a/ens/[Link] 87
2019-11-03 • 18:19:27.
7.5. Couples de variables aléatoires Quantification de l’information
H ( X, Y ) = H (Y | X ) + H ( X ) = H ( X |Y ) + H (Y ).
7.5.5 7.5.2
H ( X, Y ) = H (Y | X ) + H ( X ) ≤ H (Y ) + H ( X ),
I ( X : Y ) : = H ( X ) − H ( X |Y ) .
Remarque 7.5.8. Le théorème 7.5.6 garantit que I ( X : Y ) ≥ 0, avec égalité si, et seule-
ment si, les variables aléatoires X et Y sont indépendantes ; dans le cas d’indépendance,
l’observation de Y ne nous apprend rien sur X, par conséquent, si nous soustrayons
de l’incertitude de X l’incertitude conditionnelle, l’incertitude résiduelle est nulle. Par
ailleurs, des égalités
H ( X, Y ) = H (Y | X ) + H ( X ) = H ( X |Y ) + H (Y ),
I ( X : Y ) = H ( X ) − H ( X |Y )
= H ( X ) + H (Y ) − H ( X, Y )
= I (Y : X ) .
/Users/dp/a/ens/[Link] 88
2019-11-03 • 18:19:27.
Quantification de l’information 7.6. Registres de stockage de l’information
Exemple 7.6.1 (Un registre élémentaire). Supposons que nous disposons d’une urne à
deux compartiments — notés respectivement 0 et 1 — qui correspondent à l’alphabet
X = {0, 1}. La figure 7.5 illustre un tel registre.
— L’état informationnel du registre est une probabilité extrémale sur X. Notons
que
extr M1 (X) := {p0 = (1, 0), p1 = (0, 1)} ' X.
/Users/dp/a/ens/[Link] 89
2019-11-03 • 18:19:27.
7.6. Registres de stockage de l’information Quantification de l’information
+ +
/Users/dp/a/ens/[Link] 90
2019-11-03 • 18:19:27.
Quantification de l’information 7.6. Registres de stockage de l’information
+ +
∆E = 1, ∆H = −1 ∆E = −1, ∆H = 1
∆E = −1, ∆H = 1 ∆E = 1, ∆H = −1
+ +
2R 2R
+ +
registre dans état « bit 0 stocké » registre dans état « bit 1 stocké »
Figure 7.6 – En mesurant l’énergie en unités 2mgR et l’entropie en bits, les transformations permet-
tant d’écrire un bit (0 ou 1) à partir d’un état « vide », dépensent une unité d’énergie et diminuent
l’entropie d’un bit. Réciproquement l’effacement d’un bit (0 ou 1) restitue une unité d’énergie et
augmente l’entropie d’un bit.
/Users/dp/a/ens/[Link] 91
2019-11-03 • 18:19:27.
7.6. Registres de stockage de l’information Quantification de l’information
/Users/dp/a/ens/[Link]
92
2019-09-06 • 16:57:18.
Quantification de l’information 7.7. Exercices
7.7 Exercices
Entropie, mesure de l’information
66. Les habitants d’un village sont divisés en deux parties. Une partie A contient
des individus qui disent la vérité avec probabilité 1/2, mentent avec probabi-
lité 3/10 et refusent de répondre avec probabilité 2/10. La partie B contient des
individus dont les probabilités pour chaque type de comportement sont res-
pectivement 3/10, 1/2 et 2/10. Soit p ∈ [0, 1] la probabilité qu’un habitant du
village choisi au hasard appartienne au groupe A. On note i := i ( p) l’informa-
tion sur son comportement vis-à-vis des questions posées qui est véhiculé par
son appartenance à un groupe donné. Calculer p0 = arg max i ( p) et i ( p0 ).
67. Soient ( ai )i=1,...,n des nombres positifs vérifiant ∑in=1 ai = 1 et ( xi )i=1,...,n des
nombres strictement positifs. Établissez l’inégalité
n
x1a1 · · · xnan ≤ ∑ ai xi .
i =1
(b) Soient ( ai )i=1,...,n une famille de nombres positifs et (bi )i=1,...,n une famille de
nombres strictement positifs. Montrer que
n
ai n ∑nj=1 a j
∑ ai log bi ≥ ∑ log ∑n bk .
i =1 i =1 k =1
(c) Montrer que D (pkq) est convexe en le couple (p, q), i.e. si (p, q) et (p0 , q0 )
sont deux couples de vecteurs de probabilité et λ ∈ [0, 1] alors
/Users/dp/a/ens/[Link]
93
2019-09-06 • 16:57:18.
7.7. Exercices Quantification de l’information
(a) Calculer P( Z = x ).
(b) En se servant du fait que le conditionnement réduit l’incertitude, i.e. H ( Z ) ≥
H ( Z |Y ), établir le résultat de concavité de H (p) par rapport à p avec une
méthode alternative à celle utilisée dans l’exercice précédent.
(a) il existe une mesure de probabilité µ β sur X qui sature le supν∈M1 (X) ( H (ν) − βνU ),
où H (ν) désigne l’entropie de ν,
exp(− βU ( x ))
(b) µ β ( x ) = Z ( β)
, pour tout x ∈ X, où Z ( β) = ∑y∈X exp(− βU (y)) est un
facteur de normalisation.
(a) Utiliser la concavité de la fonction log pour montrer que pour tout ν ∈
M1 (X), on a H (ν) − βνU ≤ log Z ( β).
(b) Calculer H (µ β ) − βµ β U.
74. Simulation d’une loi arbitraire avec une pièce honnête. (Extrait de l’examen du
15 décembre 2014).
On dispose d’une pièce honnête (prenant de valeurs dans B = {0, 1} selon le
vecteur de probabilité (1/2, 1/2)). Les lancers successifs de la pièce sont modé-
lisés par des suites aléatoires de longueur arbitraire de bits indépendants, c’est-
à-dire par des mots ξ ∈ B+ (on rappelle que B+ = ∪∞ n=1 B ). On veut simuler
n
une variable aléatoire X à valeurs dans un ensemble fini X dont la loi est décrite
par un vecteur de probabilité p arbitraire. Autrement dit, nous voulons expri-
mer X comme fonction de certains mots, choisis d’une certaine manière, parmi
les mots de B+ , de façon que la loi de X soit déterminée par les probabilités des
mots choisis.
9. Le vecteur de probabilité ν est considéré comme un vecteur ligne, la variable aléatoire U comme
un vecteur colonne ; pour ν fixé, l’espérance de U est la forme linéaire νU.
/Users/dp/a/ens/[Link]
94
2019-09-06 • 16:57:18.
Quantification de l’information 7.7. Exercices
/Users/dp/a/ens/[Link] 95
2019-11-03 • 18:19:27.
7.7. Exercices Quantification de l’information
/Users/dp/a/ens/[Link] 96
2019-12-01 • 11:29:38.
Sources et leur codage
8
Nous disposons d’une source qui génère une suite de symboles que nous sup-
posons qu’ils puissent être transmis sans erreur, i.e. à travers un canal de transmis-
sion parfait (il restitue à sa sortie un message identique à celui qu’il reçoit en entrée).
Notre préoccupation donc est uniquement d’optimiser le codage de la source en tenant
compte de la probabilité avec laquelle les lettres du message-source sont produit.
8.1 Sources
Définition 8.1.1. Soit (Ω, F , P) un espace probabilisé adéquat.
1. Une source discrète est un dispositif qui émet une suite ( Xn )n∈N de variables
aléatoires à valeurs dans un ensemble fini X. L’ensemble X constitue les sym-
boles émis par la source. La source est totalement déterminée par la donnée
((Ω, F , P), X) que nous pouvons abréger en (X, P).
2. Une source discrète (X, P) est stationnaire si pour tout N ∈ N, tout n ≥ 1 et
tout n-uplet ( x1 , . . . , xn ) ∈ Xn , on a
P ( X N + 1 = x 1 , . . . , X N + n = x n ) = P ( X1 = x 1 , . . . , X n = x n ) .
3. Une source discrète (X, P) est markovienne si la suite ( Xn )n∈N est une chaîne
de Markov MC(X, P, ·).
4. Une source discrète (X, P) est sans mémoire si la suite ( Xn )n∈N est une suite
indépendante.
5. Une source discrète (X, P) sans mémoire est homogène si la suite ( Xn )n∈N est
une suite indépendante et identiquement distribuée avec P( Xn = x ) = p( x ),
pour tout x ∈ X et tout n ∈ N, où p = ( p( x )) x∈X ∈ PVX est le vecteur de
probabilité de la loi de X1 .
Dans ce chapitre nous nous limiterons au cas de sources discrètes homogènes sans
mémoire, c’est-à-dire que les messages produits peuvent être considérés comme des
97
8.2. Codes uniquement décodables Sources et leur codage
/Users/dp/a/ens/[Link] 98
2019-12-01 • 11:29:38.
Sources et leur codage 8.2. Codes uniquement décodables
Figure 8.1 – Le code iso/cei-646 C128 : X → A7 de longueur fixe de 7 bits. Par exemple la
lettre z ∈ X est codée en C128 (z) = h122i10 = h7Ai16 = h1111010i2 ∈ A7 . (Source de la figure :
domaine public).
/Users/dp/a/ens/[Link] 99
2019-12-01 • 11:29:38.
8.2. Codes uniquement décodables Sources et leur codage
α pour obtenir le mot duquel il est construit. Par exemple, pour le premier codage,
si α = 0110111100110, nous constatons aisément que α = C (134213). De la même
façon, pour le deuxième exemple, le mot α = 0100011 = C (12113). Cette possibilité de
décoder de manière unique est une caractéristique essentielle du code.
x C1 ( x ) C2 ( x ) C3 ( x ) C4 ( x )
1 0 0 10 0
2 0 010 00 10
3 1 01 11 110
4 1 10 110 111
C1 est singulier car il n’est pas injectif, C2 est non-singulier mais non uniquement dé-
codable car C2−1 (010) = {31, 2, 14}, C3 est uniquement décidable mais non instantané
car le mot de code 11 est préfixe du mot de code 110, C4 est instantané.
Le qualificatif instantané pour le codes dont les mots de code ne sont pas préfixes
d’autres mots de code provient du fait qu’un mot α nous est donné, son décodage se
fait au fur et à mesure de sa lecture ; la fin de chaque mot de code le composant est
déterminée uniquement par l’information accumulée par la lecture du mot de gauche
à droite ; il n’est pas nécessaire de connaître les lettres ultérieures pour décoder. Par
exemple, le code C sur X = {0, 1} défini par C (0) = 0, C (1) = 0| .{z
. . 0} 1 est uniquement
n
décodable ; cependant, si le mot 0| .{z
. . 0} 1 est envoyé, nous devons attendre la réception
n +1
des tous les n + 2 symboles pour savoir que le mot source était 01.
/Users/dp/a/ens/[Link] 100
2019-12-01 • 11:29:38.
Sources et leur codage 8.3. Théorème de Shannon sur le codage sans bruit
code C est uniquement décodable est plus difficile car il faut s’assurer de l’injectivité
de C sur X+ .
On peut établir un critère (condition nécessaire et suffisante) d’unique décodabilité
d’un code arbitraire à l’aide d’une procédure itérative. On note S0 = C (X) l’ensemble
de mots du code (vu comme suffixes du mot vide). Pour tout n ≥ 1, on construit
itérativement la suite des suffixes relatifs possibles
Sn = { β ∈ A+ : (αβ = γ) ∨ (γβ = α), pour α ∈ S0 , γ ∈ Sn−1 }.
On note ensuite S∞ = ∪n≥1 Sn . Le critère est donné par le
Théorème 8.2.8. [Sardinas-Patterson (1953)] Un code C : X → A+ est uniquement déco-
dable si, et seulement si,
S∞ ∩ S0 = ∅.
Démonstration. À rédiger ultérieurement.
Remarque 8.2.9. L’utilité du critère précédent peut paraître limitée car son application
nécessite la détermination de la suite infinie de suffixes relatifs (Sn )n≥1 . Il n’en est rien.
Notons en effet L = maxx∈X |C ( x )| la longueur maximale des mots du code. Il s’ensuit
que tous les mots de β ∈ Sn vérifient | β| ≤ L et, par conséquent, tous les ensembles de
suffixes Sn sont finis. La suite (Sn ) est donc nécessairement finalement périodique (i.e.
il existe deux entiers N, p ≥ 1 tels que pour tout m ≥ N : Sm = Sm+ p ). Une instance
particulière de périodicité finale est le cas S N = ∅ pour un certain N ≥ 1 ; il est alors
évident que Sm = ∅ pour tout m ≥ N. Cette remarque garantit que l’algorithme 8.2.10
s’arrête en un temps fini.
Pour B, C ⊆ A+ , on note B−1 C = {γ ∈ A∗ : βγ ∈ C, β ∈ B}. Le symbole ε est
toujours réservé pour le mot vide.
∑ A−li ≤ 1.
i∈ I
/Users/dp/a/ens/[Link] 101
2019-12-01 • 11:29:38.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
∑ A−lx ≤ 1 ⇒ ∑ A L − l x ≤ A L ⇒ A L − l1 < A L ;
x ∈X x ∈X
∑ A−lx ≤ 1 ⇒ ∑ A L − l x ≤ A L ⇒ A L − l1 + A L − l2 < A L ;
x ∈X x ∈X
/Users/dp/a/ens/[Link] 102
2019-12-01 • 11:29:38.
Sources et leur codage 8.3. Théorème de Shannon sur le codage sans bruit
J (`) = ∑ p ( x ) l x + λ ( ∑ A − l x − 1),
x x
E|C ( X )| ≥ H A ( X ),
car l’entropie relative D est positive et ∑y A−|C(y)| ≤ 1. Nous aurons égalité si D (pkr) =
0 et ∑y A−|C(y)| = 1.
/Users/dp/a/ens/[Link] 103
2019-12-01 • 11:29:38.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
Théorème 8.3.4. Soit X une variable aléatoire de loi décrite par le vecteur de probabilité p. Il
existe un code instantané C, tel que
Démonstration. En général, nous ne pouvons pas nous attendre à ce que les valeurs lx∗ =
− log A p( x ) qui minimisent la fonctionnelle d’optimisation J — introduite en début du
paragraphe — soient entières. Cependant, chaque intervalle [− log A p( x ), − log A p( x ) +
1[ contient nécessairement un entier lx . La famille des entiers (lx ) x∈X vérifie l’inégalité
∗
de Kraft car A−lx ≤ A−lx , pour tout x. Par conséquent, il existe un code instantané
C qui admet cette famille comme famille de longueurs de mots du code. De l’enca-
drement lx∗ ≤ lx ≤ lx∗ + 1 découle immédiatement l’inégalité H A (p) ≤ E|C ( X )| <
H A (p) + 1.
Nous avons établi l’inégalité de Kraft pour des codes C ∈ Cinst . Or la classe Cud
est plus grande que C ∈ Cinst . Nous pouvons donc légitimement nous interroger si
en optimisant E|C ( X )| sur la famille des codes uniquement décodables nous pouvons
améliorer la borne de l’entropie. Le théorème suivant répond négativement à cette
question.
Démonstration. On utilise le même symbole C pour noter le code primaire et son exten-
sion sur l’alphabet Xk de blocs de taille k.
1. On note
Xkj = {ξ ∈ Xk : |C (ξ )| = j};
Bi1 ,...,ik = {α ∈ A+ : α = α1 · · · αk , |α1 | = i1 , . . . , |αk | = ik }.
!k k !k
L L kL
∑ A−|C(x)| = ∑ ∑ A−l = ∑ νl A−l = ∑ Nl A−l ,
x l =1 x ∈X1 l =1 l =k
l
où
Nl = ∑
m ,...,m
νm1 · · · νmk = cardXkl .
1 k
m1 +...+mk =l
L’unique décodabilité du code C implique que pour chaque mot β ∈ Bi1 ,...,ik
avec i1 + . . . + ik = l, il existe au plus un mot ξ ∈ Xkl tel que C (ξ ) = β. Il est
évident par ailleurs que
Bi1 ,...,ik = Al .
[
i1 ,...,ik
i1 +...+ik =l
/Users/dp/a/ens/[Link] 104
2019-12-01 • 11:29:38.
Sources et leur codage 8.3. Théorème de Shannon sur le codage sans bruit
ce qui entraîne que ∑ x A−|C( x)| ≤ k1/k L1/k . Cette majoration étant vraie pour
tout k ≥ 1, restera vraie en passant à la limite k → ∞, établissant ainsi l’inégalité
de Kraft pour les longueurs |C ( x )| du code C.
2. Par le théorème 8.3.2, nous savons que si l’inégalité de Kraft est vérifiée pour
une famille d’entiers (lx ), il existe un code instantané C qui admet cette famille
d’entiers comme famille des longueurs. Or tout code instantané est uniquement
décodable.
Définition 8.3.6. 1. Un code C est dit K-optimal pour une classe particulière K ⊂
C si pour tout code C 0 ∈ K on a
2. Un code C ∈ Cud qui sature la borne de Shannon, i.e. qui vérifie E|C ( X )| =
H A ( X ), est dit absolument optimal.
En général nous ne pouvons pas espérer qu’un code primaire C : X → A+ soit ab-
solument optimal ; la saturation de la borne de Shannon pourra s’obtenir uniquement
pour des codes étendus sur Xk , lorsque k → ∞. Il est donc utile d’avoir des résultats
permettant d’ordonner de manière abstraite les codes par leur optimalité.
Lemme 8.3.8. Un code C optimal pour la classe Cinst est optimal pour la classe Cud .
Démonstration. Supposons qu’il existe un code C2 ∈ Cud meilleur que C. Nous au-
rons alors E|C2 ( X )| < E|C ( X )|. Notons l2 ( x ) = |C2 ( x )| pour x ∈ X ; le théorème
de McMillan 8.3.5 implique que les longueurs (l2 ( x )) vérifient l’inégalité de Kraft. Par
le théorème de Kraft 8.3.2, nous savons qu’il existe un code C1 ∈ Cinst qui admet a
|C1 ( x )| = l2 ( x ). Nous avons donc trouvé un code instantané C1 strictement meilleur
que C ce qui contredit l’optimalité de ce dernier.
/Users/dp/a/ens/[Link] 105
2019-12-01 • 11:29:38.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
/Users/dp/a/ens/[Link] 106
2019-12-01 • 11:29:38.
Sources et leur codage 8.3. Théorème de Shannon sur le codage sans bruit
/Users/dp/a/ens/[Link] 107
2019-12-01 • 11:29:38.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
/Users/dp/a/ens/[Link] 108
2019-12-01 • 11:29:38.
Sources et leur codage 8.4. Autres types de codes
du vecteur de probabilité mais cette information est suffisante pour coder et décoder le
message sans qu’une table complète pour des blocs de grande taille soit nécessaire. Les
codes par dictionnaire, dont un exemple est présenté en §8.4.2, ne nécessitent même
pas la connaissance du vecteur de probabilité et sont donc adaptés pour des codages
de textes plurilingues.
(avec ∑ x∈X p( x ) = 1). Le symbole précis qui représente chaque lettre d’entrée ne jouera
aucun rôle ; on identifie donc X avec l’ensemble {0, . . . , M − 1}. Cette identification in-
duit un ordre naturel sur le lettres de l’alphabet. Nous pouvons donc définir la fonction
de répartition d’une variable aléatoire X prenant des valeurs dans X selon la loi décrite
par p :
F ( z ) = P( X ≤ z ) = ∑ p ( y ),
y∈X,y≤ x
F (z−) = P( X < z) = ∑ p ( y ),
y∈X,y< x
pour tout z ∈ R.
5. L’auteur n’a pas pu accéder à la référence [27].
/Users/dp/a/ens/[Link] 109
2019-12-01 • 11:29:38.
8.4. Autres types de codes Sources et leur codage
0.8
0.6
0.4
0.2
0
−6 −4 −2 0 2 4 6
x p( x ) F ( x −) Ix
a'0 0.2 0.0 [0.0, 0.2[
b'1 0.5 0.2 [0.2, 0.7[
c'2 0.3 0.7 [0.7, 1.0[
Table 8.1 – L’association x 7→ Ix , x ∈ X, pour l’exemple 8.4.2.
/Users/dp/a/ens/[Link] 110
2019-12-01 • 11:29:38.
Sources et leur codage 8.4. Autres types de codes
on est sûr que l’approximation ŷ de y est encore dans l’intervalle Iξ ; elle peut
donc servir à représenter Iξ .
— Il s’ensuit que nous pouvons coder le mot ξ ∈ X N en posant C (ξ ) = β̂ L .
— Il est à souligner que le nombre de bits L := Lξ nécessaire dépend du mot ξ =
x1 · · · x N à travers la dépendance de la longueur l := lξ de l’intervalle Iξ . En
effet, lξ = p( x1 ) · · · p( x N ). Par conséquent Lξ = d− ∑kN=1 log A p( xk ) + log A 2e.
— Le décodage s’effectue en suivant le cheminement logique inverse.
On est alors en mesure de présenter le codage et le décodage SFE sous forme algo-
rithmique.
/Users/dp/a/ens/[Link] 111
2019-12-01 • 11:29:38.
8.4. Autres types de codes Sources et leur codage
Théorème 8.4.5. Soit ( Xn )n∈N une suite de variables aléatoires, à valeurs dans un alphabet
X, indépendantes et identiquement distribuées. On note X ( N ) = X1 · · · X N ∈ X N le N-uplet
de N copies indépendantes de la même variable aléatoire X distribuée selon la loi commune et
C : X → A+ le code de Shannon-Fano-Elias (et son extension sur X+ ). Alors
N log A 2 N
− ∑ log A p( xk ) +
N
≤ |C ( X ( N ) )| = L X ( N ) ≤ − ∑ log A p( xk ) + log A 2 + 1.
k =1 k =1
/Users/dp/a/ens/[Link] 112
2019-12-01 • 11:29:38.
Sources et leur codage 8.4. Autres types de codes
Table 8.2 – La construction du dictionnaire selon LZ78 ; elle correspond à l’analyse du mot ξ =
·0 · 1 · 11 · 01 · 010 · 00 · 10 ; le symbole · sert à visualiser les positions de césure. Le dictionnaire
contient 8 entrées —numérotées de 0 à 7 — nécessitant donc 3 bits pour être codées. Le code
brut correspondant à ξ est C (ξ ) = (0, 1)(0, 0)(1, 1)(2, 1)(4, 1)(2, 0)(1, 0). En codant la position
de chaque préfixe dans le dictionnaire par un mot de 3 bits, on obtient pour le code final C (ξ ) =
000100000010101100101000010 de longueur |C (ξ )| = 28 bits.
/Users/dp/a/ens/[Link] 113
2019-12-01 • 11:29:38.
8.4. Autres types de codes Sources et leur codage
On peut remarquer que le code LZ78 en aucun moment ne fait appel explicitement
au vecteur de probabilité de l’alphabet. Par ailleurs, il semble que pour le mot court de
l’exemple ci-dessus, on a |C (ξ )| > |ξ |, i.e. un code qui est plus plus long que le mot sur
lequel il s’applique. Il est cependant remarquable que l’on peut montrer le
Théorème 8.4.7. Soit ( Xn )n∈N une suite de variables aléatoire indépendantes et identique-
ment distribuées à valeurs dans X. Pour tout n ∈ N, on note X := X(n) = ( X1 X2 · · · Xn ) ∈
Xn . On alors
|C (X(n) )|
lim = H ( X1 ) .
n→∞ n
De manière encore plus remarquable, on peut étendre ce résultat à des suites de
variables aléatoires stationnaires (cf. définition 5.5.1).
Remarque 8.4.8. On montre aussi facilement qu’une suite ( Xn )n∈N de variables aléa-
toires sur un espace de probabilité (Ω, F , P) à valeurs dans (X, X ) est stationnaire si,
pour tout k ∈ N, les lois conjointes P( Xn ∈ B0 , . . . Xn+k ∈ Bk ), pour B0 , . . . , Bk ∈ X , ne
dépendent pas de n.
Les suites stationnaires généralisent les suites i.i.d. En effet, toute suite i.i.d. est
stationnaire. Il existe cependant des suites stationnaires qui ne sont pas i.i.d. comme le
montre l’exemple suivant.
/Users/dp/a/ens/[Link] 114
2019-12-01 • 11:29:38.
Sources et leur codage 8.5. Exercices
Exemple 8.4.9. 1. Soit ( Xn )n∈N une chaîne de Markov (X, P, π ), où π est la pro-
babilité invariante de la chaîne. Alors ( Xn )n∈N est stationnaire.
2. Soient (ξ n )n∈N une suite variables aléatoires réelles i.i.d. intégrables et (αn )n∈N
une suite réelle sommable. La suite ( Xn )n∈N définie, pour tout n ∈ N, par Xn =
∑∞m=0 αm ξ n+m est stationnaire.
Théorème 8.4.10. Soit X := ( Xn )n∈N une chaîne de Markov (X, P, π ), où π est la probabi-
lité invariante de la chaîne. Alors
|C ( X1 · · · Xn )|
lim = h ( X ),
n→∞ n
| H ( X1 ··· Xn )|
où h(X) := limn→∞ H ( Xn | X1 · · · Xn−1 ) = limn→∞ n est l’entropie spécifique (i.e.
l’entropie par variable aléatoire) de la chaîne.
La démonstration (voir [5, pp. 184–189] par exemple) de ce théorème est en dehors
des exigences de ce cours. On peut même démontrer un résultat analogue pour toute
suite stationnaire ergodique — pas nécessairement une chaîne de Markov possédant
une probabilité invariante — (voir [14, pp. 319–326]). Ce résultat s’inscrit dans le cadre
plus général de la relation entre la complexité de Kolmogorov — notion que sera ef-
fleurée dans le cours de Complexité [49] — et l’entropie.
8.5 Exercices
Codes instantanés, codes uniquement décodables
75. Soit C : {a, b} → {0, 1}∗ le code défini par
x C(x)
a 1
b 101
(a) Le code C est-il instantané ?
(b) Est-il uniquement déchiffrable ?
76. Déterminer si les codes suivants — définis sur des ensembles à 7 ou 8 éléments
selon le cas — sont instantanés ; sinon sont-ils uniquement décodables.
x1 abc 0101 00 00
x2 abcd 0001 112 11
x3 e 0110 0110 0101
x4 dba 1100 0112 111
x5 bace 00011 100 1010
x6 ceac 00110 201 100100
x7 ceab 11110 212 0110
x8 eabd 101011 22
77. Soient X un ensemble de cardinal M = 4 et p = (1/2, 1/4, 1/8, 1/8) un vecteur
de probabilité sur X. On considère les quatre codes Ck , k = 1, . . . , 4, définis ci-
dessous.
/Users/dp/a/ens/[Link]
115
2019-09-02 • 10:31:02.
8.5. Exercices Sources et leur codage
X C1 ( X ) C2 ( X ) C3 ( X ) C4 ( X )
a 0 00 0 0
b 10 01 1 01
c 110 10 00 011
d 111 11 11 111
(a) Calculer H (p).
(b) Pour k = 1, . . . , 4, calculer E|Ck ( X )| et comparer avec H (p).
(c) Pour k = 1, . . . , 4, déterminer si Ck est un code instantané et sinon s’il est
uniquement décodable.
Codes de Huffman
78. Soient X un ensemble de cardinal M et p un vecteur de probabilité sur X. Calcu-
ler un code de Huffman et comparer l’espérance de sa longueur avec l’entropie
dans les cas suivants :
(a) M = 5 et p = (0.25, 0.25, 0.2, 0.15, 0.15).
(b) M = 6 et p = (0.3, 0.25, 0.2, 0.1, 0.1, 0.05).
79. Soit X = {0, 1}, p = (0.9, 0.1) et p0 = (0.6, 0.4) deux vecteurs de probabilité et
K un entier strictement positif. On note X K = ( X1 , . . . , XK ), où ( Xi )i=1,...,K sont
de copies indépendantes de la même variable aléatoire sur X.
(a) Calculer H ( X K ) lorsque X1 est distribuée selon p et selon p0 .
(b) Calculer un code de Huffman C pour K = 2, . . . , 4 dans les deux cas p et p0 .
(c) Calculer Ep |C ( X K )| et Ep0 |C ( X K )| pour K = 2, . . . , 4.
80. Déterminer un vecteur de probabilité p sur X = {a, b, c, d} qui donne lieu à
deux codes de Huffman différents. Pour chacun de ces codes calculer l’espé-
rance de sa longueur et comparer la avec H (p).
/Users/dp/a/ens/[Link] 116
2019-12-01 • 11:29:38.
Sources et leur codage 8.5. Exercices
β = 00121212102101210122101
/Users/dp/a/ens/[Link] 117
2019-12-01 • 11:29:38.
8.5. Exercices Sources et leur codage
/Users/dp/a/ens/[Link] 118
2019-12-08 • 10:20:27.
Canaux bruités sans mémoire
9
La notion de canal est très générale. Initialement elle a été introduite pour signifier
la transmission d’un signal codant de l’information à travers un milieu et décrire les
altérations que subit l’information à cause du bruit. Cependant, on parle aujourd’hui
de canal pour modéliser une transformation arbitraire que subit un mot codé dans un
alphabet fini. Les codes que nous avons vus au chapitre précédent sont des cas par-
ticuliers des canaux. Ce qui va nous intéresser dans ce chapitre n’est pas de coder
efficacement la source mais de décrire précisément l’action du canal, c’est-à-dire les
perturbations dues au bruit.
Définition 9.1.1. Soit ( pn )n∈N une suite d’applications, définies pour tout n ∈ N, par
119
9.2. Classification des canaux Canaux bruités sans mémoire
1 − e0 e0
Exemple 9.1.2. Considérer le canal avec X = Y = {0, 1} et P = e1 1 − e1 , avec
e0 , e1 ∈ [0, 1]. Il s’agit d’un canal discret sans mémoire. On calcule
P(Y = 110|X = 010) = P(0, 1) P(1, 1) P(0, 0) = e0 (1 − e1 )(1 − e0 ).
Si e0 = e1 = 0 ce canal est parfait car P = I. Dans un certain sens, qui sera précisé
en §9.2 mais qui est intuitivement clair, le cas avec e0 = e1 = 1 correspond aussi à un
canal parfait, tandis que le cas e0 = e1 = 1/2 à un canal inutile.
Remarque 9.1.3. La notion de canal est une notion très générale. Nous avons étudié
en chapitre 8 le codage de la source. Si X = { a, b, c, d} et A = {0, 1}, nous avons
vu que C : X → A+ avec C ( a) = 0, C (b) = 10, C (c) = 110 et C (d) = 111 est
un code instantané. Ce code peut aussi être vu comme un canal avec Y = C (X) =
{0, 10, 110, 111} et P une matrice stochastique déterministe, correspondant à un canal
parfait. Plus généralement toute fonction f : X → Y est équivalente à une matrice
stochastique déterministe |X| × |Y|, notée K f , dont les éléments de matrice sont définis
par
X × Y 3 ( x, y) 7→ K f ( x, y) = δ f ( x) (y).
C’est-à-dire une fonction f : X → Y est le canal (X, Y, K f ).
Nous avons établi en chapitre 7 les propriétés de l’entropie et les relations entre
entropie conjointe, entropie conditionnelle et information mutuelle. Rappelons aussi
que si la loi (le vecteur de probabilité) de la source µ ∈ PVX et la matrice stochastique
P du canal sont données, nous pouvons calculer
— l’entropie de la source H ( X ),
— la loi conjointe κ ( x, y) = P( X = x, Y = y) = µ( x ) P( x, y) (et par conséquent
l’entropie conjointe H ( X, Y )),
— la loi de sortie ν(y) = ∑ x∈X κ ( x, y) = ∑ x∈X µ( x ) P( x, y) (et par conséquent l’en-
tropie de la sortie H (Y )),
— les entropies conditionnelles H ( X |Y ) et H (Y | X ) et l’information mutuelle I ( X :
Y ).
La figure 9.1 rappelle schématiquement les relations qui existent entre ces différentes
quantités. Il va de soi que toutes ces quantités sont fonctions du couple (µ, P). Ceci
nous amène, lorsque la loi de l’entrée est fixée, à une notation plus précise du canal.
Notation 9.1.4. Un canal discret sans mémoire est le quadruplet (X, µ, Y, P), où X, Y
sont les alphabets d’entrée er de sortie, µ la loi de l’entrée et P la matrice de trans-
mission. On garde cependant la notation sous forme de triplet (X, Y, P) lorsque nous
ne voulons pas préciser d’emblée la loi d’entrée (par exemple lorsque nous voulons
étudier le comportement du canal pour une famille de lois d’entrée (cf. définition de
capacité 9.3.1 plus loin).
/Users/dp/a/ens/[Link] 120
2019-12-08 • 10:20:27.
Canaux bruités sans mémoire 9.2. Classification des canaux
H ( X, Y )
H (X)
H (Y )
H ( X |Y ) I (X : Y) H (Y | X )
Figure 9.1 – Représentation schématique des valeurs de différentes entropies. Toutes ces quantités
sont fonctions de la loi de la source µ et de la matrice stochastique P du canal.
P(Y ∈ Bi | X = xi ) = ∑ P( xi , y) = P( xi , Bi ) = 1.
y∈ Bi
P( X = xi ; Y ∈ Bi ) = µ( xi );
µ ( xi ) µ ( xi )
P( X = xi |Y ∈ Bi ) = =
P(Y ∈ Bi ) ∑ j P(Y ∈ Bi | X j = x j )P( X = x j )
µ ( xi ) µ ( xi )
= = = 1.
∑ j δi,j µ( x j ) µ ( xi )
X × Y 3 ( x, y) 7→ κ ( x, y) = µ( x ) P( x, y) = µ( x )1{yx } (y).
Exemple 9.2.1. Supposons que nous disposions d’un jeu de 52 cartes. Soit X ∈ X =
{1, . . . , 10, J, Q, K} × {♥, ♦, ♠, ♣} le vecteur aléatoire du couple (valeur, enseigne) d’une
carte tirée au hasard et Y ∈ Y = {♥, ♦, ♠, ♣} la variable aléatoire « enseigne » de la
carte qui est transmise. Si la loi de X est la loi uniforme sur X, alors I ( X : Y ) = H (Y ) =
log 4 = 2.
/Users/dp/a/ens/[Link] 121
2019-12-08 • 10:20:27.
9.2. Classification des canaux Canaux bruités sans mémoire
0 = I ( X : Y ) = H ( X ) − H ( X |Y ) = 0 ⇒ H ( X ) = H ( X |Y ) ,
c’est-à-dire que les variables X et Y d’entrée-sortie sont indépendantes ou, dit autre-
ment, l’observation de la sortie ne nous apprend rien sur l’entrée. Une autre manifes-
tation de l’indépendance de variables X et Y est que toutes les lignes de la matrice
stochastique P sont égales entre elles (et bien-sûr correspondent à un vecteur de pro-
babilité sur Y).
sont des canaux symétriques. Effectivement, dans les deux cas, chaque ligne est la per-
mutation d’un même vecteur de probabilité et chaque colonne la permutation d’un
même vecteur de [0, 1]|X| .
Calculons l’entropie conditionnelle :
H (Y | X ) = ∑ µ ( x ) H (Y | X = x )
x ∈X
=− ∑ µ( x ) ∑ P(Y = y|X = x) log P(Y = y|X = x)
x ∈X y ∈Y
=− ∑ µ( x ) ∑ P( x, y) log P( x, y)
x ∈X y ∈Y
/Users/dp/a/ens/[Link] 122
2019-12-08 • 10:20:27.
Canaux bruités sans mémoire 9.3. Capacité du canal, propriétés de la capacité
Remarque 9.3.2. La signification de la définition 9.3.1 n’est pas encore très claire. Elle
le deviendra dans le §9.5. Signalons pour l’instant les deux résultats qui seront montrés
dans la suite :
1. il est possible de transmettre de l’information avec un taux d’erreur arbitraire-
ment petit à tout taux de transmission R (cf. définition 9.5.2) R < cap,
2. dès que le taux de transmission R dépasse la capacité cap, la transmission n’est
plus fiable.
Ceci signifie que chaque canal se comporte comme un « tuyau » à travers lequel on
peut faire passer un débit maximal de fluide.
Proposition 9.3.3. Soient un canal sans bruit (X, Y, P) et cap sa capacité.
1. cap ≥ 0.
2. cap ≤ log cardX.
3. cap ≤ log cardY.
Démonstration. 1. Comme I ( X : Y ) ≥ 0 (cf. remarque 7.5.8), la positivité de cap en
découle immédiatement.
2. On a
cap = sup I (X : Y) = sup ( H ( X ) − H ( X |Y )) ≤ sup H ( X ) ≤ log cardX.
µ∈M1 (X) µ∈M1 (X) µ∈M1 (X)
3. On a
cap = sup I (X : Y) = sup ( H (Y ) − H (Y | X )) ≤ sup H (Y ) ≤ log cardY.
µ∈M1 (X) µ∈M1 (X) µ∈M1 (X)
/Users/dp/a/ens/[Link] 123
2019-12-08 • 10:20:27.
9.4. Un exemple illustratif simple Canaux bruités sans mémoire
Notez que la matrice P̂t est stochastique mais pas P̂ elle-même. On constate aussi que
la solution au problème de maximisation de vraisemblance est
y arg maxz∈X P̂zy
y1 { x1 }
y2 { x1 , x2 , x3 }
y3 { x2 }
Tout élément x ∗ dans l’ensemble arg maxz∈X P( X = z|Y = y), pour y ∈ Y, peut
servir à définir ∆(y) := ∆MV (y) = x ∗ .
D’autres règles de décision sont possibles. Par exemple si X = {000, 111} et Y =
{0, 1}3 , on peut définir, pour tout y = (y1 , y2 , y3 ) ∈ Y, la règle de la majorité
(
000 si y1 + y2 + y3 ≤ 1,
∆(y) := ∆Maj (y) =
111 si y1 + y2 + y3 > 1.
/Users/dp/a/ens/[Link] 124
2019-12-08 • 10:20:27.
Canaux bruités sans mémoire 9.5. Le théorème fondamental de la transmission
On peut même définir des règles de décision stochastiques, i.e. décrites par des
noyaux stochastiques non-déterministes K∆ : Y × X → [0, 1], signifiant qu’à chaque
symbole y ∈ Y reçu, on assigne un symbole x ∈ X avec probabilité K∆ (y, x ). Dans
l’exemple 9.4.1, on peut définir une règle de décision stochastique décrite par le noyau
stochastique
1 0 0
K∆ := 1/3 1/3 1/3 .
0 1 0
Mais ceci n’est pas le seul choix. Tout noyau stochastique K∆ : Y × X → [0, 1] correspon-
drait à une règle de décision pas nécessairement plausible mais acceptable du point
de vue de la théorie. Noter aussi que les règles de décision du maximum de vrai-
semblance et de la majorité (ainsi que toute autre règle de décision décrite par une
fonction ∆ : Y → X) sont aussi décrites par des noyaux stochastiques déterministes
K∆ : Y × X → {0, 1}, définis par K∆ (y, x ) = 1{∆(y)} ( x ).
On arrive ainsi à la définition suivante :
Définition 9.4.3. Une règle de décision est un noyau stochastique
K∆ : Y × X → [0, 1]
qui assigne à tout symbole y ∈ Y reçu par le canal, un symbole émis x ∈ X avec
probabilité K∆ (y, x ).
/Users/dp/a/ens/[Link] 125
2019-12-08 • 10:20:27.
9.5. Le théorème fondamental de la transmission Canaux bruités sans mémoire
M codage Xn Yn décodage M
m C(m) y ∆(y)
Xn canal Yn
y (1)
x ..
.
y( L)
Qn (x, y(i) )
Figure 9.2 – Résumé des actions de codage, transmission et décodage, considérées séparément.
Notez que l’action du canal transforme toute entrée x ∈ Xn en une variable aléatoire
Y ∈ Xn de loi conditionnelle (à l’entrée) Qn (x, ·), i.e. pour tout A ⊂ Yn , P(Y ∈ A| X =
x) = ∑y∈ A Qn (x, y).
y (1) ∆ ( y (1) )
m C(m) .. ..
. .
y( L) ∆ (y( L) )
Qn ( C ( m ), y (i ) )
Figure 9.3 – Résumé des actions de codage, transmission et décodage, considérées séquentiellement.
/Users/dp/a/ens/[Link] 126
2019-12-08 • 10:20:27.
Canaux bruités sans mémoire 9.5. Le théorème fondamental de la transmission
I.e. le codage est le canal déterministe (M, Xn , KC ) (cf. remarque 9.1.3). L’opération
de décodage ∆ est aussi une fonction ; elle est donc équivalente au canal déterministe
(Yn , M, K∆ ), où K∆ (y, m) = δ∆(y) (m). La séquence codage-transmission-décodage équi-
vaut donc à la multiplication de 3 matrices stochastiques KC Qn K∆ (vérifier que les
dimensions des matrices permettent leur multiplication dans cet ordre). Ce canal com-
posé transformera tout vecteur de probabilité (ligne) a priori µ ∈ M1 (M) en un vec-
teur de probabilité (ligne) a posteriori νµ = µKC Qn K∆ ∈ M1 (M). En particulier, il
transformera l’entrée déterministe M = m (correspondant au vecteur de probabilité
µ = δm ) en la variable aléatoire M0 ∈ M de loi ν, c’est-à-dire,
Plus généralement, lorsque le message d’entrée est lui même considéré comme résul-
tant d’un choix aléatoire selon une loi µ non-déterministe, nous obtenons
νµ (m0 ) = Pµ ( M0 = m0 ) = ∑ P( M 0 = m 0 | M = m ) µ ( m )
m ∈M
= ∑ ∑ n µ(m)Qn (C(m), y)δ∆(y) (m0 ).
m ∈M y ∈Y
(n)
emax := emax = max e(n) (m),
m ∈M
e : = e(n) = ∑ µ ( m ) e ( n ) ( m ).
m ∈M
(n) (n)
Comme e(n) (m) ≤ emax pour tout m ∈ M, il est évident que e(n) ≤ emax . Cependant, un
des résultats importants du théorème fondamental de la transmission sera que lorsque
n → ∞, les deux erreurs sont du même ordre.
/Users/dp/a/ens/[Link] 127
2019-12-08 • 10:20:27.
9.5. Le théorème fondamental de la transmission Canaux bruités sans mémoire
Définition 9.5.1. Un (k, n)-code (par blocs) (avec k et n entiers supérieurs à 1) pour un
canal discret sans mémoire (X, Y, P) est la donnée
— d’un ensemble de messages M avec cardM = k,
— d’un codage C : M → Xn de taille fixe n,
— d’un décodage ∆ : Yn → M.
On note ce code K, ou plus précisément K(k, n) si on veut préciser ses paramètres.
L’ensemble C(M) ⊆ Xn est appelé glossaire du code K.
Le codage C est toujours supposé non-singulier, i.e. injectif. En le considérant comme
une application C : M → C(M), il devient aussi surjectif, donc bijectif. Étant donné
que C est bijectif entre M et son glossaire, on peut identifier M avec le glossaire et
considérer M comme isomorphe à une partie spécifique de Xn .
(n)
Il est évident qu’une fois le code K choisi, les erreurs emax et e(n) définies plus haut,
dépendent de K ; on précise cette dépendance en écrivant emax [K(k, n)] ou e[K(k, n)].
Définition 9.5.2. Soit K un (k, n)-code par blocs.
1. Son taux de transmission R est défini par
log|X| k
R := R[K] = .
n
2. Un taux de transmission R est atteignable s’il existe une suite (K` )`∈N de (k ` , n` )-
codes par blocs, tels que liml →∞ emax [K` ] = 0.
Exemple 9.5.3. Soit X = {0, 1} l’alphabet binaire.
1. On considère le (2, 3)-code par blocs de répétition de taille 3 avec M = {0, 1},
défini par C(b) = bbb, pour b ∈ M, i.e. de glossaire C(M) := {000, 111}. Il a un
log 2
taux de transmission R = 32 = 13 .
2. On considère le (4, 3)-code par blocs avec bit de parité de taille 3 avec M =
{00, 01, 10, 11}, découlant, pour tout message ab ∈ M, du codage C( ab) = abc ∈
X3 avec c = a + b + mod 2, i.e. ayant comme glossaire C(M) = {000, 011, 101, 110}.
log 4
Il a un taux de transmission R = 32 = 23 .
9.5.3 Le théorème
Le théorème fondamental de la transmission établit que la capacité est le supremum
des taux de transmission atteignables.
Théorème 9.5.4. Soit (X, Y, P) un canal sans mémoire de capacité cap := cap( P).
1. Pour tout R < cap, il existe une suite infinie (K` )`∈N de (k ` , n` )-codes, ayant des taux
log k`
de transmission R` := n|X| vérifiant R` ↓ R, tels que lim`→∞ e[K` ] = 0.
`
2. Réciproquement, pour tout R > cap et toute suite (K` )`∈N de (k ` , n` )-codes avec des
blocs de taille croissante (i.e. n1 < n2 < n3 < . . .) et des taux de transmission vérifiant
R` ≥ R, on a lim`→∞ e[K` ] = 1.
La démonstration de ce théorème est longue et assez compliquée. Elle est basée sur
la notion de suites conjointement typiques et fait usage du fait que si I ( X : Y ) > 0,
en prenant des blocs suffisamment longs, on peut distiller un code et en raréfiant l’en-
semble de messages à coder (i.e. en ne considérant qu’un sous-ensemble suffisamment
épars de messages) on peut transmettre avec une erreur arbitrairement petite. L’idée
est illustrée dans l’exemple 9.5.5.
/Users/dp/a/ens/[Link] 128
2019-12-08 • 10:20:27.
Canaux bruités sans mémoire 9.5. Le théorème fondamental de la transmission
Figure 9.4 – Le touches blanches correspondent aux notes de base : do, re, mi, fa, sol, la, si. La
touche représentée en cyan sur la figure correspond au « do » de base, la touche représentée en jaune
sur la figure au « la » et la gamme se répète périodiquement sur le clavier. Source de la figure :
Wikipédia ; distribuée sous licence CC BY-SA 3.0.
L’idée intuitive sous-tendant la démonstration du théorème 9.5.4 est que tout canal,
pour des blocs de taille n suffisamment grande, se comporte comme l’exemple 9.5.5.
Démonstration du théorème 9.5.4 : À compléter.
2. Le théorème ne dit rien sur . . . la musicalité de l’interprétation. Le titre de cet exemple est un jeu
de mots faisant référence à l’œuvre Das wohltemperierte Klavier de J.-S. Bach, connu en français sous le
titre Le clavier bien tempéré. Falschtemperierte pourrait se traduire par mal tempéré.
/Users/dp/a/ens/[Link]
129
2019-09-02 • 10:31:36.
9.6. Exercices Canaux bruités sans mémoire
9.6 Exercices
Codage du canal
85. Pour trois variables aléatoires X, W, Y discrètes arbitraires, établir les relations
suivantes :
(a) H (W, Y | X ) ≤ H (W | X ) + H (Y | X ).
(b) H (W, Y | X ) = H (W | X ) + H (Y | X, W ).
(c) H (Y | X, W ) ≤ H (Y | X ).
86. Soient les canaux K1 = (X, π, W, P) et K2 = (W, ρ, Y, Q) où X, W et Y sont
des alphabets d’entrée ou de sortie et P et Q des matrices de transmission. On
construit le canal K = (X, π, Y, PQ) en mettant les canaux K1 et K2 en cascade.
(a) Comparer les probabilités conditionnelles P(Y = y| X = x, W = w) et P(Y =
y |W = w ) .
(b) Montrer que la capacité CK du canal composé ne peut pas excéder la plus
petite des capacités CK1 et CK2 .
(c) Commenter ce dernier résultat.
87. Soient X un espace fini, X une variable aléatoire à valeurs dans X, g : X → W
une application arbitraire et Y une variable aléatoire à valeurs dans Y de loi
conjointe κ avec X. Monter par deux méthodes différentes que H (Y | g( X )) ≥
H (Y | X ) .
88. (Extrait de l’examen du 19 décembre 2013).
Soit un canal discret sans mémoire ayant un alphabet d’entrée X, un alphabet
de sortie Y, une matrice stochastique de transmission P et une loi des symboles
d’entrée déterminée par le vecteur de probabilité π. Lorsque un symbole y ∈ Y
est transmis, on le décode par un schéma de décision qui peut être soit une
fonction déterministe d : Y → X soit une variable aléatoire ∆ définie sur Y à
valeurs dans X.
(a) Déterminer le vecteur de probabilité ρ définissant la loi des symboles de sor-
tie.
(b) On se place dans le cas particulier X= { x1 , x2 , x3 }, Y = {y1 , y2 , y3 }, π =
1 0 0
(1/2, 1/4, 1/4) et P = 0 1 0 . Calculer ρ.
0 1/2 1/2
(c) Dans le cas particulier ci-dessus, on utilise le schéma de décision détermi-
niste d(y1 ) = x1 , d(y2 ) = d(y3 ) = x3 . Calculer la probabilité globale de
décision (=décodage) erronée.
(d) Pour une règle de décision d, établir les formules générales des probabilités
de décision correcte et erronée, notées respectivement PTE(d) et PTC(d).
(e) Calculer la probabilité de décision correcte dans le cas particulier de la ques-
tion b).
(f) On appelle observateur idéal le choix de la règle de décision do (y) = xy ,
où y ∈ Y, le xy maximise la probabilité conditionnelle P( X = x |Y = y),
c’est-à-dire :
xy = arg max P( X = x |Y = y).
x
Monter que la règle de décision ainsi définie est optimale, c’est-à-dire, pour
toute autre règle déterministe d0 , on PTC(d) ≤ PTC(do ).
/Users/dp/a/ens/[Link]
130
2019-09-02 • 10:31:36.
Canaux bruités sans mémoire 9.6. Exercices
3. Les valeurs numériques données pour les probabilités de la source et de l’erreur permettent de
déterminer toutes les autres probabilités comme des rationnels calculables facilement à la main.
4. Les valeurs numériques données pour les probabilités de la source et de l’erreur permettent de
déterminer toutes les autres probabilités comme des rationnels calculables facilement à la main.
/Users/dp/a/ens/[Link]
131
2019-09-02 • 10:31:36.
9.6. Exercices Canaux bruités sans mémoire
ii. Si le canal est « enZ » avec tauxd’erreur f = 1/16, i.e. sa matrice sto-
1 0
chastique est P = , calculer
1/16 15/16
— Le vecteur de probabilité de sortie ν
— Les probabilités Q(1, 0) et Q(1, 1).
91. Soient Ki , avec i = 1, 2 deux canaux avec alphabets d’entrée Xi , alphabets de
sortie Yi et matrices de transmission Pi . On note X = X1 ⊕ X2 (si les alphabets
X1 et X2 sont distincts alors X1 ⊕ X2 = X1 ∪ X2 ; s’ils ne sont pas distincts,
on commence par distinguer artificiellement les éléments de X1 et de X2 avant
de prendre leur réunion). De même Y = Y1 ⊕ Y2 . Finalement
la matrice de
P1 0
transmission du canal « somme » est la matrice bloc P = .
0 P2
(a) Soient X une variable aléatoire à valeurs dans X dont la loi est décrite par
le vecteur de probabilité π et Y une variable aléatoire à valeurs dans Y. On
note κ la loi conjointe du couple ( X, Y ). Soit p = ∑ x∈X1 π ( x ) (donc 1 − p =
π (x)
∑ x∈X2 π ( x )). Pour x ∈ X1 on note ρ1 ( x ) = p et pour x ∈ X2 on note
π (x)
ρ2 ( x ) = 1− p . Montrer que H (π ) = H ( p, 1 − p) + pH (ρ1 ) + (1 − p) H (ρ2 ).
(b) Montrer que
H ( X |Y ) = − p ∑ ρ1 ( x ) P1 ( x, y) log P( X = x |Y = y)
x ∈X1 ,y∈Y1
− (1 − p ) ∑ ρ2 ( x ) P2 ( x, y) log P( X = x |Y = y).
x ∈X2 ,y∈Y2
H ( X |Y ) = pH ( X1 |Y1 ) + (1 − p) H ( X2 |Y2 )
et conclure que
2C1
(d) Montrer que la valeur de p qui maximise C ( p) est p = .
2C1 +2C2
(e) En conclure que la capacité du canal « somme » vérifie C
2 =2 1 C + 2C2 .
/Users/dp/a/ens/[Link] 132
2019-12-08 • 10:20:27.
10
Chiffrement
Augustus Kerchoffs : La cryptographie militaire ; Journal des sciences militaires (1883) [31, page 12].
Dans l’extrait ci-dessus, Augustus Kerchoffs énonçait, en 1883, avec une surpre-
nante modernité, les conditions que doit remplir un bon système de cryptage. On
pourrait utiliser ce passage — presque mot pour mot — pour formuler les exigences
cryptographiques d’aujourd’hui.
133
10.1. Sécurité des communications Chiffrement
est supposée inversible. Dans tous les systèmes cryptologiques, il est supposé qu’il est
très difficile de calculer l’inverse si la clé est inconnue.
On peut donc décrire les opération de cryptage et de décryptage comme des opé-
rations de codage et de décodage vues aux chapitres précédents. Plus précisément :
C : M × K → Y,
/Users/dp/a/ens/[Link] 134
2019-12-08 • 11:11:28.
Chiffrement 10.1. Sécurité des communications
Table 10.1 – Une estimation grossière de l’ordre de grandeur du temps nécessaire pour factoriser un
entier à n bits (avec n = 100, 500, 1000), sous l’hypothèse d’exécution du programme de factorisation
sur un ordinateur hypothétique faisant une opération par nanoseconde, comme fonction de la com-
plexité temporelle de l’algorithme. Lorsque le protocole RSA a été proposée [50] en 1978, le meilleur
algorithme avait une complexité temporelle de O(exp(n)). De nos jours, le meilleur algorithme [36] a
une complexité O(exp(n1/3 log2/3 n)). Si un ordinateur quantique se construit, l’algorithme de Shor
[56] a une complexité O(n3 ). Pour mémoire : « âge de l’univers » = 1.377 × 1010 a.
Comme on verra dans le paragraphe suivant 10.2, la mise en place d’un code in-
conditionnellement sûr exige
— la génération d’une suite de même dimension que le message à coder de nombres
purement aléatoires ,
— l’utilisation de la suite une seule fois ou one-time pad et
— la transmission sûre de la clé de cryptage.
Durant plus d’un siècle, ces trois exigences étaient impossible à réaliser en pratique.
C’est pourquoi, les méthodes de cryptographie symétrique à clé privée ont été aban-
données au profit du cryptage asymétrique à clé publique (RSA par exemple). L’avè-
nement de la technologie quantique en cryptographie change la donne car aujourd’hui
on dispose des méthodes rapides, fiables et efficaces remplissant ces exigences. Des
solutions quantiques sont déjà proposées dans un stade pré-industriel et à un coût
raisonnable (cf. cours [48]).
/Users/dp/a/ens/[Link] 135
2019-12-08 • 11:11:28.
10.2. Code de Vernam (one-time pad) Chiffrement
Comme mentionné dans l’article de revue de Bellovin ([3]), en 1882, Frank Miller 1
avait proposé une méthode de chiffrement, appelée one-time pad, qui permettait de chif-
frer des messages en les combinant avec des clés de même longueur. Le 13 septembre
1918, Gilbert Vernam dépose aux États-Unis une demande de brevet pour un dispositif
appelé « Secret signaling system » de chiffrement selon la méthode de one-time-pad.
La demande est acceptée et Vernam devient détenteur du brevet US Patent 1310719 le
22 juillet 1919 2 .
La méthode introduite par Vernam porte aujourd’hui le nom de code de Vernam
et sa description peut être trouvée dans [60]. La méthode est censée réponde aux exi-
gences de Kerchoffs.
Soit A alphabet fini, identifié au groupe additif Z|A| := {0, . . . , |A| − 1} des entiers
modulo |A|. Les messages que nous enverrons constituent une partie spécifique M ⊆
X := A+ , i.e. ils sont des mots finis sur cet alphabet. Les fréquences d’apparition de
lettres sont arbitraires ; M peut par conséquent correspondre à une partie d’un langage
naturel, du français par exemple.
Supposons que l’on veuille chiffrer le message m ∈ M, avec N := |m|. On suppose
que nous disposons d’une clé aléatoire K ∈ K := A N , distribuée selon la loi uniforme
sur K, i.e. P(K = k) = K 1
= A1N . Le chiffrement se fait par addition bit par bit mo-
dulo |A| des lettres de m et de k, i.e. C (m, k) = y, avec yi = mi + k i mod |A|. Plus
précisément, on a
On constate que l’algorithme de Vernam génère une clé aléatoire de même lon-
gueur que le message à chiffrer et que cette clé est utilisée pour ce seul message. Le
récipiendaire du message chiffré y, s’il connaît la clé k, exécute l’algorithme suivant :
1. L’auteur de ces notes n’a pas pu consulter le texte original de la contribution de Frank Miller,
Telegraphic code to insure privacy and secrecy in the transmission of telegrams. C.M. Cornwell (1882).
2. Par la suite il améliore son invention en accédant à d’autres brevets US Patent 1416765, US Patent
1584749 et US Patent 1613686.
/Users/dp/a/ens/[Link] 136
2019-12-08 • 11:11:28.
Chiffrement 10.2. Code de Vernam (one-time pad)
Lemme 10.2.3. Si m0 est obtenu par l’application de l’algorithme 10.2.2 sur le cryptgramme
y produit par l’algorithme 10.2.1, alors
(
0 0 1 si m0 = m
P( M = m | M = m ) =
0 sinon.
1. de longueur N = |m|,
2. utilisée une seule fois et
3. connue uniquement des deux partenaires légitimes,
alors l’algorithme de Vernam (10.2.1 et 10.2.2) est parfaitement sûr, i.e. il offre une sécurité
inconditionnelle.
P(M = m, Y = y) P(M = m, K = k, Y = y)
P( Y = y | M = m ) = = ∑
P( M = m ) k∈K
P( M = m )
P(Y = y|M = m, K = k)
= ∑ P( M = m )
P(M = m, K = k)
k∈K
1
= ∑ P(K = k)δy,m⊕k = P(K = y m) =
|A| N
, ∀m ∈ M.
k∈K
/Users/dp/a/ens/[Link] 137
2019-12-08 • 11:11:28.
10.2. Code de Vernam (one-time pad) Chiffrement
calcule de même
P(m = m, Y = y) P(m = m, K = k, Y = y)
P( M = m | Y = y ) = = ∑
P( Y = y ) k∈K
P( Y = y )
P(Y = y|M = m, K = k)
= ∑ P ( Y = y )
P(M = m, K = k)
k∈K
P( K = k)P( M = m ) P( K = y m )
= ∑ P ( Y = y )
δy,m⊕k =
P ( Y = y )
P( M = m )
k∈K
= P( M = m ).
On conclut que la connaissance du fait que Y = y ne nous apprend rien sur M. De
l’indépendance de Y et M découle l’égalité I (M : Y) = 0 et la sécurité inconditionnelle
du code de Vernam.
Exemple 10.2.5. Le résultat précédent implique qu’en absence de connaissance de la
clé, le seul moyen d’attaquer le code de Vernam est la recherche exhaustive des clés
dans K. Maintenant, supposons que le message initial est
m = wewonthebattlebutwedefinitelylostthewar
et que par une clé k il est codé en y. Un intrus qui ne connaît pas la clé k doit examiner
toutes les clés k0 ∈ K (étant donné que m = 39, il en existe 2639 = 1.53 × 1055 telles
clés) et calculer tous les message m0 = y k0 . La plupart de messages ainsi obtenus
n’auront aucun sens. Mais il en existe qui ont un sens totalement différent, par exemple
parmi ces messages il trouvera bien sûr m mais aussi
m0 = overwhelminglyvictoriousovertheevilaxis
/Users/dp/a/ens/[Link] 138
2019-12-08 • 11:11:28.
Chiffrement 10.3. Authentification
Après que l’affaire des révélations d’Edward Snowden éclate (en 2013), le NIST est obligé
d’admettre que l’algorithme est floué et publie, en 2015, une recommandation révisée 6 d’où il
retire l’algorithme incriminé.
L’American Mathematical Society (AMS) initie la publication dans ses Notices d’une série d’ar-
ticles sur le thème « Mathematicians discuss the Snowden revelation ». Dans cette série, appa-
raît un article 7 par Michael Wertheimer. Notons que l’AMS se sent obligée d’apposer la préci-
sion « At the time of the writing of this piece Michael Wertheimer was the Director of Research
at the NSA ; he recently retired from that position » sur cet article.
10.3 Authentification
L’authentification d’un message consiste à fournir au destinataire légitime l’évi-
dence que le message reçu émane bien de l’expéditeur, même en présence d’un adver-
saire qui peut
— envoyer au destinataire des messages frauduleux de sa propre facture (non émis
par l’expéditeur), — on parle alors d’usurpation d’identité (impersonation en
anglais) — et/ou
— intercepter les messages expédiés en les substituant par des messages fraudu-
leux générés par lui — on parle alors de substitution.
Dans ce paragraphe nous nous intéressons à une authentification informationnelle
(inconditionnelle) 8 c’est-à-dire, nous supposons que la partie adverse connaît tous les
algorithmes utilisés par les partenaires légitimes ; elle ignore uniquement la clé secrète
qu’ils ont utilisée. Nous suivons les exposés [58, 57, 40]. Contrairement au cas de cryp-
tage, où le théorème de Shannon fournit comme définition du parfait chiffrement l’in-
dépendance entre les messages émis et chiffré, la situation est plus subtile dans le cas
de l’authentification. On ne connaît pas de définition d’authentification parfaite : on
peut rendre la probabilité de fraude (deceit probability en anglais) arbitrairement petite
— en utilisant une clé d’authentification suffisamment longue — sans jamais l’annuler.
P(Y = y| X = x; K = k ) = Mk ( x, y), x ∈ X, y ∈ Y, k ∈ K.
6. NIST Special Publication 800-90A Revision 1: Recommendation for Random Number Generation
Using Deterministic Random Bit Generators (2015).
7. Intitulé « Encryption and the NSA role in international standards ».
8. Par opposition à une authentification algorithmique (calculatoire).
/Users/dp/a/ens/[Link] 139
2019-12-08 • 11:11:28.
10.3. Authentification Chiffrement
La partie adverse — qui tente d’usurper l’identité de A mais ignore la clé utilisée —
génère un message Ỹ ∈ Y selon une loi (arbitraire) q̃, i.e. P(Ỹ = y) = q̃(y) et l’envoie
de manière intempestive à B.
Le problème mathématique se pose donc comme un problème de test d’hypothèses
statistiques ; on note H0 l’hypothèse nulle signifiant que le message reçu par B est un
message authentique et H1 l’hypothèse alternative signifiant que le message reçu est
frauduleux. Pour décider quel est le cas qui prévaut, le partenaire B dispose d’une fa-
mille — indexée par K — de règles de décision (∆k )k∈K , i.e. des applications ∆k : Y →
{0, 1} ; les valeurs 0 ou 1 prises par ∆k signifient respectivement que H0 ou H1 sont ac-
ceptées, i.e. que le message est respectivement jugé « authentique » ou « frauduleux ».
Pour chaque k, la règle de décision permet donc de partitioner l’ensemble Y en deux
sous-ensembles disjoints Yk (0) := {y ∈ Y : ∆k (y) = 0} et Yk (1) := {y ∈ Y : ∆k (y) =
1}.
Le partenaire B reçoit donc un message
(
Y si l’hypothèse H0 prévaut,
Ŷ =
Ỹ si l’hypothèse H1 prévaut
et doit se servir de sa règle de décision pour départager les deux cas. Il est alors évident
que, sur l’évènement {Ŷ = y},
P(K = k, ∆k (y) = 1| H0 ) = µ(k, y),
P(K = k, ∆k (y) = 0| H1 ) = ρ(k )q̃(y).
β= ∑ ρ(k )q̃(z).
z ∈Yk (0)
On voit que α représente l’erreur de première espèce (juger le message non authentique
tandis qu’il l’est) et β l’erreur de deuxième espèce (juger le message authentique tandis
qu’il ne l’est pas) ; β représente donc la probabilité que l’adversaire réussisse son coup.
/Users/dp/a/ens/[Link] 140
2019-12-08 • 11:11:28.
Chiffrement 10.4. Signature
On constate alors que Yk (0) et Yk (1) sont des fragmentations de {0} et de {1}. Comme
la fragmentation augmente le contraste de Kullback-Leibler (voir la proposition 7.3.6),
on aura, pour toute probabilité de génération de messages q̃ utilisée par la partie ad-
verse, D (αk β) ≤ D (µkρ ⊗ q̃).
Corollaire 10.3.2. Pour tout schéma d’authentification,
d(α, β) ≤ I (K : Y ).
En particulier, si α = 0, la probabilité d’usurpation d’identité est minorée par
β ≥ 2− I (K:Y ) .
Démonstration. La majoration D (αk β) ≤ D (µkρ ⊗ q̃) obtenue dans le théorème pré-
cédent est valable pour toutes les probabilités q̃ potentiellement utilisées par l’usurpa-
teur. Elle peut donc être optimisée en D (αk β) ≤ inf p∈M1 (Y) D (µkρ ⊗ p). En particulier,
D (αk β) ≤ D (µkρ ⊗ ν)
car ν n’est pas nécessairement optimale. Or D (µkρ ⊗ ν) = I (K : Y ).
Si α = 0, l’inégalité devient d(0, β) = log β1 ≤ I (K : Y ).
10.4 Signature
/Users/dp/a/ens/[Link] 141
2019-12-08 • 11:11:28.
10.6. Exercices Chiffrement
10.6 Exercices
9. To solicit, evaluate, and standardize one or more quantum-resistant public-key cryptographic algorithms.
[Link]
/Users/dp/a/ens/[Link] 142
2019-12-08 • 11:11:28.
11
Codes correcteurs d’erreur
1
Shannon
Taux de transmission R
0.8 Rn
Région inaccessible
0.6
0.4
0.2
0
10−1410−1210−10 10−8 10−6 10−4 10−2
Probabilité d’erreur résiduelle q
143
11.1. La borne de Hamming Codes correcteurs d’erreur
11.5 Exercices
Codes à répétition
Dans ce paragraphe, on considère un canal binaire symétrique ayant une proba-
bilité d’erreur p. On note R N le code à N répétitions pour chaque bit et pb ( R N , p) la
probabilité de décoder de manière erronée un bit par la méthode de vote majoritaire.
92. Calculer pb ( R3 , p) pour p = 0.1.
93. Pour N arbitraire,
(a) Calculer pb ( R N , p).
(b) Pour p = 0.1 quel est le terme dominant dans l’expression de pb ( R N , p).
(c) À partir de quelle valeur de N, on obtient une valeur de pb ( R N , 0.1) ≤
10−15 ?
(d) Quel est le taux de transmission pour R N ?
(e) Placer les couples ( R N , log pb ( R N , p)) pour N ∈ {1, 3, 5 . . . , 101} sur un gra-
phique. Qu’observez-vous ?
Codes de Hamming
94. Décoder par le code de Hamming H AM (7, 4) les messages suivants :
(a) = 1101011,
r
(b) = 0110110,
r
(c)= 0100111,
r
(d) = 1111111.
r
95. Calculer toutes les chaînes de bruit b ∈ {0, 1}7 qui donnent un syndrome nul
pour H AM (7, 4).
96. Pour le code H AM (7, 4) et le canal binaire symétrique avec p = 0.1,
(a) déterminer la probabilité qu’un block de 7 bits ne soit pas décodé correcte-
ment,
(b) en déduire la probabilité du taux d’erreur par bit, dans le cas où le poids du
bruit est exactement k Bk = 2.
97. La matrice de contrôle de parité du code H AM (15, 4) est donnée par
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 0 0 0 0 1 1 1 1 0 1 0 0
H :=
0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 .
1 0 1 1 1 0 1 0 1 0 1 0 0 0 1
/Users/dp/a/ens/[Link]
144
2019-09-02 • 10:31:54.
Codes correcteurs d’erreur 11.5. Exercices
/Users/dp/a/ens/[Link] 145
2019-09-15 • 14:02:24.
Références Codes correcteurs d’erreur
/Users/dp/a/ens/[Link] 146
2019-11-03 • 17:54:07.
Bibliographie
[1] Robert B. Ash. Information theory. Dover Publications Inc., New York, 1990. Cor-
rected reprint of the 1965 original. 78
[2] Philippe Barbe and Michel Ledoux. Probabilité. EDP Sciences, Les Ulis, 2007.
Deuxième édition, revue et corrigée. 9, 14
[3] Steven M. Bellovin. Frank miller: Inventor of the one-time pad. Cryptologia, 35, 07
2011. 136
[4] Manabendra Nath Bera, Arnau Riera, Maciej Lewenstein, Zahra Baghali Khanian,
and Andreas Winter. Thermodynamics as a Consequence of Information Conser-
vation. Quantum, 3:121, February 2019. 78
[5] Rabi N. Bhattacharya and Edward C. Waymire. Stochastic processes with applica-
tions. Wiley Series in Probability and Mathematical Statistics: Applied Probability
and Statistics. John Wiley & Sons Inc., New York, 1990. A Wiley-Interscience Pu-
blication. 115
[6] Patrick Billingsley. Probability and measure. Wiley Series in Probability and Ma-
thematical Statistics. John Wiley & Sons Inc., New York, third edition, 1995. A
Wiley-Interscience Publication. 9, 12
[7] Ludwig Boltzmann. Vorlesungen über Gastheorie, 1. Theil. Verlag von Johann Am-
brosius Barth, Leipzig, 1896. 78, 79
[8] Ludwig Boltzmann. Leçons sur la théorie cinétique des gaz. Traduit de l’original al-
lemand par A. Galloti. Gauthiers-Villars, Paris, 1902. Ré-imprimé par les Éditions
Jacques Gabay, Paris (1987). 79
[9] Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web
search engine. Comput. Netw. ISDN Syst., 30(1-7):107–117, April 1998. 56
[10] Allen Broughton and Barthel W. Huff. A comment on unions of sigma-fields.
Amer. Math. Monthly, 84(7):553–554, 1977. 18
[11] Yuan Shih Chow and Henry Teicher. Probability theory. Springer Texts in Statistics.
Springer-Verlag, New York, third edition, 1997. Independence, interchangeability,
martingales. 33
[12] Kai Lai Chung. A course in probability theory. Academic Press, Inc., San Diego, CA,
third edition, 2001. 33
[13] The Unicode Consortium. Unicode Standard, Version 5.0, The (5th Edition). Addison-
Wesley Professional, 5 edition, 2006. 98
[14] Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley-
Interscience [John Wiley & Sons], Hoboken, NJ, second edition, 2006. 78, 115
[15] Harald Cramér. On the representation of a function by certain Fourier integrals.
Trans. Amer. Math. Soc., 46:191–201, 1939. 33
147
Références BIBLIOGRAPHIE
[16] Persi Diaconis, Susan Holmes, and Richard Montgomery. Dynamical bias in the
coin toss. SIAM Rev., 49(2):211–235, 2007. 16
[17] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE
Trans. Information Theory, IT-22(6):644–654, 1976. 135
[18] Jean-Guillaume Dumas, Jean-Louis Roch, Éric Tannier, and Sébastien Varette.
Foundations of Coding: Compression, Encryption, Error Correction. Wiley, 2015. 134
[19] Paul Ehrenfest and Tatiana Ehrenfest. Über zwei bekannte einwände gegen das
boltzmannsche h-theorem. Physilalsche Zeitschrift, 8:311–314, 1907. 53
[20] Peter Elias. Error-free coding. Information Theory, Transactions of the IRE Professional
Group on, 4(4):29–37, 1954. 2
[21] Peter Elias. The noisy channel coding theorem for erasure channels. Amer. Math.
Monthly, 81(8):853–862, 1974. 2
[22] J. Gemmer, M. Michel, and G. Mahler. Quantum thermodynamics, volume 784 of
Lecture Notes in Physics. Springer-Verlag, Berlin, second edition, 2009. Emergence
of thermodynamic behavior within composite quantum systems. 78
[23] Hans-Otto Georgii. Probabilistic aspects of entropy. In Entropy, Princeton Ser.
Appl. Math., pages 37–54. Princeton Univ. Press, Princeton, NJ, 2003. 78
[24] Hans-Otto Georgii. Stochastik. de Gruyter Lehrbuch. [de Gruyter Textbook]. Wal-
ter de Gruyter & Co., Berlin, expanded edition, 2009. Einführung in die Wahr-
scheinlichkeitstheorie und Statistik. [Introduction to probability and statistics]. 9,
14
[25] J. Willard Gibbs. Elementary principles in statistical mechanics: developed with especial
reference to the rational foundation of thermodynamics. Dover publications Inc., New
York, 1960. 78
[26] David A. Huffman. A method for the construction of minimum-redundancy
codes. Proceedings of the IRE, 40, 1952. 108
[27] F. Jelinek. Probabilistic Information Theory. McGraw-Hill, N. Y., 1968. 109
[28] R.S. Katti and A. Ghosh. Security using Shannon-Fano-Elias codes. In Circuits
and Systems, 2009. ISCAS 2009. IEEE International Symposium on, pages 2689–2692,
2009. 112
[29] Mark Kelbert and Yuri Suhov. Information Theory and Coding by Example. Cam-
bridge University Press, Cambridge, 2013. 78
[30] Joseph B. Keller. The probability of heads. Amer. Math. Monthly, 93(3):191–197,
1986. 16
[31] Auguste Kerchoffs. La cryptographie militaire. Journal des sciences militaires, pages
5–38, 1883. 133
[32] Aleksandr Yakovlevich Khinchin. Mathematical foundations of information theory.
Dover Publications Inc., New York, N. Y., 1957. Translated by R. A. Silverman and
M. D. Friedman. 2, 78
[33] Andrej Nikolaevich Kolmogoroff. Grundbegriffe der Wahrscheinlichkeitsrechnung.
Springer-Verlag, Berlin, 1977. Reprint of the 1933 original. 3, 9
[34] Leon G. Kraft. A device for quantizing, grouping, and coding amplitude-modulated
pulses. PhD thesis, Massachusetts Institute of Technology, 1949. 102
/Users/dp/a/ens/[Link] 148
2019-11-03 • 17:54:07.
BIBLIOGRAPHIE Références
[35] Rolf Landauer. The physical nature of information. Phys. Lett. A, 217(4-5):188–193,
1996. 92
[36] A. K. Lenstra and H. W. Lenstra, Jr., editors. The development of the number field
sieve, volume 1554 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1993.
135
[37] Annick Lesne. Shannon entropy: a rigorous notion at the crossroads between
probability, information theory, dynamical systems and statistical physics. Math.
Structures Comput. Sci., 24(3):e240311, 63, 2014. 78
[38] Eugene Lukacs. Characteristic functions. Hafner Publishing Co., New York, 1970.
Second edition, revised and enlarged. 33
[39] David J. C. MacKay. Information theory, inference and learning algorithms. Cambridge
University Press, New York, 2003. 78
[40] Ueli M. Maurer. Authentication theory and hypothesis testing. IEEE Trans. Inform.
Theory, 46(4):1350–1356, 2000. 139
[41] R. J. McEliece. The theory of information and coding, volume 86 of Encyclopedia of
Mathematics and its Applications. Cambridge University Press, Cambridge, student
edition, 2004. With a foreword by Mark Kac. 78
[42] Brockway McMillan. The basic theorems of information theory. Ann. Math. Sta-
tistics, 24:196–219, 1953. 104
[43] Jacques Neveu. Bases mathématiques du calcul des probabilités. Préface de R. Fortet.
Deuxième édition, revue et corrigée. Masson et Cie, Éditeurs, Paris, 1970. 9
[44] J. R. Norris. Markov chains, volume 2 of Cambridge Series in Statistical and Probabi-
listic Mathematics. Cambridge University Press, Cambridge, 1998. Reprint of 1997
original. 51
[45] Juan M. R. Parrondo, Jordan M. Horowitz, and Takahiro Sagawa. Thermodyna-
mics of information. Nature Physics, 11:131 EP –, 02 2015. 78
[46] William A. Pearlman and Amir Said. Digital signal compression : principles and
practice. Cambridge University Press, 2011. 109
[47] Dimitri Petritis. Markov chains on measurable spaces, 2015. Premiminary draft
of lecture notes taught at the University of Rennes 1. 44, 51
[48] Dimitri Petritis. Mathematical foundations of quantum mechanics, 2018. Notes
de cours pour le master de cryptographie - version préliminaire, Université de
Rennes 1. 135
[49] Dimitri Petritis. Théorie de la complexité, 2018. Notes de cours pour le master de
cryptographie - version préliminaire, Université de Rennes 1. 115, 138
[50] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures
and public-key cryptosystems. Comm. ACM, 21(2):120–126, 1978. 135
[51] Y. A. Rozanov. Probability theory. Dover Publications Inc., New York, english edi-
tion, 1977. A concise course, Translated from the Russian and edited by Richard
A. Silverman. 9
[52] Claude E. Shannon. A mathematical theory of communication. Bell System Tech.
J., 27:379–423, 623–656, 1948. 77, 103
[53] Claude E. Shannon. Communication in the presence of noise. Proc. I.R.E., 37:10–
21, 1949. 2
/Users/dp/a/ens/[Link] 149
2019-11-03 • 17:54:07.
Index BIBLIOGRAPHIE
[54] Claude E. Shannon. Communication theory of secrecy systems. Bell System Tech.
J., 28:656–715, 1949. Claude Shannon’s report, originally issued as a classified do-
cument entitled “A Mathematical Theory of Cryptography”, Memorandum MM
45-110-02, September 1, 1945, was formally published in 1949 as “Communica-
tion Theory of Secrecy Systems” in Bell System Technical Journal, 28 (1949) 656–
715. The original form of the paper, is nowadays available only as a low quality
scanned version. Recently a version has been retyped by Jiejun Kong and made
available to the community. 2, 133, 137
[55] Albert Nikolaevich Shiryayev. Probability, volume 95 of Graduate Texts in Mathema-
tics. Springer-Verlag, New York, 1984. Translated from the Russian by R. P. Boas.
9, 33, 36
[56] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. 135
[57] G. J. Simmons. A survey of information authentication. In Contemporary crypto-
logy, pages 379–419. IEEE, New York, 1992. 139
[58] Gustavus J. Simmons. Authentication theory/coding theory. In George Robert
Blakley and David Chaum, editors, Advances in Cryptology, pages 411–431, Berlin,
Heidelberg, 1985. Springer Berlin Heidelberg. 139
[59] Yakov Grigorevich Sinai. Probability theory. Springer Textbook. Springer-Verlag,
Berlin, 1992. An introductory course, Translated from the Russian and with a
preface by D. Haughton. 9
[60] Gilbert S. Vernam. Cipher printing telegraph systems for secret wire and radio
telegraphic communications. Journal of the IEEE, 55:109–115, 1926. 136
[61] Jacob Ziv. Coding theorems for individual sequences. IEEE Trans. Inform. Theory,
24(4):405–412, 1978. 112
[62] Jacob Ziv and Abraham Lempel. Compression of individual sequences via
variable-rate coding. IEEE Trans. Inform. Theory, 24(5):530–536, 1978. 112
/Users/dp/a/ens/[Link] 150
2019-11-03 • 18:28:38.
Index
151
Index INDEX
registre
de stockage, 86
état informationnel du –, 86
univers, 9
variable aléatoire, 15
discrète, 29
espérance d’une —, 30
/Users/dp/a/ens/[Link] 152
2019-11-03 • 18:28:38.