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
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 67
6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 Estimation paramétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2.1 Estimation ponctuelle . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2.2 Estimation d’intervalles de confiance . . . . . . . . . . . . . . . . 70
6.2.3 Tests d’hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
II Théorie de l’information 77
7 Quantification de l’information 79
7.1 Postulats d’une quantité d’incertitude, entropie . . . . . . . . . . . . . . . 79
7.2 Trois interprétations de l’entropie . . . . . . . . . . . . . . . . . . . . . . . 84
7.2.1 H est une espérance (qui nous fait vieillir !) . . . . . . . . . . . . . 84
7.2.2 H est le nombre moyen de questions nécessaires pour déterminer
la valeur que prend une variable aléatoire . . . . . . . . . . . . . . 84
7.2.3 H est le rapport des logarithmes du volume des configurations
typiques sur celui de toutes les configurations . . . . . . . . . . . 87
7.3 Propriétés de la fonction entropie, entropie relative . . . . . . . . . . . . 89
7.4 Entropie des évolutions markoviennes . . . . . . . . . . . . . . . . . . . . 91
7.5 Couples de variables aléatoires . . . . . . . . . . . . . . . . . . . . . . . . 93
7.5.1 Entropie conjointe . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.5.2 Entropie conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . 94
7.5.3 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.6 Registres de stockage de l’information . . . . . . . . . . . . . . . . . . . . 95
7.7 Irreversibilité et principe de Landauer . . . . . . . . . . . . . . . . . . . . 97
7.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
/Users/dp/a/ens/[Link] iv
2023-01-02 • 09:41:54.
TABLE DES MATIÈRES TABLE DES MATIÈRES
10 Chiffrement 149
10.1 Sécurité des communications . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.1.1 Les exigences du chiffrement . . . . . . . . . . . . . . . . . . . . . 150
10.1.2 Les niveaux de sécurité . . . . . . . . . . . . . . . . . . . . . . . . 150
10.2 Le chiffrement comme code . . . . . . . . . . . . . . . . . . . . . . . . . . 152
10.2.1 Code de Vernam (one-time pad) . . . . . . . . . . . . . . . . . . . . 152
10.2.2 Le rôle essentiel des nombres aléatoires . . . . . . . . . . . . . . . 155
10.3 Authentification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
10.3.1 Illustration du problème et notation . . . . . . . . . . . . . . . . . 156
10.3.2 Minoration de la probabilité de fraude (cas de substitution) . . . 156
10.3.3 Minoration de la probabilité de fraude (cas d’usurpation d’identité)157
10.4 Qu’est-ce la cryptographie post-quantique ? . . . . . . . . . . . . . . . . . 159
10.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Références 176
Index 182
/Users/dp/a/ens/[Link] v
2023-01-02 • 09:41:54.
TABLE DES MATIÈRES TABLE DES MATIÈRES
/Users/dp/a/ens/[Link] vi
2023-01-02 • 09:41:54.
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
2022-08-30 • 11:36:05.
Aléa et information 1.2. Probabilités et intuition aléatoire
/Users/dp/a/ens/[Link] 3
2022-08-30 • 11:36:05.
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 avec remise (n >
0, M > 0) :
É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
2021-08-19 • 17:06:16.
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
2021-08-19 • 17:06:16.
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
2022-08-30 • 11:36:05.
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 [42] et nous
nous inspirons librement des exposés pédagogiques [29, 61, 65, 69], en particulier pour
le choix de certains exemples. Les livres [2, 8, 52] 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 [42] 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
2022-08-30 • 11:37:23.
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 ∩ An = ∅, 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
2022-08-30 • 11:37:23.
2.1. Espace de probabilité Théorie élémentaire des probabilités
Axiome 2.1.14 (de choix). Pour toute collection C d’ensembles non-vides, il existe une fonction de choix
définie sur C qui à chaque ensemble A ∈ C associe un élément de cet ensemble. Plus précisément :
Démonstration du théorème 2.1.13. On introduit une relation d’équivalence sur Ω en décrétant que deux
suites ω, ω 0 ∈ Ω sont équivalentes si elles sont identiques à partir d’une certaine position, i.e.
[ω ∼ ω 0 ] ⇔ [∃n0 ∈ N : ωn = ωn0 , ∀n ≥ n0 ].
Par l’axiome de choix, il existe une partie A ⊆ Ω qui contient exactement un élément de chaque classe
d’équivalence de Ω/ ∼.
On note S = {S ⊂ N : cardS < ∞} ⊆ t`∈N S` , où S` = {S ⊂ N : max S = `}. De toute évidence,
S est dénombrable. Si S ∈ S , on définit TS = ◦k∈S Tk (l’ordre de composition des fonctions est sans
importance car les applications Tk et Tk0 commutent pour k 6= k0 ). On observe que
— La famille ( TS A)S∈S est composée de parties deux-à-deux disjoints. En effet, supposons que
TS A ∩ TS0 A 6= ∅ pour S, S0 ∈ S . Il existe alors ω, ω 0 ∈ A tels que TS ω = Ts0 ω 0 . Nous aurons
alors,
ω ∼ TS ω = Ts0 ω 0 ∼ ω 0 .
Par le choix de A, ceci signifie que ω = ω 0 et par conséquent S = S0 .
— Par ailleurs Ω = tS∈S TS A, car, en effet, pour tout ω ∈ Ω, il existe ω 0 ∈ A, tel que ω ∼ ω 0 . Par
conséquent, il existe un S ∈ S tel que ω = TS ω 0 ∼ ω 0 ∈ TS A.
— En utilisant successivement les propriétés de normalisation, d’additivité dénombrable disjointe
et d’invariance aux renversements des bits, nous arrivons à la conclusion absurde :
1. L’axiome de choix a été introduit par Zermelo en 1904 pour formaliser la théorie axiomatique des
ensembles.
/Users/dp/a/ens/[Link] 12
2022-08-30 • 11:37:23.
Théorie élémentaire des probabilités 2.1. Espace de probabilité
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.17. 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éunions 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. On peut en don-
ner une en s’inspirant de la démonstration du théorème 2.1.13 ; on peut en trouver une
dans [8, pp. 24–28] par exemple.
Définition 2.1.18 (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.19 (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.
2. Additivité finie. P( A ∪ B) + P( A ∩ B) = P( A) + P( B). En particulier P( A) +
P( Ac ) = 1.
3. Monotonie. Si A ⊆ B alors P( A) ≤ P( B).
4. σ-sous-additivité. P(∪n∈N An ) ≤ ∑n∈N P( An ).
5. σ-continuité monotone. Si soit An ↑ A soit An ↓ A (i.e. la suite ( An ) est soit croissante
avec réunion A soit décroissante avec intersection A), alors P( An ) −−−→ P( A).
n→∞
P( ∅ ) = P( ∅ ∪ ∅ ∪ . . . ) = ∑ P( ∅ ).
n ∈N
P( A ∪ B ) = P( A ∪ B ∪ ∅ ∪ ∅ ∪ . . . ) = P( A ) + P( B ) + 0 + 0 + . . . .
/Users/dp/a/ens/[Link] 13
2022-08-30 • 11:37:23.
2.1. Espace de probabilité Théorie élémentaire des probabilités
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] 14
2022-08-30 • 11:37:23.
Théorie élémentaire des probabilités 2.1. Espace de probabilité
ω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.
/Users/dp/a/ens/[Link] 15
2022-08-30 • 11:37:23.
2.2. Variables aléatoires Théorie élémentaire des probabilités
Contre-exemple 2.1.25. 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 à Ω).
Remarque 2.2.3. La donnée importante pour une variable aléatoire est sa loi PX (une
probabilité sur (X, X )). L’espace abstrait (Ω, F , P) n’est qu’une construction auxiliaire.
Le choix du triplet (Ω, F , P) reflète le moyen où le système décrit par la variable aléa-
toire X est construite et il n’est pas unique comme le montre l’exemple 2.2.4.
Exemple 2.2.4. (Trois manières radicalement différentes de jouer au pile ou face). Jouer
au pile ou face équivaut à construire une probabilité PX = 12 ε 0 + 12 ε 1 sur X = {0, 1},
muni de sa tribu exhaustive X = P (X).
Monsieur Tout-le-monde joue au pile ou face. On lance une pièce sur une table
approximativement considérée infiniment étendue dans le plan horizontale et
infiniment plastique. L’état instantané de la pièce est un élément de Ω = (R+ ×
R2 ) × R3 × R3 × S2 . Cet espace code la position du centre de masse R, la vi-
tesse du centre de masse V, le moment angulaire M et l’orientation N de la
normale extérieure sur la face « face ». On choisit pour F = B(Ω) et P désigne
/Users/dp/a/ens/[Link] 16
2022-08-30 • 11:37:23.
Théorie élémentaire des probabilités 2.2. Variables aléatoires
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.
Le simulateur (sur ordinateur) joue au pile ou face. Soient Ω = [0, 1], F = B([0, 1])
et P la mesure de Lebesgue sur [0, 1]. Le résultat d’une pièce honnête est modé-
lisé par la variable aléatoire
0 si ω < 1/2
X (ω ) =
1 si ω > 1/2.
/Users/dp/a/ens/[Link] 17
2022-08-30 • 11:37:23.
2.3. Exercices Théorie élémentaire des probabilités
Définition 2.2.5. Soit X une variable aléatoire réelle (i.e. à valeurs dans X ⊆ R) définie
sur l’espace de probabilité (Ω, F , P). On appelle fonction de répartition de X (ou de
sa loi PX ) l’application
R 3 x 7→ FX ( x ) := P({ω ∈ Ω : X (ω ) ≤ x }) = PX (] − ∞, x ]).
où PX ({ xi }) = ρ X ( xi ) = ∆FX ( xi ) := FX ( xi ) − FX ( xi −).
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).
2.3 Exercices
Algèbres, tribus
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] 18
2022-09-12 • 09:36:12.
Théorie élémentaire des probabilités 2.3. Exercices
2. 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. [12]. La réunion engendre cependant une tribu, notée ∨i∈N Fi ,
par le procédé décrit dans cet exercice, i.e. ∨i∈N Fi = σ(∪i∈ I Fi ).
/Users/dp/a/ens/[Link] 19
2022-09-12 • 09:36:12.
2.3. Exercices Théorie élémentaire des probabilités
20. Supposons que Ω est dénombrable (fini ou infini) et qu’il existe une application
ρ : Ω → [0, 1] telle que ∑ω ∈Ω ρ(ω ) = 1. Montrer que ρ définit une mesure de
probabilité sur (Ω, F ) définie par
Ω 3 ω = (ω1 , . . . , ωk , . . . , ωn ) 7→ Tk ω := (ω1 , . . . , 1 − ωk , . . . , ωn ) ∈ Ω.
/Users/dp/a/ens/[Link] 20
2022-09-12 • 09:36:12.
Théorie élémentaire des probabilités 2.3. Exercices
Noter que si FX a une densité comme ci-dessus, alors FX est continue et différen-
tiable avec FX0 = ρ X . (La démonstration de ces affirmations n’est pas demandée.
Tandis que la démonstration de la continuité est facile, celle de la différentiabi-
lité est longue et non-triviale.
/Users/dp/a/ens/[Link] 21
2022-08-30 • 11:37:23.
2.3. Exercices Théorie élémentaire des probabilités
/Users/dp/a/ens/[Link] 22
2022-08-30 • 11:38:08.
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 ).
23
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 3.1.5. (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] 24
2022-08-30 • 11:38:08.
Probabilité conditionnelle et indépendance 3.1. Conditionnement
Dans le cas considéré dans le théorème précédant (où N < ∞) la tribu X = ⊗nN=0 P (Xn )
coïncide avec la tribu exhaustive X = P (X), engendrée par les singletons X = σ({x}, x ∈
X). La démonstration donc du théorème est élémentaire. Pour établir par exemple
l’unicité de la construction, il suffit de vérifier que toutes les probabilités définies par
le membre de droite de la formule de l’énoncé coïncident sur les singletons, sont donc
identiques sur X .
Nous serons cependant amenés à considérer des suites infinies de variables aléa-
toires, 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.7 mais pour N → ∞. La difficulté
essentielle provient du fait que, même pour une suite (Xn )n∈N d’alphabets finis, l’es-
pace X = ×n∈N Xn n’est plus dénombrable. Le théorème 3.1.8, démontré ci-dessous,
fournit la généralisation du théorème 3.1.7 dans le cas N = ∞.
Théorème 3.1.8. Soit (Xn )n∈N une suite d’alphabets dénombrables. On note X = ×n∈N Xn
le produit cartésien des ces alphabets. L’espace X est supposé muni de la tribu X = ⊗n∈N P (Xn ).
Supposons que ρ0 est un vecteur de probabilité sur X0 et pour tout k ≥ 1, et tout x =
( x0 , x1 , . . .) ∈ X, ρk,xk−1 un vecteur de probabilité sur Xk . Alors, il existe un espace probabi-
lisé (Ω, F , P), avec (Ω, F ) suffisamment riche pour que toute la suite X = ( X0 , X1 , . . .) =
( Xn )n∈N de variables aléatoires soit définie de façon que, pour tout N ≥ 1 et tout x ∈ X, la
probabilité P soit l’unique probabilité sur (Ω, F ) vérifiant
Remarque 3.1.9. La tribu X = ⊗n∈N P (Xn ) n’est pas la tribu exhaustive. Elle est
engendrée par la famille des « rectangles » R = ∪ N ∈N R N , où
/Users/dp/a/ens/[Link] 25
2022-08-30 • 11:38:08.
3.2. Indépendance Probabilité conditionnelle et indépendance
Nous obtenons une partition à l’ordre k, en écrivant chacun de ceux intervalles comme une partition
plus fine
Ix0 ··· xk−1 = t xk ∈Xk Ix0 ··· xk ,
avec λ( Ix0 ··· xk ) = λ( Ix0 ··· xk−1 )ρk,xk−1 ( xk ). Cette construction peut être répétée ad infinitum.
Pour chaque k, la famille ( Ix )x∈X0 ×···×Xk 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 une variable aléatoire. En effet, considérer la famille G = {∅} ∪ k≥0 Gk ,
S
où
Gk = { X0 = x0 , . . . , Xk = xk , xi ∈ Xi , i = 0, . . . , k} = {Xk = xk }.
Cette famille constitue une algèbre qui engendre une tribu F , sous-tribu de B([0, 1[). Par ailleurs, pour
tout cylindre C = [ x0 · · · x N ] ∈ C , on aura X−1 (C ) = {X N = x N } = IxN ∈ F ⊆ B([0, 1[). En outre,
λ ◦ X−1 définit bien une probabilité P sur (Ω, F ) ayant les propriétés requises.
Unicité. Supposons qu’il existe deux mesures de probabilité P et P0 sur (Ω, F ) telles que
On remarque que ces probabilités coïncident sur G . Comme G contient l’ensemble vide, est stable par
intersection finie et engendre F , elles coïncideront sur F .
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 ).
/Users/dp/a/ens/[Link] 26
2022-08-30 • 11:38:08.
Probabilité conditionnelle et indépendance 3.2. Indépendance
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.
exercice 38). 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 39).
Définition 3.2.3. Soient (Ω, F , P) un espace de probabilité et I 6= ∅ une famille arbi-
traire d’indices.
1. Une famille ( Ai )i∈ I d’événements de F est dite indépendante par rapport à P
si pour toute partie finie J, ∅ 6= J ⊆ I, nous avons
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
A = {lors du premier lancer la pièce tombe sur face},
B = {lors du second lancer la pièce tombe sur face},
C = {lors des deux lancers la pièce tombe du même côté}.
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.
La définition 3.2.3 appliquée à la construction faite dans le théorème 3.1.8 implique
que les vecteurs de probabilité ne dépendent pas de x. Une famille de variables aléa-
toires ( Xn )n=1,...,N , avec Xn : Ω → Bn , est indépendante si sur chaque (Xn , P (Xn )), il
existe un vecteur de probabilité ρn (indépendant des xi pour i < n) et
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] 27
2022-08-30 • 11:38:08.
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 mar-
ginales arbitraires). Ceci reste valable même pour des suites infinies ( Xn )n∈N de va-
riables aléatoires Xn : Ω → Xn indépendantes, sur des alphabets dénombrables (Xn ).
Le théorème 3.1.8 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 les formules
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]
28
2021-11-13 • 17:54:44.
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é ?
Une usine a produit 2 lots, notés a et b, d’objets. Tous les objets du lot a sont fonc-
tionnels tandis que seulement 75% d’objets du lot b sont fonctionnels, les autres
étant défectueux. On note p = (1/2, 1/2) le vecteur de probabilité uniforme sur
l’ensemble de lots L = { a, b} et X = {d, f }.
(a) On modélise par la variable aléatoire L à valeurs dans L, de loi a priori p, le
choix du lot et par une variable aléatoire X à valeurs dans X l’état de l’objet
choisi. On choisit un lot au hasard (selon p) et un objet au hasard (selon
la loi uniforme) dans le lot ; l’objet se trouve être fonctionnel. Déterminer le
vecteur de probabilité a posteriori q sur L, obtenue après que cette expérience
ait eu lieu (i.e. sachant que l’objet choisi est fonctionnel).
(b) On remet l’objet dans le lot duquel il a été extrait et on choisit au hasard un
deuxième objet de ce même lot. Quelle est la probabilité que cet objet soit
défectueux ? (On note Y la variable aléatoire à valeurs dans X qui modélise
l’état du second objet extrait).
Indépendance
38. Une urne contient n boules discernables noires et r boules discernables 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 }}
/Users/dp/a/ens/[Link]
29
2021-11-13 • 17:54:44.
3.3. Exercices Probabilité conditionnelle et indépendance
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 } ⊂ Ω.
/Users/dp/a/ens/[Link] 30
2022-08-30 • 11:38:08.
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 et 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).
31
4.1. Espérance Espérance, variance ; théorèmes des grands nombres
E( X ) = EP ( X ) := ∑ xP( X = x ).
x ∈ X (Ω)
E( X ) = ∑ xP( A x )
x ∈ X (Ω)
= ∑ xPX ({ x })
x ∈ X (Ω)
= ∑ xρ X ( x )
x ∈ X (Ω)
Démonstration. 1. Soit (Ω, F , P) un espace probabilisé sur lequel les deux variables aléatoires X :
Ω → X = X (Ω) et Y : Ω → Y = Y (Ω) sont simultanément définies. La condition X ≤ Y
signifie que pour toute réalisation ω ∈ Ω, X (ω ) ≤ Y (ω ). On conclut que
= ∑ yP( X −1
(X), Y −1
({y})) = ∑ yP(Y −1 ({y})) = E(Y ).
y ∈Y y ∈Y
/Users/dp/a/ens/[Link] 32
2022-09-18 • 20:20:33.
Espérance, variance ; théorèmes des grands nombres 4.1. Espérance
L’égalité requise s’obtient en enlevant la valeur absolue dans la suite des relations ci-dessus.
3. Par la positivité des variables, pour tout N ∈ N, nous avons X ≥ S N := ∑kN=0 Xk et par consé-
quent, par la linéartité de l’espérance E( X ) ≥ ∑kN=0 E( Xk ). La dernière inégalité est vraie pour
tout N ∈ N ; elle sera alors vraie dans la limite N → ∞, i.e. E( X ) ≥ ∑k∈N E( Xk ).
Pour conclure, il faut établir l’inégalité inverse. Soit c ∈]0, 1[ arbitraire τ = inf{ N ≥ 0 : S N ≥
cX } ∈ N ∪ {+∞}. Puisque S N ↑ X, il s’ensuit que τ < ∞. Or {τ < ∞} = ∪ N ∈N {τ = N } ; par
conséquent, Sτ = Sτ ∑ N ∈N 1{τ = N } = ∑ N ∈N S N 1{τ = N } . On a alors
= ∑ ∑ xP( Xn = x; τ ≥ n) ≤ ∑ ∑ xP( Xn = x ) = ∑ E( Xn ).
n ∈N x ∈ Xn ( Ω ) n ∈N x ∈ Xn ( Ω ) n ∈N
/Users/dp/a/ens/[Link] 33
2022-09-18 • 20:20:33.
4.2. Variance et covariance Espérance, variance ; théorèmes des grands nombres
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).
Remarque 4.1.5. Les affirmations de la proposition 4.1.3, établies dans le cas discret,
restent valables dans le cas continu.
Cov( X, Y )
r ( X, Y ) = p .
Var( X )Var(Y )
Démonstration. Exercice !
/Users/dp/a/ens/[Link] 34
2022-09-18 • 20:20:33.
Espérance, variance ; théorèmes des grands nombres 4.3. Fonction génératrice
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 := GX 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−).
Démonstration. La démonstration est triviale si la loi de la variable aléatoire a un support fini. Nous
nous concentrons donc au cas où X prend une infinité de valeurs dans N avec probabilité strictement
positive.
1. Puisque pour z ∈ [0, 1], nous avons G (z) = ∑k≥0 ρ(k)zk , il s’ensuit que G (0) = ρ(0). De même,
pour 0 ≥ z < 1, G 0 (z) = ∑k≥1 ρ(k)kzk−1 et G 0 (0) = ρ(1). Par récurrence, pour0 ≥ z < 1, nous
avons G (n) (z) = ∑k≥n ρ(k)k (k − 1) · · · 1zk−1 et G 0 (0) = k!ρ(k).
2.
G (1) − G ( z ) 1 − zx
1−z
= ∑ ρ( x ) 1 − z = ∑ ρ(x)(1 − zx ) ∑ zk
x ≥1 x ≥1 k ≥0
x −1
= ∑ ρ( x ) ∑ zk , expression bien définie sur [0, 1[.
x ≥1 k =0
En prenant la limite
x −1
G (1) − G ( z )
lim = lim ∑ ρ( x ) ∑ zk
z ↑1 1−z z ↑1 x ≥1 k =0
N x −1
= sup sup ∑ ρ( x ) ∑ zk
z <1 N ≥1 x =1 k =0
N x −1
= sup ∑ ρ(x) sup ∑ zk , car, par monotonie, on peut intervertir les limites
N ≥1 x =1 z <1 k =0
N
= sup ∑ ρ( x ) x
N ≥1 x =1
∞
= sup ∑ ρ(x)xzx−1 , car sup xz x−1 = x.
z <1 x =1 z <1
Si toutes ces expressions restent finies lorsque z = 1, nous avons que EX = limz↑1 G 0 (z) =
G 0 (1−).
/Users/dp/a/ens/[Link] 35
2022-09-18 • 20:20:33.
4.4. Fonction caractéristique Espérance, variance ; théorèmes des grands nombres
3. De même,
G 0 (1−) − G 0 (z)
lim
z ↑1 1−z
= G 00 (1−) = ∑ ρ(x)x(x − 1) ∈ [0, ∞].
x ≥2
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 )
χ 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
/Users/dp/a/ens/[Link] 36
2022-09-18 • 20:20:33.
Espérance, variance ; théorèmes des grands nombres 4.5. Théorèmes des grands nombres
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 [15, Théorème 6.5.2, page 180] ou [47, Théorème 4.2.1, pp. 71–73]
par exemple.
Comme un cas particulier d’un résultat de Cramér [18] 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
ˆ Aˆ A
g( x, A) = f (t − s) exp(i (t − s) x )dtds,
0 0
P( Xi = 1) = P({ω : ωi = 1})
= p ∑ p ∑ k 6 =i ω k (1 − p ) n −1− ∑ k 6 =i ω k
ω1 ,...,ωi−1 ,ωi+1 ,...,ωn
ωk
p
= p (1 − p ) n −1
∑ ∏ 1− p
ω1 ,...,ωi−1 ,ωi+1 ,...,ωn k6=i
= p.
Par conséquent, on calcule de même que P( Xi = 0) = 1 − p. Maintenant, si on note
la somme partielle Sk = X1 + . . . + Xk , pour k = 1, . . . , n, il est immédiat de calculer
/Users/dp/a/ens/[Link] 37
2022-09-18 • 20:20:33.
4.5. Théorèmes des grands nombres Espérance, variance ; théorèmes des grands nombres
Sn
E( Sk ) = ∑ik=1 E( Xi )= pk et par conséquent E = p : l’espérance du nombre
n
moyen de fois où l’on a observé « face » est égale à la probabilité d’obtenir « face » lors
d’une réalisation.
D’un autre côté, on ne peut pas s’attendre à ce que pour tout ε > 0 et tout ω ∈ Ω
S (ω )
on ait | n n − p| < ε. En effet, pour p ∈]0, 1[,
Sn
P =1 = P( X1 = 1, . . . , Xn = 1) = pn
n
Sn
P =0 = P( X1 = 0, . . . , Xn = 0) = (1 − p)n .
n
1 1
En choisissant p = 2 et ε < 2n ,
on voit qu’en notant
Sn ( ω )
As = ω ∈ Ω : = s , s ∈ [0, 1],
n
A1 est un événement avec P( A1 ) = pn 6= 0 (par conséquent non-vide). Pour des ω ∈
S (ω )
A1 , on aura n n − p = 1 − p = 12 ≥ ε.
Nous observons cependant que lorsque n est grand, les probabilités des événe-
ments A0 et A1 sont exponentiellement petites en n, puisque P( A1 ) = pn et P( A0 ) =
(1 − p)n . Il est donc naturel de s’attendre à ce que la probabilité des événements {ω ∈
S (ω )
Ω : | n n − p| > ε} soit petite.
Proposition 4.5.1 (Inégalité de Markov). Soit (Ω, F , P) un espace de probabilité et ξ une
variable aléatoire réelle positive définie sur Ω. Alors
Eξ
∀ε > 0, P(ξ ≥ ε) ≤ .
ε
Démonstration. Nous avons de manière évidente
ξ = ξ1ξ <ε + ξ1ξ ≥ε ≥ ξ1ξ ≥ε ≥ ε1ξ ≥ε .
Par conséquent, E(ξ ) ≥ εP(ξ ≥ ε).
Remarque 4.5.2. L’inégalité de Markov présente un intérêt uniquement si E(ξ ) < ∞.
Corollaire 4.5.3. Soit (Ω, F , P) un espace de probabilité et ξ une variable aléatoire réelle
définie sur Ω. Alors, pour tout ε > 0, on a
E(|ξ |)
P(|ξ | ≥ ε) ≤
ε
E( ξ 2 )
P(|ξ | ≥ ε) ≤
ε2
Var(ξ )
P(|ξ − E(ξ )|) ≥ ε) ≤ (inégalité de Bienaymé-Tchebychev).
ε2
/Users/dp/a/ens/[Link] 38
2022-09-18 • 20:20:33.
Espérance, variance ; théorèmes des grands nombres 4.5. Théorèmes des grands nombres
Lemme 4.5.5. Soient (Ω, F , P) un espace de probabilité et ( Xn )n∈N une suite de variables
aléatoires réelles de carré intégrables (i.e. Xi ∈ L2 (Ω, F , P; R), pour tout i ∈ N) indépen-
dantes et identiquement distribuées. On note m = E( X1 ) l’espérance de l’une d’entre elles,
σ2 = Var( X1 ) la variance de l’une d’entre elles et, pour tout entier k ≥ 0, Sk = ∑ik=1 Xk .
Alors
E(Sk ) = km
Var(Sk ) = kσ2 .
k k k
Var(Sk ) = ∑ Var(Xi ) + ∑ ∑ Cov( Xi , X j ) = kσ2
i =1 i =1 j=1;j6=i
Remarque 4.5.6. Dans le lemme 4.5.5, nous utilisons implicitement le fait que l’es-
pace (Ω, F , P) est suffisamment grand pour contenir dans son intégralité la suite X =
( Xn )n∈N , avec Xk : Ω → X, où (X, X ) est un espace d’événements. Lorsque nous nous
référons aux lois d’une variable aléatoire individuelle, par exemple Xk , nous sous-
entendons que cette loi est la marginale uni-dimensionnelle de la loi conjointe pour
toute la suite :
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
σ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
/Users/dp/a/ens/[Link] 39
2022-09-18 • 20:20:33.
4.5. Théorèmes des grands nombres Espérance, variance ; théorèmes des grands nombres
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 [65,
P
Théorème 2, §III.3, pp. 325–326]). On a alors limn→∞ 1
n ∑nk=1 Xk = E( X1 ).
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
Exercice 4.5.13. (Principe d’une simulation Monte Carlo pour des échantillons indé-
pendants). Soit (Un )n∈N une suite de variables aléatoires indépendantes et identique-
ment distribuées avec la loi uniforme sur l’intervalle [0, 1]. Soit f : [0, 1] → R une appli-
cation de carré intégrable. On construit la suite des sommes partielles Sn = ∑nk=1 f (Uk ).
La suite Snn converge-t-elle en probabilité et si oui vers quoi ? Application : simuler sur
ordinateur avec la suite Snn avec f ( x ) = 1+1x2 .
/Users/dp/a/ens/[Link] 40
2022-09-18 • 20:20:33.
Espérance, variance ; théorèmes des grands nombres 4.6. Théorème central limite
Dans le tableau 4.1 on rappelle les densités ρ de quelques lois usuelles ainsi que
leurs fonctions caractéristiques χ.
Loi de X X ρX χX
Binomiale Bn,p {0, . . . , n} x x
Cn p (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.
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
/Users/dp/a/ens/[Link] 41
2022-09-18 • 20:20:33.
4.7. Exercices Espérance, variance ; théorèmes des grands nombres
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) (voir exercice 54, 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
p.s.
ξ n −→ ξ
P loi
ξ n −→ ξ ξ n −→ ξ
Lp
ξ n −→ ξ
4.7 Exercices
Lois, espérance, variance
40. 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
/Users/dp/a/ens/[Link]
42
2022-11-08 • 17:09:00.
Espérance, variance ; théorèmes des grands nombres 4.7. Exercices
(a) EX,
(b) EY,
(c) Cov( X, Y ),
(d) P( X = 1, Y = 1).
Quelle est votre conclusion ?
41. 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}.
42. 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).
43. 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.
44. 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 quantité relative
à la variable ξ.
45. 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 .
(c) Si ξ + = 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 ; on suppose que
Eξ = Eη = 0 et Varξ = Varη = 1. On note r := r (ξ, η ) le coefficient de corréla-
tion 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 la variable τ est indépendante des
variables aléatoires ( Xn )n∈N . Montrer que la variable aléatoire
τ
Sτ = ∑ Xi
n =1
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).
/Users/dp/a/ens/[Link]
43
2022-11-08 • 17:09:00.
4.7. Exercices Espérance, variance ; théorèmes des grands nombres
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 = 0, . . . , 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, indépendantes et iden-
tiquement distribuée, d’espérance nulle et de variance finie, 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 !)
Fonctions caractéristiques
54. Soient X une variables aléatoire réelle et a, b ∈ R. Montrer que χ aX +b (t) =
χ X ( at) exp(itb).
55. Soient (χn )n∈N une suite de fonctions caractéristiques et (λn )n∈N une suite de
variables positives avec ∑n∈N λn = 1. Monter que ∑n∈N λn χn est encore une
fonction caractéristique.
/Users/dp/a/ens/[Link]
44
2022-11-08 • 17:09:00.
Espérance, variance ; théorèmes des grands nombres 4.7. Exercices
56. Soit la famille (χ j ) j=1,...,n de fonctions caractéristiques. Montrer que ∏nj=1 χ j est
encore une fonction caractéristique.
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) log 11− p.
58. 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 1
∀ε > 0, P − (2p − 1) ≥ ε ≤ 2 exp(− ε2 n).
n 2
/Users/dp/a/ens/[Link]
45
2022-11-08 • 17:09:00.
4.7. Exercices Espérance, variance ; théorèmes des grands nombres
59. Dans une circonscription d’un million d’électeurs les candidats A et B sont en
lice. Parmi ces électeurs, 2000 connaissent bien le candidat A et votent unanime-
ment pour lui. Les autres 998000 choisissent purement au hasard en lançant une
pièce honnête. Minorer la probabilité pour que le candidat A gagne.
60. Soit ( Xn )n∈N une suite de variables aléatoires réelles indépendantes et identi-
quement distribuées, avec E| X1 | < ∞. On note m = EX1 .
(a) Calculer la fonction caractéristique de la variable aléatoire Snn , où Sn = ∑nk=1 Xk .
loi
(b) S’en servir pour montrer que Snn −→ m.
61. 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 ).
D2
(c) Calculer limn→∞ nn .
62. 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 )
.
63. (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éatoires dont on se servira dans
cet exercice.
(a) Soient X et Y deux variables aléatoires indépendantes 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ée 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 identi-
quement distribueé 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] 46
2022-09-18 • 20:20:33.
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.8. 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.
47
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
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.
Remarque 5.1.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). Il ne faut pas confondre
la notation PX , signifiant la loi d’une variable aléatoire X, avec Px , signifiant la loi sur
l’espace des trajectoires avec démarrage initiale déterministe ρ0 = ε x . En fait, Px dé-
signe la loi conjointe PX de la suite infinie X = ( X0 , X1 , . . .) conditionnée à l’évènement
{ X0 = x } .
Exemple 5.1.3. 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 = 2 2 . L’étude du comportement
2 1
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 67.
/Users/dp/a/ens/[Link] 48
2022-10-11 • 21:26:10.
Chaînes de Markov 5.2. Temps d’arrêt. Propriété forte de Markov
Théorème 5.1.4. 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 } ,
nous avons
P( A ∩ C | B ) = P( A | B )P( C | B ).
Démonstration. Exercice.
Exemple 5.2.2. Soit ( Xn )n∈N le relevée de température (en degrés Celsius avec une
décimale) à l’ombre dans un lieu donné à midi du jour n (où n = 0 correspond au
jour où des éphémérides ont commencé à exister). Soit T1 := inf{n ≥ 0 : Xn = 42.2}
et T2 := inf{n ≥ 0 : Xn est la température maximale jamais enregistrée en ce lieu}.
Évidemment T1 est un temps d’arrêt mais pas T2 . Qu’en est-t-il de T3 := inf{n ≥ 0 :
Xn > maxk=0,...,n−1 Xk } ?
Définition 5.2.4. Soit ( Xn ) ∈ CM(X, P, ρ0 ) définie sur (Ω, F , P). Pour tout A ∈ X , on
note
(1)
τA0 := inf{n ≥ 0 : Xn ∈ A} ∈ N ∪ {+∞} et τA = τA := inf{n > 0 : Xn ∈ A} ∈ N ∪ {+∞}
les temps de premier retour et temps de première entrée de la chaîne dans l’ensemble
A. Lorsque A = {y}, nous simplifions la notation en τy0 au lieu de τ{0y} (et de même
pour τ{y} ).
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.
1. En termes plus précis, si on note Fn = ⊗nk=0 X , et si { T = n} ∈ Fn pour tout n, on dit que T
est un (Fn )-temps d’arrêt. La suite des tribus (Fn ) est une suite croissante, appelée filtration naturelle
de la chaîne. Pour tout n ∈ N, la tribu Fn est la plus petite tribu qui rend les variables ( X0 , . . . , Xn )
(simultanément) mesurables.
/Users/dp/a/ens/[Link] 49
2022-10-11 • 21:26:10.
5.3. Classification des états ; récurrence, transience Chaînes de Markov
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] 50
2022-10-11 • 21:26:10.
Chaînes de Markov 5.3. Classification des états ; récurrence, transience
où [ x ] = {y ∈ Xe : x ↔ y}.
Démonstration. Exercice.
Définition 5.3.4. 1. Un ensemble d’états A ⊆ X est dit absorbant (ou stochasti-
quement fermé) si A 6= ∅ et pour x ∈ A ⇒ ∑y∈ A Px,y = 1.
2. Si pour un x ∈ X, on [ x ] = X, la chaîne est dite irréductible, i.e. ∀( x, y) ∈
X2 , ∃n := n( x, y) ≥ 1 : Px,y
n > 0.
N = α >
3. La chaîne est dite fortement irréductible si ∃ N > 0, ∃α > 0 : minx,y Px,y
0.
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
/Users/dp/a/ens/[Link] 51
2022-10-11 • 21:26:10.
5.3. Classification des états ; récurrence, transience Chaînes de Markov
1
3. Pour |z| < 1, on a R(z) = 1− Q ( z )
.
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
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 = 1 − |z| , et
n ≥0 n ≥0
| Q(z)| ≤ ∑ qn |z| n
≤ ∑ qn = Px (τx < ∞) ≤ 1.
n ≥0 n ≥0
1
Puisque r0 = 1, on conclut que R(z) = 1− Q ( z )
.
Démonstration. Immédiate.
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 < ∞.
/Users/dp/a/ens/[Link] 52
2022-10-11 • 21:26:10.
Chaînes de Markov 5.4. Probabilité limite, probabilité invariante (stationnaire)
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
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.
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
/Users/dp/a/ens/[Link] 53
2022-10-11 • 21:26:10.
5.4. Probabilité limite, probabilité invariante (stationnaire) Chaînes de Markov
∑ 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 N
( x, y) − P ( x , y)] + 0
∑ [ 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
+
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+1 , pour k ∈ N arbitraire ; en combi-
nant 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 .
Définition 5.4.2. La probabilité µ(y) = limn→∞ Px ( Xn = y) = limn→∞ Pn ( x, y) est
appelée probabilité limite. Le vecteur propre gauche, π, de P associé à la valeur propre
1 est appelé probabilité invariante (ou stationnaire).
Corollaire 5.4.3. Sous les conditions du théorème 5.4.1, le vecteur (ligne) de probabilité limite
µ est égale à 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).
/Users/dp/a/ens/[Link] 54
2022-10-11 • 21:26:10.
Chaînes de Markov 5.4. Probabilité limite, probabilité invariante (stationnaire)
/Users/dp/a/ens/[Link] 55
2022-10-11 • 21:26:10.
5.5. Stationnarité, réversibilité Chaînes de Markov
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 ) .
Démonstration. Par réversibilité, les lois de ( Xt1 , . . . , Xtn ) et de ( XT +t1 , . . . , XT +tn ) sont
les mêmes que la loi de ( X−t1 , . . . , X−tn ), car la loi de ( XT +t1 , . . . , XT +tn ) est égale à la
loi de ( XS−T −t1 , . . . , XS−T −tn ), pour tout S ∈ Z. Il suffit donc de choisir S = T.
Théorème 5.5.4. Soit ( Xn ) une MC(X, P, π ) irréductible et ayant π comme probabilité in-
variante. Pour un N ∈ N, on pose Yn = X N −n pour n = 0, . . . , N. Alors (Yn ) est une chaîne
de Markov (à horizon fini). Si la matrice Q est définie par
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 ).
1 π (y)
∑ Qyx =
π (y) ∑ π ( x ) Pxy =
π (y)
= 1.
x ∈X x ∈X
/Users/dp/a/ens/[Link] 56
2022-10-11 • 21:26:10.
Chaînes de Markov 5.5. Stationnarité, réversibilité
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.
Si un tel vecteur de probabilité existe, alors π est la probabilité invariante de la chaîne.
Démonstration. Supposons le processus réversible. Puisqu’il est stationnaire, sa margi-
nale πt à l’instant t est constante en t, i.e. π ( x ) = P( Xt = x ). La réversibilité impose
alors : P( Xt = x, Xt+1 = y) = P( Xt = y, Xt+1 = x ), ou
π ( x ) P( x, y) = π (y) P(y, x ), ∀ x, y ∈ X.
Réciproquement, supposons qu’un vecteur de probabilité π, vérifiant la condition
de bilan détaillé existe. Il est alors de toute évidence une probabilité invariante pour le
processus. Nous aurons alors
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 [22]). 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.
/Users/dp/a/ens/[Link] 57
2022-10-11 • 21:26:10.
5.6. Théorème des grands nombres pour les chaînes de Markov Chaînes de Markov
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
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
/Users/dp/a/ens/[Link] 58
2022-10-11 • 21:26:10.
Chaînes de Markov 5.6. Théorème des grands nombres pour les chaînes de Markov
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 |) < ∞.
Alors
1 n Ex ( f ( X1 ) + . . . + f ( Xτx1 )
lim
n→∞ n
∑ f ( Xk ) =
Ex τx1
, Px − p.s.
k =0
Si la chaîne est irréductible, la convergence est presque sûre indépendamment de la condition
initiale.
Démonstration. Pour x ∈ X et n ∈ N, définir le nombre de visites de la chaîne au point x avant le temps
n
n
ηn ( x ) = ∑ 1{x} (Xk ) = sup{r ≥ 1 : τxr ≤ n}.
k =1
τx1 τx1
| ∑ f ( Xk )| ≤ ∑ | f (Xk )|
k =0 k =0
et la dernière somme est intégrable (par hypothèse), donc presque sûrement finie.
La deuxième somme partielle peut se réécrire
ηn ( x ) ηn ( x )
1 ηn ( x ) 1
n ∑ Zr =
n ηn ( x ) ∑ Zr .
r =1 r =1
ηn ( x )
1
lim
n ηn ( x ) ∑ Zr = Ex ( Z1 )
r =1
famille ( Xτxr +n )n∈N est une MC(X, P, ε x ) et, en outre, la loi conjointe de ( Xτxr +n )n∈N est indépendante de
( X0 , . . . , Xτxr −1 ). On note σxr := τxr+1 − τxr le temps qui s’écoule entre deux retours successifs (r et r + 1)
au point x. On a
η ( x )−1 η (x)
σx1 + . . . + σx n ≤ n − 1 ≤ n ≤ σx1 + . . . + σx n .
En divisant ces inégalités par ηn ( x ), on obtient :
η ( x )−1 η (x)
σx1 + . . . + σx n n σ1 + . . . + σx n
≤ ≤ x .
ηn ( x ) ηn ( x ) ηn ( x )
Chacun des termes aux extrémités des inégalités précédentes converge (par la loi forte de grands nombres
et la propriété forte de Markov) presque sûrement vers Ex (σx1 ) = Ex (τx1 ). Par conséquent limn→∞ η n( x) =
n
Ex (τx1 ).
ηn ( x )+1
1
∑k=
τx
Reste à montrer que le terme de correction Rn = n n+1 f ( Xk ) tendra vers 0 ce qui est garanti
par la condition Ex (| f ( X1 )| + . . . + | f ( Xτx1 |) < ∞.
/Users/dp/a/ens/[Link] 59
2022-10-11 • 21:26:10.
5.7. Exemples d’applications algorithmiques Chaînes de Markov
/Users/dp/a/ens/[Link] 60
2022-10-11 • 21:26:10.
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] 61
2022-10-11 • 21:26:10.
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
64. 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]
62
2022-11-15 • 19:54:13.
Chaînes de Markov 5.8. Exercices
Px,y = x+ 1
1 si x ∈ X, y = x + 1
0 sinon.
(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.
67. (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]
63
2022-11-15 • 19:54:13.
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
le groupe diédral
π
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]
64
2022-11-15 • 19:54:13.
Chaînes de Markov 5.8. Exercices
(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 . Plus précisément, montrer que pour toute paire y, z ∈ Xmsr , on a
1
N ∑ ρ( g)1{z} ((k, g)y)
si z 6= y,
(k,g)
P(y, z) = 1 1
N ∑ ρ( g)1{y} ((k, g)y) +
N ∑ ρ( g)1Xmas \Xmsr ((k, g)y) si z = y.
(k,g) (k,g)
(b) Montrer que pour tout entier N ≥ 2, la matrice P est stochastique, bistochas-
tique, irréductible et apériodique.
(c) Conclure que P admet la mesure uniforme sur Xmsr comme mesure d’équi-
libre.
/Users/dp/a/ens/[Link] 65
2022-10-11 • 21:26:10.
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] 66
2022-10-11 • 21:26:10.
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 1 , avec |Π| ≥ 2 pour éviter les tri-
vialité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éalisa-
tions (observations) de la variable aléatoire X et nous voulons, à partir des observations
inférer 2 la loi qui a servi à générer les réalisations de X.
67
6.1. Motivation Notions de statistique
Exemple 6.1.1. On note (X, X , Π) le triplet qui permet de poser le problème d’infé-
rence.
1. Lorsque X = {0, 1} muni de sa tribu exhaustive, on peut s’intéresser à la famille
Dans ce cas simple, la famille Π = (Pθ )θ ∈Θ , avec Θ = [0, 1], coïncide avec
M1 (X, X ). On veut, à partir d’un échantillon X1 , . . . , Xn inférer la valeur de θ.
On peut aussi identifier Pθ avec la densité discrète (par rapport à la mesure de
dénombrement) f θ qui vaut
f θ ( x ) = θ x (1 − θ )1− x , x ∈ X, θ ∈ Θ.
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) Θ,
partie 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] 68
2022-12-06 • 18:15:34.
Notions de statistique 6.2. Estimation paramétrique
Une question pertinente est la suivante : puisqu’une statistique est une variable
aléatoire sur Xn à valeurs dans Y pourquoi introduisons-nous un nouveau terme ? La
réponse est que l’usage que nous en ferons de S engendrera une intuition différente de
celle développée pour des variables aléatoires « ordinaires ».
Lemme 6.2.3.
EQMθ (θ̂n ) = bθ (θ̂n )2 + Varθ (θ̂n ).
/Users/dp/a/ens/[Link] 69
2022-12-06 • 18:15:34.
6.2. Estimation paramétrique Notions de statistique
θ̂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.
Définition 6.2.5. Soient un modèle statistique (X, X , ( f θ )θ ∈Θ ), X(n) = ( X1 , . . . , Xn )
une famille indépendante de variables aléatoires à valeurs dans X, identiquement dis-
tribuées selon une loi de densité (discrète ou continue) f θ . On définit les statistiques
suivantes :
vraisemblance : Ln (θ ) := Ln (θ, X(n) ) = ∏in=1 f θ ( Xi ),
log-vraisemblance : ln (θ ) = log Ln (θ ),
estimateur du maximum de vraisemblance : θ̂nMV := arg max Ln (θ ) = arg max ln (θ ).
Exemple 6.2.6. Soit X(n) = ( X1 , . . . , Xn ) une famille de variables aléatoires indépen-
dantes et identiquement distribuées.
— Si X1 suit la loi de Bernoulli(θ ) avec θ ∈ [0, 1], l’estimateur du maximum de
vraisemblance θ̂nMV coïncide avec la moyenne empirique θ n .
— Si X1 suit une loi normale de paramètres θ := (m, s2 ), l’estimateur de maximum
de vraisemblance est θ̂nMV = (mn , vn ), où l’estimateur de maximum de vraisem-
blance pour m coïncide avec la moyenne emprique θ̂n,1 = mn et
1 n
n i∑
vn = ( Xi − m n ) 2
=1
/Users/dp/a/ens/[Link] 70
2022-12-06 • 18:15:34.
Notions de statistique 6.2. Estimation paramétrique
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 (Fk est tabulée).
/Users/dp/a/ens/[Link] 71
2022-12-06 • 18:15:34.
6.2. Estimation paramétrique Notions de statistique
Le paramètre α est aussi appelé taille de la région critique tandis que le paramètre
1 − β est appelé puissance.
On souhaiterait minimiser la probabilité de prendre une décision erronée :
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
3. Il serait plus cohérent de les appeler erreurs d’ordre 0 et 1 respectivement mais, pour des raisons
historiques, on garde la nomenclature type I et II.
/Users/dp/a/ens/[Link] 72
2022-12-06 • 18:15:34.
Notions de statistique 6.2. Estimation paramétrique
En décomposant
R = ( R ∩ S ) t ( R ∩ S c ),
S = ( S ∩ R ) t ( S ∩ R c ),
nous avons
ˆ ˆ ˆ ˆ
L0 (x)dx + L0 (x)dx = L0 (x)dx + L0 (x)dx
R∩S R∩Sc R∩S S∩ Rc
ou ˆ ˆ
L0 (x)dx = L0 (x)dx.
R∩Sc S∩ Rc
Par ailleurs, sur R, nous avons L1 ≥ Lδ0 tandis que sur Rc , nous avons L1 < L0
δ . On
conclut que
ˆ ˆ ˆ ˆ
L0 ( x ) L0 ( x )
L1 (x)dx ≥ dx = dx ≥ L1 (x)dx.
R∩Sc R∩Sc δ S∩ Rc δ S∩ Rc
/Users/dp/a/ens/[Link] 73
2022-12-06 • 18:15:34.
6.2. Estimation paramétrique Notions de statistique
où, pour tout j ∈ K, on pose νj := νj (X(n) ) = ∑in=1 1Xj ( Xi ). Il est évident que νj /n
représente la fréquence empirique avec laquelle la classe j ∈ K est chargée par l’échan-
tillon. Par ailleurs, chaque Pθ de la population induit un vecteur de probabilité p :=
pθ ∈ VPK , où
k
VPK = {p ∈ Rk>+1 : ∑ p ( i ) = 1}.
i =0
i.e. on suppose que pour tout i ∈ K, on a pi > 0. Par le théorème de grands nombres
νi (X(n) )
lim = P θ ( Xi ) = p i .
n→∞ n
Ce résultat permet d’affirmer que composante par composante, νi /n est un estimateur
de pi . Or les paramètres ( pi )i∈K ne sont pas libres car elles vérifient l’égalité ∑i pi = 1.
Nous voulons cependant une approche qui permet de former un estimateur simultané
pour toutes les composantes du vecteur de probabilité. Pour cela nous utiliserons l’es-
timateur du maximum de vraisemblance. Pour tout vecteur de probabilité q ∈ VPK ,
on introduit la fonction de vraisemblance
ν (X(n) )
Ln (q) := Ln (q, X(n) ) = ∏ qi i
i ∈K
/Users/dp/a/ens/[Link] 74
2022-12-06 • 18:15:34.
Notions de statistique 6.3. Exercices
(νi − npi )2
Qn = ∑ npi
i ∈K
P( Z > χ2k,α ) = α.
6.3 Exercices
Estimation ponctuelle
70. Montrer que la variance empirique, définie par :
n 2
1
V n ( X(n) ) : = ∑
n − 1 i =1
Xi − m n ( X ( n ) ) ,
Intervalles de confiance
74. Le but de cet exercice est de démontrer une amélioration — connue sous le nom
d’inégalité de Hoeffding — de l’inégalité obtenue en exercice 58.
/Users/dp/a/ens/ptin-td-stati-linked.tex75
2022-06-22 • 17:02:43.
6.3. Exercices Notions de statistique
(a) Utiliser l’inégalité de Markov pour montrer que, pour tout t > 0,
n n
P( ∑ Xi ≥ ε) ≤ exp(−tε) ∏ E exp(tXi ).
i =1 i =1
(b) Montrer que l’on peut écrire, pour tout i ∈ N, la variable aléatoire Xi comme
une combinaison convexe aléatoire, i.e.
[ a i , bi ] 3 X i = ( 1 − ξ i ) a i + ξ i bi
pour une variable aléatoire ξ i que l’on exprimera en fonction de Xi .
(c) Utiliser la convexité de t 7→ exp(tx ), pour x ∈ R arbitraire fixé, pour ma-
jorer exp(tXi ) en se servant de la décomposition convexe de Xi , établie à la
question précédente.
(d) Utiliser le centrage des variables aléatoires (EXi = 0), pour exprimer E exp(tXi ) =
exp( g(ui )), où ui = t(bi − a1 ) et g(u) = −ci ui + log(1 − ci + ci exp(ui )) et
ai
ci = − b − .
i ai
(e) Calculer g(0), g0 (0) et montrer que pour tout v > 0, g00 (v) ≤ 1/4.
(f) On rappelle que pour toute fonction g ∈ C2 (R), et pour tout u > 0, il existe
2
v ∈ [0, u] tel que g(u) = g(0) + ug0 (0) + u2 g00 (v). S’en servir pour conclure
2
que E exp(tXi ) ≤ exp( g(ui )) ≤ exp( t8 (bi − ai )2 ).
75. Soit ( Xi )i∈N une suite indépendante et identiquement distribuée selon la loi
Bernoulli(θ ), avec θ ∈ [0, 1].
q
1
(a) Soient α ∈]0, 1[ et ε n = 2n log α2 . Noter mn la moyenne empirique et
Cn =]mn − ε n , mn + ε n [∩[0, 1]
la troncature éventuelle de l’intervalle aléatoire de longueur 2ε n et de centre
aléatoire θ̂n induite par son intersection avec l’intervalle [0, 1]. Montrer que
Pθ (Cn 3 θ ) ≥ 1 − α.
(b) Effectuer l’expérience suivante sur ordinateur. Fixer α = 0.05, θ = 0.4 et
générer un échantillon ( Xi )i=1,...,10000 .
(c) Déterminer pour tout j = 1, . . . , 10000, les bords de l’intervalle Cj .
(d) Calculer la suite Kn = ∑in=1 1Ci (θ ) pour n = 1, . . . , 10000 et présenter les
couples (n, Kn ) et (n, |Cn |) pour n = 1, . . . , 10000.
Tests d’hypothèses
/Users/dp/a/ens/[Link] 76
2022-12-06 • 18:15:34.
Deuxième partie
Théorie de l’information
77
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.
79
7.1. Postulats d’une quantité d’incertitude, entropie Quantification de l’information
]0, 1] 3 p 7→ h( p) ∈ R.
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.
1
p( x ) = M , pour tout x = X, où |X| = M, et notons f ( M) = H M (( M 1 1
,..., M )) la valeur
de l’incertitude moyenne associée dans ce cas d’équidistribution. 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 inhérente d’un tirage du loto, i.e. f (2) < f (1.3 × 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 ).
/Users/dp/a/ens/[Link] 80
2022-09-06 • 16:25:42.
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 ),
log 2 f (2) 1
− < .
log M f ( M) r
Puisque M est fixé tandis que r est arbitraire, nous avons
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] 81
2022-09-06 • 16:25:42.
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
H M (p) = H2 ((q, p M )) + qH M−1 (( 1 , . . . , M−1 )) + p M H1 ((1))
q q
" #
M −1
pi pi
= −C q log q + p M log( 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] 82
2022-09-06 • 16:25:42.
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] 83
2022-09-06 • 16:25:42.
7.2. Trois interprétations de l’entropie Quantification de l’information
/Users/dp/a/ens/[Link] 84
2022-09-06 • 16:25:42.
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 [9], 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, quoiqu’obtenue par une méthode différente de celle utilisée par Shannon. 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 [10].
/Users/dp/a/ens/[Link] 85
2022-09-06 • 16:25:42.
7.2. Trois interprétations de l’entropie Quantification de l’information
∈ X = x2
X { x1 , x2 } ?
non (0.4) [2, 0.5 · 0.4]
oui (0.4)
= x3 ? X = x3
non (0.5) [2, 0.5 · 0.4]
non (0.6)
oui (0.5) X = x4
= x4 ?
[3, 0.5 · 0.6 · 0.5]
X = x5
non (0.5) [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.
E( N ) = 2 · [0.5 · 0.6 + 0.5 · 0.4 + 0.5 · 0.4] + 3 · [0.5 · 0.6 · 0.5 + 0.5 · 0.6 · 0.5]
= 2 · [0.3 + 0.2 + 0.2] + 3 · [0.15 + 0.15]
= 2.3.
Par ailleurs, nous pouvons calculer l’entropie de p :
H (p) = −0.3 log 0.3 − 0.4 log 0.2 − 0.3 log 0.15 = 2.27.
/Users/dp/a/ens/[Link] 86
2022-09-06 • 16:25:42.
Quantification de l’information 7.2. Trois interprétations de l’entropie
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.
observe que dans ce cas H (p) = 0.88 tandis que E( N ) = 1 et il semble que nous ne
pouvons pas faire mieux que cela. En fait, il est possible de faire mieux. Supposons
en effet qu’au lieu de considérer une variable aléatoire X, nous considérons une paire
Z = ( X1 , X2 ) de deux copies indépendantes de X, i.e. la variable aléatoire Z prend de
valeurs dans {( x1 , x1 ), ( x1 , x2 ), ( x2 , x1 ), ( x2 , x2 )} ; sa loi sera décrite par le vecteur de
probabilité q = (0.49, 0.21, 0.21, 0.09). On peut construire facilement un schéma de dé-
cision des valeurs que prend la variable aléatoire Z avec E( N ) = 1.81. (Construisez ce
schéma). Cependant, ce schéma permet de déterminer une paire indépendante de va-
riables aléatoires X, donc l’espérance du nombre de questions par variable aléatoire est
0.905, plus proche de l’entropie que la valeur 1 déterminée précédemment. Nous pou-
vons continuer ce procédé avec des triplets, quadruplets, etc. de variables aléatoires ;
chaque fois nous obtiendrons une espérance du nombre de questions par variable qui
s’approche de H (p). L’exercice 86e montre que l’espérance du nombre de questions
par variable converge en décroissant vers l’entropie de la loi de l’une d’entre elles mais
il n’existe pas de schéma permettant de faire mieux que la barrière de l’entropie.
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 (α) =
6. Si M = cardA, sans perte de généralité, nous pouvons supposer que A ' {1, . . . , M} et que
p = ( pi )i=1,...,M .
/Users/dp/a/ens/[Link] 87
2022-09-06 • 16:25:42.
7.2. Trois interprétations de l’entropie Quantification de l’information
∑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 :
1 (n)
nν (α) ∈ PVA ; ce vecteur de probabilité est appelé type de la suite α.
(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 :
Définition 7.2.2. Soient un entier n ≥ 1, un alphabet fini A, un vecteur de probabilité
p ∈ PVcardA et un entier K > 0. Une suite α ∈ An est dite typique (plus précisément
(n, p, K )-typique) si
(n)
νa (α) − np a
∀ a ∈ A, p < K,
np a (1 − p a )
sinon, elle est appelée atypique. L’ensemble
/Users/dp/a/ens/[Link] 88
2022-09-06 • 16:25:42.
Quantification de l’information 7.3. Propriétés de la fonction entropie, entropie relative
(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.
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] 89
2022-09-06 • 16:25:42.
7.3. Propriétés de la fonction entropie, entropie relative Quantification de l’information
qa qa
∑ p a ln
pa
≤ ∑ pa (
pa
− 1) = ∑ ( pa − qa ) = 0.
a ∈A a ∈A a ∈A
Pour deux vecteurs de probabilité p et q sur le même alphabet A, on dit que p est
absolument continu par rapport à q, et l’on note p q, si p a = 0 pour tout a ∈ A tel
que q a = 0, i.e. si q a = 0 implique que p a = 0.
Définition 7.3.5. Soient (X, p) et (Y, q) deux espaces probabilisés finis (munis de leurs
tribus exhaustives) avec X ⊆ Y. On dit que (Y, q) est une fragmentation de (X, p)
(ou que (X, p) est une coalescence de (Y, q)) si on peut partitioner Y = t x∈X Yx , de
sorte que pour tout x ∈ X, on a p( x ) = ∑y∈Yx q(y).
Proposition 7.3.6. Pour i = 0, 1, on suppose que (Y, qi ) sont des fragmentations de (X, pi ).
Alors
D ( q0 k q1 ) ≥ D ( p0 k p1 ),
en d’autres termes, la fragmentation augmente le contraste de Kullback-Leibler.
/Users/dp/a/ens/[Link] 90
2022-09-06 • 16:25:42.
Quantification de l’information 7.4. Entropie des évolutions markoviennes
q0 ( y ) p0 ( x )
D ( q0 k q1 ) − D ( p0 k p1 ) = ∑ q0 (y) log q1 (y) − ∑ p0 ( x ) log
p1 ( x )
y ∈Y x ∈X
q0 ( y ) p (x)
= ∑ ∑ q0 (y) log
q1 ( y )
− q0 (y) log 0
p1 ( x )
x ∈X y ∈Y x
q0 ( y ) p1 ( x )
= ∑ ∑ q0 (y) log
q1 ( y ) p0 ( x )
x ∈X y ∈Y x
q ( y ) p0 ( x ) 1
≥ ∑ ∑ q0 ( y ) − q0 ( y ) 1
q0 ( y ) p1 ( x )
(car log t ≥ 1 − )
t
x ∈X y ∈Y x
= 0.
Soit ( Xt )t∈N une chaîne de Markov irréductible et apériodique sur un espace dé-
nombrable X (muni de sa tribu exhaustive X ) et de matrice stochastique P. On note π
sa probabilité d’équilibre, vérifiant π = πP et µn (y) := Pρ ( Xt = y) pour une probabi-
lité initiale ρ ∈ M1 (X) fixée.
Supposons que f : R+ → R soit une fonction mesurable strictement concave et,
pour n ∈ N,
µn (y)
Fn = ∑ π (y) f π (y)
.
y ∈X
Théorème 7.4.1. Sous le conditions ci-dessus, la suite des fonctions Fn est strictement crois-
sante en n.
/Users/dp/a/ens/[Link] 91
2022-09-06 • 16:25:42.
7.4. Entropie des évolutions markoviennes Quantification de l’information
π (y) P(y,x )
π (x)
le noyau de la chaîne renversée dans le temps, nous avons
µ n +1 ( y )
u n +1 ( x ) =
π (y)
P(z, x )
= ∑ µn (z) π (x)
z ∈X
µn (z) P(z, x )
= ∑ π (z)
π (z)
π (x)
z ∈X
= ∑ P̂(x, z)un (z).
z ∈X
!
f (un+1 ( x )) = f ∑ P̂(x, z)un (z)
z ∈X
> ∑ P̂(x, z) f (un (z)) (à cause de la stricte concavité de f ).
z ∈X
Fn+1 = ∑ π ( x ) f (un+1 ( x ))
x ∈X
π (z) P(z, x )
> ∑ π (x)
π (x)
f (un (z))
x,z∈X
= ∑ π (z) f (un (z)) (car ∑ P(z, x ) = 1 ).
z ∈X x
= Fn .
/Users/dp/a/ens/[Link] 92
2022-09-06 • 16:25:42.
Quantification de l’information 7.5. Couples de variables aléatoires
/Users/dp/a/ens/[Link] 93
2022-09-06 • 16:25:42.
7.5. Couples de variables aléatoires Quantification de l’information
H (Y | X ) = ∑ H (Y | X = x ) P ( X = x ) .
x ∈X
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 ) .
/Users/dp/a/ens/[Link] 94
2022-09-06 • 16:25:42.
Quantification de l’information 7.6. Registres de stockage de l’information
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] 95
2022-09-06 • 16:25:42.
7.6. Registres de stockage de l’information Quantification de l’information
Exemple 7.6.3. (Un registre idéal vu comme un objet mathématique abstrait). Sup-
posons A = X = {0, 1}, avec X équipé de sa tribu exhaustive. Les mesures de pro-
babilité extrémales sont les mesures qui n’admettent pas de décomposition convexe
non-triviale en d’autres mesures de probabilité. Il est aussi évident que {ε x , x ∈ X} ⊆
∂e M1 (X, X ). Cette inclusion devient une égalité si l’espace (X, X ) est séparable, ce qui
est effectivement la cas dans la situation présente.
De façon abstraite (i.e. en négligeant les contraintes de la réalisation physique), un
registre idéal 8 est l’application définie par la formule x 7→ R( x ) := {ε x } pour tout
x ∈ X. Lorsque x 6= y,
D (ε x kε y ) = +∞,
par conséquent les lettres x et y sont réalisées par deux mesures de probabilité unique-
ment définies et parfaitement discernables.
Exemple 7.6.4. (Un registre idéal vu comme un objet physique). Sous la même notation
que dans l’exemple 7.6.3, i.e. A = X = {0, 1}, associer avec l’état logique ‘0’, une
pièce totalement biaisée avec deux cotés « face » et avec l’état logique ‘1’, une pièce
totalement biaisée avec deux cotés « pile ». Ce système remplit les conditions pour qu’il
soit considéré comme registre ; il implémente physiquement la notion mathématique
abstraite de registre. Cependant, un tel système est totalement inutile pratiquement car
le codage des états logiques se fait en dur dans la construction de la pièce qui empêche
la transformation de 0 en 1 par l’action d’une opération raisonnable sur le système.
Bien sûr, il est toujours possible de faire fondre la pièce pour en frapper une nouvelle
avec un côté « pile » et un côté « face », une opération qui n’est pas très pratique pour
stocker, extraire et traiter l’information sur un ordinateur !
La discernabilité parfaite est une exigence trop forte pour qu’elle soit physiquement
implémentable. Pour cette raison, la définition 7.6.1 assouplit la condition de discerna-
bilité parfaite en la condition de discernabilité au dessus d’un certai seuil θ > 0, en
déclarant deux mesures µ et ν dans M1 (X) comme discernées (au seuil θ ∈ ]0, ∞[)
si θ ≤ D (µkν). Or, si le contraste n’est pas infini, les deux mesures ne peuvent pas
être mutuellement singulières ; par conséquent, elles ne peuvent pas être des masses
de Dirac masses supportées par des lettres différentes. Il est donc nécessaire de consi-
dérer pas seulement des mesures extrémales mais aussi des mesures générales dans
M1 (X) = co({ε x , x ∈ X}).
Une difficulté supplémentaire surgit lorsqu’on relaxe la condition de stricte dis-
cernabilité. Tandis que l’ensemble des probabilités extrémales ∂e M(X) est en bijec-
tion avec l’ensemble des états logiques X, l’ensemble M1 (X) est beaucoup plus grand
que X. En outre, puisque la discrimination est faite à l’aide du seuil θ > 0, l’image
R(A) = t a∈A R( a) ne couvre pas M1 (X). Puisqu’alors M1 (X) \ R(A) 6= ∅, il existe
d’états physiques qui ne correspondent pas à des états logiques ; lorsque le système
est préparé dans l’un de ces états, son état logique reste indéterminé. Moyennant l’ex-
tension de l’alphabet A en Au par adjonction d’une nouvelle lettre Au := A t {∂},
l’application R peut être conçue comme l’application de l’alphabet étendu dans les
classes d’équivalence des mesures de probabilité sur X, engendrée par la partition
M1 (X) = t a∈Au R( a), où R(∂) = M1 (X) \ R(A).
Le contraste de Kullback-Leibler n’est pas de maniement facile pour discriminer
le codage de différentes lettres pour des alphabets à trois lettres ou plus. La distance
8. I.e. qui discerne parfaitement les états physiques p.
/Users/dp/a/ens/[Link] 96
2022-09-06 • 16:25:42.
Quantification de l’information 7.7. Irreversibilité et principe de Landauer
Figure 7.5 – Gauche : D (pkq) pour p = ( p, 1 − p), q = (q, 1 − q), comme fonction de
p, q ∈ ]0.05, 0.95[. Les intersections avec les plans horizontaux à hauteur θ ∈ {0.1, 0.2, . . . , 1.9, 2.0}
sont représentées par les courbes rouges sur la surface. Milieu : Projection de la surface précédente sur
me plan horizontal (à hauteur 0) ; elle permet de visualiser les courbes de niveau à hauteur θ. Si nous
fixons le seuil de discrimination à θ = 0.1, la région interne (« lac » coloré en bleu clair) correspond à
la classe d’équivalence des états physiques R(∂) provenant de l’état logique indéterminé ∂. La région
gauche supérieure (au delà de la rive nord-ouest du lac) correspond à la classe d’équivalence R(1)
des états physiques provenant de l’état logique 1, la région droite inférieure (au delà de la rive sud-
est du lac) à la classe d’équivalence R(0) provenant de l’état logique 0. Droite : Intersection de la
surface descrvant D (pkq) avec le plan vertical q = 1 − p. Nous remarquons que quand p = 1/2,
les vecteurs p = ( p, 1 − p) et q = (1 − p, p) coïncident ; par conséquent leur contraste s’annule et
les vecteurs deviennent indiscernables. Les probabilités peuvent être discriminées efficacement lorsque
leur contraste excède un certain seuil, ex. 0.1.
9. Le lecteur intéressé peut consulter les livres [25, 34] pour des détails techniques.
/Users/dp/a/ens/[Link] 97
2022-09-06 • 16:25:42.
7.7. Irreversibilité et principe de Landauer Quantification de l’information
εa εa
R( a)
ρ1
ρ0
ρ2
R(b) R(c)
εb εc εb εc
Figure 7.6 – Gauche : L’ensemble convexe des états M1 ({ a, b, c}) et exemples de boules (pour
la distance de variation totale) de rayon δ = 0.1 autour des états ρ0 = 31 (ε a + ε b + ε c ), ρ1 =
1
2 ( ε a + ε b ) et ρ2 = 0.2ε a + 0.3ε b + 0.5ε c . Droite : Partition de l’ensemble des états en régions
disjointes R( a), R(b), R(c) codant les lettres a, b, c ∈ X et région tampon (orange) d’épaisseur 0.1,
correspondant à l’état indéterminé ∂. Cette région est obtenue comme enveloppe convexe de toutes
les boules de rayon δ = 0.1 centrées autour des états entre ρ0 et 21 (ε a + ε b ), entre ρ0 et 12 (ε b + ε c )
et entre ρ0 et 12 (ε c + ε a ). Les régions R( a), R(b) et R(c) sont des ensembles disjoints provenant de
la complémentation de la région tampon ; elles correspondent aux classes d’équivalence [ε a ], [ε b ] et
[ε c ] d’états qui peuvent sans ambiguïté être associés (à seuil de discernabilité that can be θ = 0.1)
aux lettres a, b et c respectivement.
/Users/dp/a/ens/[Link] 98
2022-09-06 • 16:25:42.
Quantification de l’information 7.7. Irreversibilité et principe de Landauer
Puisque l’ordre des lettres dans le mot b est sans importance, b est bijectivement re-
présenté par le vecteur d’occupation :
B 3 b 7 → ρ b ∈ M1 (A),
où
N
1
ρb ( a) =
N ∑ 1 { a } ( bi ) .
k =1
N −r
· · 0} 1| ·{z
Autrement dit, le mot b = [0| ·{z · · 1}] engendre le vecteur ρb = ( Nr , N ). Soit
r N −r
(Ω, F , P) un espace de probabilité (suffisamment grand). Nous introduisons le va-
riable aléatoire U : Ω → {1, . . . , N } et une famille paramétrique de variables aléatoire
X : B × Ω → A, où U est uniformement distribuée sur {1, . . . , N } et X (b, ω ) = bU (ω ) .
Lorsqu’il y a r boules dans le compartiment gauche et N − r boules dans le comparti-
ment droit,
N N
1
P( X = 0) = ∑ P ( X = 0 |U = k ) P (U = k ) =
N ∑ 1 { 0 } ( bk ) = ρ b ( 0 ) .
k =1 k =1
/Users/dp/a/ens/[Link] 99
2022-09-06 • 16:25:42.
7.7. Irreversibilité et principe de Landauer Quantification de l’information
Exemple 7.7.1. Instancier le modèle précédent dans le cas N = 2 (deux boules dans
une urne à 2 compartiments) engendrant les états physiques (1, 0), (1/2, 1/2) et (1, 1) ;
ils peuvent être réalisés respectivement par les configurations des boules [00], [01] et
[11]. De toute évidence, nous associons l’état logique 0 avec la configuration physique
ρ[00] , l’état logique 1 avec l’état physique ρ[11] et l’état logique ∂ avec la configuration
ρ[01] .
V V
Pgauche = rkT = pNkT, Pdroite = ( N − r )kT = (1 − p) NkT,
2 2
(a)
(b)
(c)
(d)
Figure 7.8 – (a) État initial du système ( p, 1 − p), avec p = r/N. (b) Le trou dans la paroi interne
est ouverte à coût énergétique zéro. Très rapidement après l’ouverture du troi, le gaz occupe désormais
uniformément la totalité du volume. Les couleurs différentes pour les atomes sont uniquement pour
des raisons d’illustration pour rappeler la provenance de chaque atome individuel. Penser cependant
que les atomes sont indiscernables. Par conséquent la couleur ne sera pas montrée dans les étapes
suivantes. (c) La paroir à l’extrémité droite est en réalité un piston qui comprime le gaz de façon
isotherme jusqu’à la moitié du volume. (d) Le trou est de nouveau fermé et le piston retourné à sa
position initiale à l’extrémité droite du récipient. Maintenant, tous les atomes se trouvent dans le
compartiment gauche et le registre est dans l’état pur (1, 0).
12. A DIABATIQUE, adj. et subst. fém. Qui se produit sans qu’il y ait échange de chaleur avec l’extérieur.
/Users/dp/a/ens/[Link] 100
2022-09-06 • 16:25:42.
Quantification de l’information 7.7. Irreversibilité et principe de Landauer
W
∆S = .
k B T ln 2
Plus spécificement, « effcer » un bit d’information coûte de l’énergie. Dans le calcul pré-
cédent, uniquement des transformations adiabatiques sont considérées. Si l’hypothèse
d’adiabaticité est assouplie, au lieu de l’égalité nous avons l’inégalité
∆S ≤ β∆Q,
/Users/dp/a/ens/[Link] 101
2022-09-06 • 16:25:42.
7.7. Irreversibilité et principe de Landauer Quantification de l’information
/Users/dp/a/ens/[Link] 102
2022-09-06 • 16:25:42.
Quantification de l’information 7.8. Exercices
7.8 Exercices
Entropie, mesure de l’information
78. 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 ).
79. 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
16. Selon les données publiées par l’International Energy Agency, la consommation totale d’élecricité
est environ de 68.4 HJ et représente 13% du total de l’énergie produite (ca. 540 HJ.) Le symbole H désigne
le préfixe hexa, représentant le facteur 1018 .
/Users/dp/a/ens/[Link]
103
2022-09-05 • 14:37:22.
7.8. Exercices Quantification de l’information
(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]
104
2022-09-05 • 14:37:22.
Quantification de l’information 7.8. Exercices
86. 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 ).
n
On veut simuler 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 exprimer 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.
Commencer par l’ensemble à trois éléments X =
{ a, b, c} et p = (1/2, 1/4, 1/4). Placer les lettres
a, b, c comme des feuilles d’un arbre binaire com-
plet (i.e. dont chaque nœud a 0 ou 2 descendants)
comme dans la figure adjacente. En associant le
(a) bit 0 aux arêtes gauches et le bit 1 aux arêtes a
droites, on constate que l’ensemble de feuilles
F = {0, 10, 11} de l’arbre se surjecte sur X. On b c
note F : F → X cette surjection (dans ce cas par-
ticulier, il s’agit d’une bijection). Expliciter l’algo-
rithme de génération de X.
(b) Dans le cas particulier de la question précédente, estimer le nombre moyen
de fois qu’il faudra lancer la pièce pour réaliser X et comparer ce résultat
avec l’entropie H ( X ).
(c) Considérer maintenant l’ensemble X = { a, b} et le vecteur de probabilité
p = (2/3, 1/3). Suggestion : Observer que ∑∞ 1 2
k=0 22k+1 = 3 et utiliser cette égalité
pour donner les représentations binaires des nombres 2/3 et 1/3 ; se servir de cette
représentation pour déterminer l’ensemble F de feuilles et la surjection F : F → X.
(d) Estimer le nombre moyen de lancers nécessaires pour simuler X.
(e) Pouvez-vous proposer une méthode générale pour un ensemble fini X arbi-
traire muni d’un vecteur de probabilité arbitraire p ?
/Users/dp/a/ens/[Link] 105
2022-09-06 • 16:25:42.
7.8. Exercices Quantification de l’information
/Users/dp/a/ens/[Link] 106
2022-09-08 • 19:58:05.
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 constitutives du message-source sont
produites.
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
107
8.2. Codes uniquement décodables Sources et leur codage
/Users/dp/a/ens/[Link] 108
2022-09-08 • 19:58:05.
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).
codage UTF -8, connu aussi comme ISO / CEI -10646, du standard UNICODE est un code
C : X → {0, 1}8m de longueur variable en 8m bits où m ∈ {1, 2, 3, 4}, assurant la
compatibilité descendante avec le code ASCII.
Exemple 8.2.4. 1. Soient X = {1, 2, 3, 4}, A = {0, 1}, p = (1/2, 1/4, 1/8, 1/8) et
C le code
x C(x)
1 0
2 10
3 110
4 111
Nous calculons E(|C ( X )| = 1.75 ; il se trouve que pour cet exemple, l’entropie a
aussi la valeur numérique H (p) = 1.75.
2. Soient X = {1, 2, 3}, A = {0, 1}, p = (1/3, 1/3, 1/3) et C le code
x C(x)
1 0
2 10
3 11
Nous calculons E(|C ( X )| = 1.66 tandis que la valeur numérique de l’entropie
est H (p) = 1.58.
buginais, balinais, linéaire A et B, italique, gothique, ugaritique, chypriote, phénicien, kharostht, sys-
tèmes de numérotation anciens, cunéiforme, ainsi que les parties constitutives d’idéogrammes chinois,
japonais et coréens, des symboles mathématiques courants, etc.
/Users/dp/a/ens/[Link] 109
2022-09-08 • 19:58:05.
8.2. Codes uniquement décodables Sources et leur codage
Pour les deux codes de l’exemple précédent 8.2.4, nous observons que si α ∈ A∗
est un mot, image par C d’un mot ξ ∈ X+ , nous pouvons de manière unique décoder
α 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écodable 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. Il n’est donc pas
instantané (comme son caractère non-préfixe le laisse entendre).
/Users/dp/a/ens/[Link] 110
2022-09-08 • 19:58:05.
Sources et leur codage 8.2. Codes uniquement décodables
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.
/Users/dp/a/ens/[Link] 111
2022-09-08 • 19:58:05.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
∑ A−li ≤ 1.
i∈ I
(⇐) Sans perte de généralité, nous pouvons supposer que les x soient rangées en
x1 , . . . , xcardX de sorte que l1 ≤ l2 ≤ . . . ≤ lcardX , où li = lx1 . Nous choisissons un
nœud arbitraire de la l1e génération de T et nous assignons le mot qui correspond
au nœud choisi à C ( x1 ) ; nous excluons simultanément le sous-arbre enraciné
à α1 = C ( x1 ) ce qui revient à exclure A L−l1 feuilles de la génération L. Il est
évident que
∑ A−lx ≤ 1 ⇒ ∑ A L − l x ≤ A L ⇒ A L − l1 < A L ;
x ∈X x ∈X
/Users/dp/a/ens/[Link] 112
2022-09-08 • 19:58:05.
Sources et leur codage 8.3. Théorème de Shannon sur le codage sans bruit
∑ A−lx ≤ 1 ⇒ ∑ A L − l x ≤ A L ⇒ A L − l1 + A L − l2 < A L ;
x ∈X x ∈X
J (`) = ∑ p ( x ) l x + λ ( ∑ A − l x − 1),
x x
∂J
∀ x, = p( x ) − λA−lx log A = 0,
∂lx
∗ p( x )
équation qui admet comme solution A−lx = λ log A . La saturation de la contrainte per-
met de déterminer la constante λ = 1/ log A et par conséquent, exprimer la solution
sous la forme : lx∗ = − log A p( x ). Si les lx∗ étaient tous des entiers, on pourrait alors
construire un code instantané C ∗ qui aurait une longueur moyenne de E|C ∗ ( X )| =
− ∑ x p( x ) log A p( x ) = H A ( X ). Cependant, les lx∗ ne sont pas nécessairement des en-
tiers. Nous avons donc le
E|C ( X )| ≥ H A ( X ),
A−|C( x)|
Démonstration. Introduisons un nouveau vecteur de probabilité r ( x ) = sur
∑y A−|C(y)|
/Users/dp/a/ens/[Link] 113
2022-09-08 • 19:58:05.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
X. Nous aurons
E|C ( X )| − H A ( X ) = ∑ p(x)|C(x)| + ∑ p(x) log A p(x)
x x
= − ∑ p( x ) log A A −|C ( x )|
+ ∑ p( x ) log A p( x )
x x
p( x )
= ∑ p( x ) log A − log(∑ A−|C(y)| )
x r(x) y
1
= D (pkr) + log
∑y A−|C(y)|
≥ 0,
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.
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
H A (p) ≤ E|C ( X )| < H A (p) + 1.
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.
Théorème 8.3.5. (McMillan [51]).
1. Tout code C ∈ Cud vérifie ∑ x A−|C( x)| ≤ 1.
2. Réciproquement, pour toute famille d’entiers (lx ) vérifiant l’inégalité de Kraft, il existe
un code C ∈ Cud tel que |C ( x )| = lx , ∀ x.
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 }.
Introduisons les symboles L = maxx |C ( x )| et νl = cardX1l . Pour tout k ≥ 1 :
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
/Users/dp/a/ens/[Link] 114
2022-09-08 • 19:58:05.
Sources et leur codage 8.3. Théorème de Shannon sur le codage sans bruit
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
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é.
/Users/dp/a/ens/[Link] 115
2022-09-08 • 19:58:05.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
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] 116
2022-09-08 • 19:58:05.
Sources et leur codage 8.3. Théorème de Shannon sur le codage sans bruit
3. S’il existe deux mots de code de longueur maximale l M qui ne coïncident pas sur
les l M − 1 premières lettres, nous pouvons effacer la dernière lettre de chacun
d’eux pour obtenir un code qui reste instantané et qui est meilleur que C.
Nous avons
M −2
E|C20 ( X )| = ∑ pi |C10 (i )| + ( p M−1 + p M )|α|
i =1
M
= ∑ pi |C10 (i)| − p M−1 |C10 ( M − 1)| − p M |C10 ( M)| + ( p M−1 + p M )(|C10 ( M − 1)| − 1)
i =1
= E|C10 ( X )| − ( p M−1 + p M ), car |C10 ( M − 1)| = |C10 ( M)|,
< E|C1 ( X )| − ( p M−1 + p M ), car C10 est supposé strictement meilleur que C1 ,
= E|C2 ( X )|,
/Users/dp/a/ens/[Link] 117
2022-09-08 • 19:58:05.
8.3. Théorème de Shannon sur le codage sans bruit Sources et leur codage
/Users/dp/a/ens/[Link] 118
2022-09-08 • 19:58:05.
Sources et leur codage 8.4. Autres types de codes
la taille de la table du code, i.e. du vecteur (C (x))x∈Xk à |X|k composantes, croît expo-
nentiellement avec la taille k des blocs. Or pour pouvoir décoder les messages, et étant
donné que le code de Huffman n’est pas uniquement déterminé par p, la connaissance
de la table du code est nécessaire par le destinataire. Ce qui implique que la table doit
aussi être transmise, ce qui dégrade les qualités du codage de Huffman.
Un autre inconvénient du code est que sa table dépend très fortement du vecteur
p. Si par exemple on veut transmettre du texte bilingue français/anglais, le vecteur de
probabilité variera selon que la portion codée est en français ou en anglais. Or le code
de Huffman n’est pas adapté à cette situation.
Pour pallier ces inconvénients, d’autres codages on été introduits. Les codes arith-
métiques, dont un exemple est présenté en §8.4.1, nécessite toujours la connaissance
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.
/Users/dp/a/ens/[Link] 119
2022-09-08 • 19:58:05.
8.4. Autres types de codes Sources et leur codage
(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.
La fonction de répartition pour cet exemple est donnée dans la figure 8.2.
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] 120
2022-09-08 • 19:58:05.
Sources et leur codage 8.4. Autres types de codes
/Users/dp/a/ens/[Link] 121
2022-09-08 • 19:58:05.
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] 122
2022-09-08 • 19:58:05.
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] 123
2022-09-08 • 19:58:05.
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 a alors, en désignant par C le code LZ78,
|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).
/Users/dp/a/ens/[Link] 124
2022-09-08 • 19:58:05.
Sources et leur codage 8.4. Autres types de codes
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.
3. Soit ( Xn )n∈N une chaîne de Markov (X, P, π ), où π est la probabilité invariante
de la chaîne. Alors ( Xn )n∈N est stationnaire.
H ( X1 , . . . , X n )
h(X) = lim (lorsque cette limite existe).
n→∞ n
2. Le taux de production d’entropie conditionnelle est
Théorème 8.4.11. Soient X = ( Xk )k∈N une suite stationnaire sur un alphabet fini et ĥn (X) =
H ( Xn | Xn−1 · · · X1 ). Alors la suite (ĥ(X))n est décroissante et possède une limite ĥ(X).
Théorème 8.4.12. Soit X = ( Xk )k∈N une suite stationnaire sur un alphabet fini. Alors les
limites h(X) et ĥ(X) existent et
h(X) = ĥ(X).
Théorème 8.4.13. Soit X := ( Xn )n∈N une chaîne de Markov (X, P, π ), où π est la probabi-
lité invariante de la chaîne. Alors, si C désigne le code LZ78,
|C ( X1 · · · Xn )|
lim = ĥ(X).
n→∞ n
La démonstration (voir [7, 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 [17, 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é [58] — et l’entropie.
/Users/dp/a/ens/[Link]
125
2022-09-06 • 15:56:48.
8.5. Exercices Sources et leur codage
8.5 Exercices
Codes instantanés, codes uniquement décodables
87. 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écodable ?
88. 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
89. 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.
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
90. 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).
91. Soient 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
des 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 .
/Users/dp/a/ens/[Link]
126
2022-09-06 • 15:56:48.
Sources et leur codage 8.5. Exercices
β = 00121212102101210122101
/Users/dp/a/ens/[Link] 127
2022-09-08 • 19:58:05.
8.5. Exercices Sources et leur codage
/Users/dp/a/ens/[Link] 128
2022-12-05 • 10:56:42.
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
129
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] 130
2022-12-05 • 10:56:42.
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] 131
2022-12-05 • 10:56:42.
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] 132
2022-12-05 • 10:56:42.
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] 133
2022-12-05 • 10:56:42.
9.4. Un exemple illustratif simple Canaux bruités sans mémoire
t P( X = z, Y = y) µ(z) Pzy
P̂zy = P̂yz = P( X = z|Y = y) = = .
P (Y = y ) ∑w∈X µ(w) Pwy
Si µ est la loi uniforme sur X, cette formule se réduit à
t Pzy
P̂zy = P̂yz = P( X = z|Y = y) = .
∑w∈X Pwy
Dans l’exemple ci-dessus (avec probabilité uniforme pour la source), elle devient donc
0.5 0.33333 . . . 0.181818 . . .
P̂t = 0.2 0.33333 . . . 0.454545 . . . .
0.3 0.33333 . . . 0.363636 . . .
On constate 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 = {0, 1} ' {000, 111}
et Y = {0, 1}3 , on peut définir, pour tout y = (y1 , y2 , y3 ) ∈ Y, la règle de la majorité,
donnée par la formule
(
000 si y1 + y2 + y3 ≤ 1,
∆(y) := ∆Maj (y) =
111 si y1 + y2 + y3 > 1,
/Users/dp/a/ens/[Link] 134
2022-12-05 • 10:56:42.
Canaux bruités sans mémoire 9.5. Le théorème fondamental de la transmission
/Users/dp/a/ens/[Link] 135
2022-12-05 • 10:56:42.
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] 136
2022-12-05 • 10:56:42.
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,
νδm (m0 ) = Pm ( M0 = m0 ) = P( M0 = m0 | M = m)
= ∑ P( M0 = m0 | M = v)δm (v) = KC Qn K∆ (m, m0 )
v ∈M
= ∑ n ∑ n KC (m, x)Qn (x, y)K∆ (y, m0 ) = ∑ n Qn (C(m), y)δ∆(y),m0 .
x ∈X y ∈Y y ∈Y
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
ν µ ( m 0 ) = Pµ ( M 0 = m 0 ) = ∑ P( M 0 = m 0 | M = m ) µ ( m )
m ∈M
= ∑ ∑ µ(m) Qn (C(m), y)δ∆(y),m0 .
m ∈M y ∈Yn
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] 137
2022-12-05 • 10:56:42.
9.5. Le théorème fondamental de la transmission Canaux bruités sans mémoire
Définition 9.5.1. Un [n, k]-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(n, k) (ou simplment [n, k ]) si on veut préciser
ses paramètres. L’ensemble C(M) ⊆ Xn est appelé glossaire du code K.
log|X| k
R := R[K] = .
n
2. Un taux de transmission R est atteignable s’il existe une suite (K` )`∈N de [n` , k ` ]-
codes par blocs, tels que
log|X| k `
lim → R et lim emax [K` ] = 0.
l →∞ n` l →∞
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 [n` , k ` ]-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 [n` , k ` ]-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.
/Users/dp/a/ens/[Link] 138
2022-12-05 • 10:56:42.
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.
La démonstration de ce théorème est longue. Elle est basée sur la notion de suites
conjointement typiques et est esquissée aux exercices 105 et 106. Elle 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’ensemble 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] 139
2022-12-05 • 10:56:42.
9.5. Le théorème fondamental de la transmission Canaux bruités sans mémoire
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.
Théorème 9.5.7. Soit ( Xi , Yi )i∈N une suite de couples aléatoires à valeurs dans X × Y indé-
pendants et identiquement distribués selon la loi conjointe κ, i.e. ∀i ∈ N,
P(( Xi , Yi ) = ( x, y)) = P(( X1 , Y1 ) = x, y) = κ ( x, y).
On note Xn (resp. Xn ) la troncature des suites infinies aux n premiers termes, i.e. Xn =
( X1 , X2 , . . . , Xn ) (resp. Yn = (Y1 , Y2 , . . . , Yn ). Alors, pour ε ∈]0, 1[ (suffisamment petit)
/Users/dp/a/ens/[Link] 140
2022-12-05 • 10:56:42.
Canaux bruités sans mémoire 9.5. Le théorème fondamental de la transmission
P
1. limn→∞ P ((Xn , Yn ) ∈ Jκ,ε,n ) = 1.
2. (1 − ε)2n( H (κ )−ε) ≤ |Jκ,ε,n | ≤ 2n( H (κ )+ε) .
3. Soient X̃ = ( X̃i )i∈N et Ỹ = (Ỹi )i∈N des suites aléatoires indépendantes et mutuelle-
ment indépendantes, à valeurs respectivement dans X et Y, distribués selon les lois
P( X̃1 = x ) = µ( x ) et P(Ỹ1 = y) = ν(y), i.e. la loi du couple est donnée par
P (X̃n , Ỹn ) = ( x, y) = µ( x )ν( x ). Alors
(1 − ε)2−nI (X1 :Y1 )+3ε) ≤ P (X̃n , Ỹn ) ∈ Jκ,ε,n ≤ 2−nI (X1 :Y1 )−3ε) ,
Remarque 9.5.8. Le code avec des tailles de blocks n pourrait coder jusqu’à |X|n mes-
sages. Ce que nous dit le théorème fondamental de la transmission est que si cap < 1
on peut, en raréfiant l’ensemble de message à un cardinal k = |X|nR avec R < cap,
transmettre les messages sans erreur. C’est précisément ce résultat que est illustré par
l’exemple 9.5.5 et c’est le résultat que nous allons démontrer dans la suite.
(m) (m)
P( X ( m ) = x ( m ) ) = µ n ( x ( m ) ) = µ ( x1 ) · · · µ ( x n )
/Users/dp/a/ens/[Link] 141
2022-12-05 • 10:56:42.
9.5. Le théorème fondamental de la transmission Canaux bruités sans mémoire
et les variables X(l ) et X(m) codant des messages différents l 6= m sont indépen-
dates. Par conséquent, le choix du code sera déterminé par la loi
k k n
∏ µ n ( x (m) ) = ∏ ∏ µ ( xi
(1) (k) (m)
P G = (x ,...,x ) = ). (9.2)
m =1 m =1 i =1
/Users/dp/a/ens/[Link]
142
2021-11-25 • 21:12:16.
Canaux bruités sans mémoire 9.6. Exercices
C Qn M̂
1 X (1)
.. ..
. .
m X(m) Y(m) M̂(Y(m) ) ∈ Mk ∪ {∂}
.. ..
. .
k X(k)
Figure 9.5 – Résumé des actions de codage du message m ∈ Mk , de sa transmission et de son
décodage. Les flèches pointillées signifient qu’une information concernant les X(l ) est utilisée lors du
décodage. Il faut cependant comprendre que cette information est juste une astuce théorique pour
démontrer le théorème ; on ne sous-entend pas que M̂ a effectivement besoin de cette information
contenue dans la réalisation précise des variables X(l ) pour effectuer le décodage.
9.6 Exercices
Codage du canal
98. 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 ).
99. 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.
100. Soit K = (X, Y, P) le canal avec alphabets d’entrée et de sortie X = Y, ayant
cardX = cardY = 27. On suppose que ces ensembles sont ordonnés ; on peut par
conséquent les identifier avec Z27 = {0, . . . , 26} d’une part et avec l’alphabet
latin augmenté du symbole blanc d’autre part à travers la bijection 0 → , 1 →
a, . . . , 26 → z. La périodisation signifie que le symbole ≡ 0 succède à z ≡ 26
et précède a ≡ 1. Lorsque l’entrée du canal X est une lettre x ∈ X, la sortie est
une variable aléatoire Y uniformément distribuée dans { x − 1 mod 27, x, x + 1
mod 27} ⊂ Y.
Suggestion : Pour cet exercice vous pouvez vous inspirez de l’exemple du « cla-
vier mal tempéré » traité en cours.
/Users/dp/a/ens/[Link]
143
2021-11-25 • 21:12:16.
9.6. Exercices Canaux bruités sans mémoire
Montrer que la règle de décision ainsi définie est optimale, c’est-à-dire, pour
toute autre règle déterministe d0 , on DC(d0 ) ≤ DC(do ).
(d) Soit D une règle de décision stochastique arbitraire correspondant à la pro-
babilité conditionnelle Qyx = P( D (y) = x |Y = y). Montrer que DC( D ) ≤
DC(do ).
(e) Dorénavant
X= { x1 , x2 , x3 }, Y = {y1 , y2 , y3 }, π = (1/2, 1/4, 1/4) et P =
1 0 0
0 1 0 , calculer ρ.
0 1/2 1/2
/Users/dp/a/ens/[Link]
144
2021-11-25 • 21:12:16.
Canaux bruités sans mémoire 9.6. Exercices
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
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.
/Users/dp/a/ens/[Link]
145
2021-11-25 • 21:12:16.
9.6. Exercices Canaux bruités sans mémoire
2C1
(d) Montrer que la valeur de p qui maximise C ( p) est p = C .
2 +2C2
1
(e) En conclure que la capacité du canal « somme » vérifie 2C = 2C1 + 2C2 ).
105. (Typicité conjointe). On utilise la notation introduite dans le paragraphe sur la
typicité conjointe.
(a) Montrer que
/Users/dp/a/ens/[Link]
146
2021-11-25 • 21:12:16.
Canaux bruités sans mémoire 9.6. Exercices
(b) Que peut-on conclure sur la dépendance des variables aléatoires composant
le couple (X(m) , Y(m) ) ? Même question pour le variables du couple (X(l ) , Y(m) ),
avec l 6= m.
(c) Partant de l’expression évidente, valable pour un m ∈ Mk fixé, pour la pro-
babilité d’erreur :
asymptotiquement à grand n.
(e) Utiliser les résultats, obtenus aux questions 106b et 105e pour majorer la
probabilité
P((X(l ) , Y(m) ) ∈ Jκ,ε,n )
asymptotiquement à grand n.
(f) Conclure que
e(m) ≤ ε + (k − 1)2−n( I (X1 :Y1 )−3ε)
où le couple ( X1 , Y1 ) est distribué selon κ.
(g) Choisir maintenant k = 2nR . Montrer que tant que R < cap, la transmission
peut se faire avec une erreur négligeable.
/Users/dp/a/ens/[Link] 147
2022-12-05 • 10:56:42.
9.6. Exercices Canaux bruités sans mémoire
/Users/dp/a/ens/[Link] 148
2023-07-18 • 17:43:52.
10
Chiffrement
Augustus Kerchoffs : La cryptographie militaire ; Journal des sciences militaires (1883) [40, 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.
149
10.1. Sécurité des communications Chiffrement
/Users/dp/a/ens/[Link] 150
2023-07-18 • 17:43:52.
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 [59] en 1978, le meilleur
algorithme avait une complexité temporelle de O(exp(n)). De nos jours, le meilleur algorithme [45] a
une complexité O(exp(n1/3 log2/3 n)). Si un ordinateur quantique se construit, l’algorithme de Shor
[66] a une complexité O(n3 ). Pour mémoire : « âge de l’univers » = 1.377 × 1010 a.
Comme on verra dans les paragraphes suivants 10.2 et 10.3, la mise en place d’un
code inconditionnellement sûr exige
— la génération d’une suite de même longueur 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 impossibles à réaliser dans la pra-
tique. C’est pourquoi, les méthodes de cryptographie symétrique à clé privée ont été
abandonné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 aujour-
d’hui on dispose des méthodes rapides, fiables et efficaces remplissant ces exigences.
/Users/dp/a/ens/[Link] 151
2023-07-18 • 17:43:52.
10.2. Le chiffrement comme code Chiffrement
Des solutions quantiques sont déjà proposées dans un stade pré-industriel et à un coût
raisonnable (cf. cours [57]).
Dans ce chapitre, nous nous intéressons uniquement aux cryptage et à l’authentifi-
cation offrant une sécurité informationnelle (inconditionnelle).
/Users/dp/a/ens/[Link] 152
2023-07-18 • 17:43:52.
Chiffrement 10.2. Le chiffrement comme code
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 :
Lemme 10.2.4. Si m0 est obtenu par l’application de l’algorithme 10.2.3 sur le cryptgramme
y produit par l’algorithme 10.2.2, alors
(
0 0 1 si m0 = m
P( M = m | M = m ) =
0 sinon.
/Users/dp/a/ens/[Link] 153
2023-07-18 • 17:43:52.
10.2. Le chiffrement comme code Chiffrement
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
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
/Users/dp/a/ens/[Link] 154
2023-07-18 • 17:43:52.
Chiffrement 10.3. Authentification
m0 = overwhelminglyvictoriousovertheevilaxis
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
5. Organisme dépendant du gouvernement des États-Unis dont les missions sont décrites à ce lien.
6. NIST Special Publication 800-90 : Recommendation for Random Number Generation Using Deter-
ministic Random Bit Generators (2007).
7. Organisation internationale de normalisation, reconnue par 162 pays dont les missions sont dé-
crites sur ce lien.
8. NIST Special Publication 800-90A Revision 1: Recommendation for Random Number Generation
Using Deterministic Random Bit Generators (2015).
9. Intitulé « Encryption and the NSA role in international standards ».
/Users/dp/a/ens/[Link] 155
2023-07-18 • 17:43:52.
10.3. Authentification Chiffrement
— 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) 10 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é se-
crète qu’ils ont utilisée. Nous suivons les exposés [68, 67, 49]. Contrairement au cas de
cryptage, où le théorème de Shannon fournit comme définition du parfait chiffrement
l’indé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.
/Users/dp/a/ens/[Link] 156
2023-07-18 • 17:43:52.
Chiffrement 10.3. Authentification
sub
Théorème 10.3.1. La probabilité moyenne β := βmax que l’adversaire réussisse sa tentative
de fraude par substitution est
β ≥ 2 − H ( K |Y ) .
H ( K |Y ) = ∑ H ( K |Y = y ) ν ( y )
y ∈Y
/Users/dp/a/ens/[Link] 157
2023-07-18 • 17:43:52.
10.3. Authentification Chiffrement
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},
α= ∑ µ(k, z),
z ∈Yk (1 )
β= ∑ ρ(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.
On introduit deux vecteurs de probabilité p0 et p1 sur l’espace des décisions D,
définis par
p0 = (1 − α, α) et p1 = ( β, 1 − β),
où α, β désignent les erreurs de type I et II respectivement. Par ailleurs, on introduit
deux vecteurs de probabilité q0 et q1 sur Y, définis pour chaque k ∈ K fixé, par
Lemme 10.3.2. Les espaces probabilisés (Y, q0 ) et (Y, q1 ) sont des fragmentations (cf. défi-
nition 7.3.5) des espaces probabilisés (D, p0 ) et (D, p1 ).
Démonstration. Par simple vérification.
Théorème 10.3.3. Sous les conventions et avec les notations précédentes, on définit
1−α α
d(α, β) := D ((1 − α, α)k( β, 1 − β)) = (1 − α) log + α log .
β 1−β
Nous avons alors
d(α, β) ≤ D (µkρ ⊗ q̃).
En particulier, β ≥ 2− I (K:Y ) .
Démonstration. La majoration D ((1 − α, α)k( β, 1 − β)) ≤ D (µkρ ⊗ q̃) est une consé-
quence directe du lemme 10.3.2 et de la proposition 7.3.6 (qui établit que la fragmenta-
tion augmente le contraste). Cette majoration est valable pour tout vecteur de probabi-
lité q̃ sur Y. On peut donc optimiser le second membre pour obtenir
d(α, β) ≤ inf D ( µ k ρ ⊗ q 0 ) ≤ D ( µ k ρ ⊗ ν ),
q0 ∈M 1 (Y)
/Users/dp/a/ens/[Link] 158
2023-07-18 • 17:43:52.
Chiffrement 10.4. Qu’est-ce la cryptographie post-quantique ?
/Users/dp/a/ens/[Link] 159
2023-07-18 • 17:43:52.
10.5. Exercices Chiffrement
10.5 Exercices
/Users/dp/a/ens/[Link] 160
2023-07-18 • 17:43:52.
Codes correcteurs d’erreur
11
Or rappelle qu’un système de communication est décrit par la figure 9.3. Le théo-
rème fondamental de transmission 9.5.4 garantit l’existence d’un codage permettant
la communication sans erreur à travers un canal K = (X, Y, P) pourvu que le taux
de transmission R < cap( P) = supµ∈M1 (X) I ( X : Y ), où µ est la loi de la variable X
à l’entrée du canal. Ce résultat s’obtient en imposant une rarefaction des messages à
transmettre, i.e. |M| < |Xn |, qui a comme conséquence d’utiliser un codage redondant
pour chaque message. Cependant, ce résultat est existentiel. Dans ce chapitre nous
allons construire des codes effectifs dans le cas où M ' Xl , avec l < n. Une telle
raréfaction induit un taux de transmission
log |Xl | l
R= = .
log |X |
n n
161
11.2. Structure géométrique des codes Codes correcteurs d’erreur
xn
et
x1
Fnq 3 x = ... 7→ W(x) = ξ = x1 · · · xn ∈ Xn
xn
qui sont l’inverse l’une de l’autre : W−1 = V et V−1 = W.
1. On rappelle que la caractéristique d’un corps unifère est le plus petit entier n tel n · 1 = 0.
2. Vérifier que d H est bien une distance.
/Users/dp/a/ens/[Link] 162
2022-01-07 • 10:22:29.
Codes correcteurs d’erreur 11.2. Structure géométrique des codes
Cette distance induit une distance, aussi notée d H , sur Fnq par d H (x, x0 ) := d H (W(x), W(x0 )).
L’espace (Xn , d H ) devient un espace métrique isomorphe à l’espace vectoriel métrisé
(Fnq , d H ).
Dans tout ce qui suit, les alphabets d’entrée et de sortie du canal sont identiques,
isomorphes à Fq (X = Y ' Fq ), avec q puissance d’un premier (le plus souvent q = 2
et X = Y = {0, 1}). S’il n’y a pas d’ambiguïté, nous ne ferons plus la distinction entre
ces espaces. Un code est une application C : Xl → Xn avec n ≥ l.
d = min d(x, x0 ).
x,x0 ∈G
x6=x0
4. On note (n, ql ), ou plus précisément (n, ql , d), le code linéaire sur l’alphabet Fq
agissant sur des blocs de taille l, produisant des blocs de taille n et à distance
minimale d. Une autre notation 3 , qui privilégie la dimension du glossaire k =
dim G , est [n, k ], ou plus précisément [n, k, d].
5. Si des bases sont fixées dans Flq et Fnq , le code linéaire C : Xl → Xn est représenté
par une matrice de Ml,n (Fq ) dépendante des bases choisies.
/Users/dp/a/ens/[Link] 163
2022-01-07 • 10:22:29.
11.2. Structure géométrique des codes Codes correcteurs d’erreur
Proposition 11.2.4. Soit C un [n, k]-code linéaire sur Fq et (e1 , . . . , ek ) une base arbitraire
du glossaire G . La matrice génératrice de C est
e1t
G = ... ∈ Mk,n .
etk
On peut par des opérations sur les lignes de G, i.e. par un changement de base, la
ramener à sa forme systématique
G := G (C ) = [ Ik | A],
y5 = x1 + x2 + x3
y6 = x2 + x3 + x4
y7 = x1 + x3 + x4 .
/Users/dp/a/ens/[Link] 164
2022-01-07 • 10:22:29.
Codes correcteurs d’erreur 11.2. Structure géométrique des codes
g ∈ G(C ) ⇐⇒ Hg = 0,
H (Pn ) = G (Rn );
/Users/dp/a/ens/[Link] 165
2022-01-07 • 10:22:29.
11.3. Décodage Codes correcteurs d’erreur
Définition 11.2.10. Soit C un [n, k ] code sur Fq dont le glossaire est G . Le code dual est
défini par son glossaire
n −1
G ⊥ = {x ∈ Fnq : x · g = xt g := ∑ xj gj mod q = 0, ∀g ∈ G},
j =0
11.3 Décodage
11.3.1 Maximum de vraisemblance
Le problème que nous voulons résoudre est illustré par l’exemple suivant.
Exemple 11.3.1. Un message m ∈ F2k est codé en un message x := C (m) ∈ F2n , avec
n ≥ k. Le message x est ensuite transmis à travers un canal symétrique binaire qui
change avec probabilité p < 1/2 un bit en son opposé. Le message transmis est alors
une variable aléatoire Y à valeurs dans F2n de loi conditionnelle
/Users/dp/a/ens/[Link] 166
2022-01-07 • 10:22:29.
Codes correcteurs d’erreur 11.3. Décodage
Une boule de Hamming est centrée sur chaque mot g ∈ G du glossaire. Tout
y ∈ Bn,r (g) sera donc décodé par l’estimation ŷ = arg minz∈F2n d(g, z) = g ∈ G . On
voit donc immédiatement les contraintes d’un bon décodage par maximum de vrai-
semblance :
1. Le rayon r de la boule doit être aussi grand que possible pour que le maximum
des mots de Fnq se trouvent dans une boule de Hamming.
2. Le rayon r doit être suffisamment petit pour que les boules de la famille { Bn,r (g), g ∈
G} soient disjointes de sorte que chaque mot dans la boule puisse être décodé
sans ambiguïté. Cette dernière condition sera vérifiée dès que r < 21 d, où d est la
distance minimale du code.
Exemple 11.3.3. Soit C = R3 le code à répétition sur F2 . Il s’agit d’un [3, 1, 3]-code.
L’estimateur du plus proche voisin corrigera une erreur si r ≤ 1. Le glossaire de ce
code est G = {000, 111} et les boules de Hamming de rayon 1 sont
B3,1 (000) = {000, 001, 010, 100} et B3,1 (111) = {111, 011, 101, 110}.
On constate que B3,1 (000) t B3,1 (111) = F32 . Tout mot de F32 peut donc être décodé sans
ambiguïté et le code corrige toute erreur qui modifie la valeur d’un bit.
Lemme 11.3.4. Un code linéaire C sur le corps F, avec distance minimale d, permet de corriger
jusqu’à t = b d− 1
2 c erreurs.
On aura donc,
Le mot y sera donc décodé par l’estimation ŷ = ∆(y) = g qui est le mot effectivement
envoyé (avec toutes les erreurs de transmission corrigées).
Réciproquement, supposons que d < 2t + 1. Il s’ensuit que d ≤ 2t. Par définition de
d, il existe deux mots différents g et g0 du glossaire différent exactement sur d positions,
i.e. d = d(g, g0 ). Il existe alors x ∈ Fn avec d(g, x) ≤ t et d(g0 , x) ≤ t. Par exemple,
en modifiant g en b 2d c positions, on obtient un tel x. Or l’estimation x̂ sera ambiguë car
tant g que g0 sont à distance inférieure à d de x.
Pour un [n, k ]-code sur Fq , les k qits sont appelés qits d’information tandis que les
n − k qits restants, qits de contrôle.
Théorème 11.3.5 (Empilement de boules de Hamming). Soit C un [n, k, d]-code linéaire
sur Fq permettant de corriger t erreurs (t ≤ b d− 1
2 c). Alors,
t
Vq (n, t) := ∑ Cnr (q − 1)r ≤ qn−k .
r =0
/Users/dp/a/ens/[Link] 167
2022-01-07 • 10:22:29.
11.3. Décodage Codes correcteurs d’erreur
Or, pour chaque g, les mots dans {x ∈ Fnq : d(x, g) = r } diffèrent de g en exactement r
indices. Si i est un tel indice, xi peut prendre n’importe quel valeur xi ∈ Fq \ { gi }. Par
conséquent, le volume Vq (n, r ) = |{x ∈ Fnq : d(x, g) = r }| = Cnr (q − 1)r .
On a donc
t
| Bn,t (g)| = ∑ Cnr (q − 1)r .
r =0
Or, dim G = k, donc il existe qk mots différents dans G . Les boules Bn,t (g) centrées sur
les mots du glossaire sont disjointes car leur rayon est inférieur à d/2. Comme elles
sont toutes contenues dans Fnq , on a de manière évidente,
t
∑ | Bn,t (g)| = qk ∑ Cnr (q − 1)r ≤ qn .
G
Bn,t (g) =
g∈G g∈G r =0
Corollaire 11.3.6. Soit C code sur Fq ayant un glossaire G de dimension k (i.e. k qits d’infor-
mation). Pour que le code puisse corriger t erreurs, il faut qu’il dispose de n − k qits de contrôle,
où !
t
n − k ≥ logq ∑ Cnr (q − 1)r .
r =0
Corollaire 11.3.7. Soit C un [n, k]-code sur F2 permettant de corriger t erreurs. Asymp-
totiquement, lorsque limn,t→∞ , avec limn→∞ nt = x ∈ [0, 1], le taux de transmission R =
limn→∞ k/n du code vérifie
1 − R ≥ H2 ( x ),
où H2 ( x ) = − x log2 x − (1 − x ) log2 (1 − x ) est l’entropie binaire.
t
n
2 ≥2 k
∑ Cnr ≥ 2k Cnt .
r =0
√
On conclut en utilisant l’approximation de Stirling pour le factoriel : n! (n/e)n 2πn.
/Users/dp/a/ens/[Link] 168
2022-01-07 • 10:22:29.
Codes correcteurs d’erreur 11.3. Décodage
Démonstration. Parmi tous le codes ayant q, n et d fixés, soit G le (glossaire du) code
qui maximise la taille du glossaire, i.e. M = |G| = Aq (n, d). Les boules de Hamming
Bd−1 (g) = {x ∈ Fnq |d(g, x) ≤ d − 1}, où g ∈ G , doivent couvrir Fnq . En effet, si y ∈ Fnq
n’appartient pas à la boule Bd−1 (g), cela signifie que d(g, y) ≥ d ; si y n’appartenait à
aucune des boules cela signifierait que d(y, g) ≥ d pour tout g ∈ G . Par conséquent,
le code dont le glossaire serait G 0 = G ∪ {y} aurait les mêmes paramètres q, n, d mais
avec |G 0 | > |G| ; ceci contredirait la maximalité de G . Maintenant,
d −1
| Bd−1 (g)| = ∑ Cnr (q − 1)r ,
r =0
tandis que la réunion (pas nécessairement disjointe) de ces boules couvre Fnq .
Dans la plupart de cas, la différence entre les bornes supérieure et inférieure de
Aq (n, d) est grande et sa valeur précise est en général difficile à calculer. On peut ce-
pendant délimiter une région entre les deux bornes asymptotiques (lorsque n → ∞) en
remarquant que si, limn→∞ d− 1 2t
n = limn→∞ n = z ∈ [0, 1], alors, dans le cas q = 2, on a
l’encadrement
1 − H (z/2) ≤ R ≤ 1 − H (z), z ∈ [0, 1],
où H désigne la fonction entropie.
Définition 11.3.9. Un [n, k, d]-code C sur Fq pour lequel la borne du théorème 11.3.5
est saturée, i.e.
t
∑ Cnr (q − 1)r = qn−k ,
r =0
est dit parfait.
/Users/dp/a/ens/[Link] 169
2022-01-07 • 10:22:29.
11.3. Décodage Codes correcteurs d’erreur
1
1 − H (z)
Taux de transmission R
0.8 1 − H (z/2)
Codes réalisables
0.6
0.4
0.2
0
0 0.2 0.4 0.6 0.8 1
z
Il est évident que la numérotation des classes n’est pas unique car plusieurs élé-
ments peuvent avoir le même poids. Cependant, pour chaque décomposition fixée, la
famille (Yr )r=0,...,L−1 est une partition de Y ; il s’ensuit que (pour cet ordre)
∀y ∈ Y, ∃!r ∈ {0, . . . , L − 1} et ∃!s ∈ {0, . . . , K − 1} : y = yr + gs .
On appelle indice pivot de la partition, et on le note r p ,
d−1
r p = max{r ∈ {0, . . . , L − 1} : w(yr ) ≤ t = b c.
2
/Users/dp/a/ens/[Link] 170
2022-01-07 • 10:22:29.
Codes correcteurs d’erreur 11.3. Décodage
Lemme 11.3.12. Soit (Yr )r=0,...,L−1 une partition de Y pour un [n, k ]-code linéaire sur Fq et
G = {g0 , . . . , gK−1 } son glossaire. On note yr le représentant dominant de la classe Yr . Soit
y ∈ Y.
1. Si y = yr + gs pour un r ∈ {0, . . . , L − 1} et s ∈ {0, . . . , K − 1}, alors gs est à
distance au plus w(yr ) de y dans G .
2. Si r ≤ r p , où r p est l’indice pivot de la partition (i.e. w(yr ) ≤ t), alors gs est l’unique
élément de G à distance au plus w(yr ) de y. On pourra donc décoder, sans erreur, y par
ŷ = gs .
Démonstration. 1. Supposons que gs ne soit pas à distance au plus w(yr ) de y. Il
existe donc un gs0 ∈ G tel que d(y, gs0 ) < d(y, gs ). Puisque pour tout x, x0 ∈ Fnq ,
nous avons d(x, x0 ) = w(x − x0 ), il s’ensuit que w(y − gs0 ) < w(y − gs ) = w(yr ).
Par ailleurs, y − gs0 = yr + (gs0 − gs ) ∈ yr + G = Yr . Ceci contredit l’hypothèse
que yr est un représentant dominant de la classe de congruence Yr .
2. Maintenant r < r p , i.e. w(yr ) ≤ t. Supposons qu’il existe gs0 ∈ G tel que
d(y, gs0 ) < d(y, gs ). On aura alors
d( g s , g s 0 ) ≥ d
> 2t ≥ 2d(y, gs ) = d(y, gs ) + d(y, gs )
≥ d(y, gs ) + d(y, gs0 ) ( car d(y, gs0 ) < d(y, gs ))
≥ d(gs , gs0 ) (par l’inégalité triangulaire).
Ceci mène à l’inégalité impossible d(gs , gs0 ) > d(gs , gs0 ).
Table 11.1 – Par abus de notation, on écrit y = ξ au lieu de y = V(ξ ). Pour ξ ∈ {0, 1}4 , le trait
discontinu sépare les classes dont le représentant dominant a un poids inférieur ou égal à t des autres.
Le dernier indice avant le trait est dit indice pivot, noté r p ; dans cet exemple r p = 4. Supposons
que 1111 est transmis mais le bruit le corrompt en 0111. En cherchant dans le tableau précédent, on
constate que y = 0111 ∈ Y4 et y = y4 + g1 . Par conséquent, g1 = 1111 est à distance 1 = w(y4 )
de y dans G . Comme 4 ≤ r p , 1111 est l’unique élément de G à distance 1 de y et on le décode sans
erreur ∆(0111) = 1111. Si y = 0101 est reçu, on constate que y ∈ Y6 . Alors 0000 est à distance 2
de y dans G ; mais comme 6 > r p , rien ne garantit que 0000 est l’unique élément de G à distance 2
de 0101. En effet 1111 l’est aussi.
/Users/dp/a/ens/[Link] 171
2022-01-07 • 10:22:29.
11.3. Décodage Codes correcteurs d’erreur
Corollaire 11.3.16. Le syndrome d’un vecteur y ∈ Y reçu ne dépend pas de y mais unique-
ment du bruit additif qui l’a corrompu.
Démonstration. Le vecteur reçu est obtenu par y = xG + b, où b est le bruit additif. Or
xG ∈ G ; par conséquent s(y) = H (g + b) = Hb, car g = xG ∈ G .
Ce résultat permet de systématiser le décodage comme le montre l’algorithme 11.3.17
ci-dessous.
Algorithme 11.3.17. Décodage par syndrome
Require: k, n, q, G , matrice H du code, partition (Yr ), suite de représentants dominants
(yr ), message à décoder y.
Ensure: ŷ = ∆(y).
s ← Hy
r←0
sr ← Hyr
while sr 6= s do
r ← r+1
sr ← Hyr
end while
ŷ ← y − yr
/Users/dp/a/ens/[Link]
172
2021-08-20 • 15:45:18.
Codes correcteurs d’erreur 11.4. Exercices
r yr w ( yr ) s ( y2 ) Yr
0 0000 0 000 {0000, 1111}
1 0001 1 001 {0001, 1110}
2 0010 1 010 {0010, 1101}
3 0100 1 100 {0100, 1011}
4 1000 1 111 {1000, 0111}
5 0011 2 011 {0011, 1100}
6 0101 2 101 {0101, 1010}
7 0110 2 110 {0110, 1001}
Table 11.2 – Supposons que 1111 est transmis mais le bruit le corrompt en 0111 ayant s(0111) =
111 correspondant à la classe r = 4. On calcule alors ∆(0111) = 0111 − 1000 = 1111.
1
Shannon
Taux de transmission R
0.8 Inaccessible
Inaccessible Rn
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
Figure 11.2 – Pour un canal symétrique binaire, avec taux d’erreur p = 0.1, la ligne rouge représente
la frontière de Shannon établie en théorème 9.5.4, délimitant la région inaccessible de la région où
des codes existent. Les points bleus représentent la suite des taux de transmission en fonction de la
probabilité d’erreur résiduelle pour la famille de codes à répétition Rn , avec n = 1, 3, 5, . . . , 61.
11.4 Exercices
Codes à répétition
107. Dans cet exercice, on considère un canal binaire symétrique ayant une proba-
bilité d’erreur p. On note Rn le code à n ∈ N> répétitions pour chaque bit et
pb (Rn , p) la probabilité de décoder de manière erronée un bit par la méthode de
vote majoritaire.
(a) Calculer pb (R3 , 0.1).
(b) Calculer pb ( Rn , p), pour n ∈ N> .
(c) Pour p = 0.1 quel est le terme dominant dans l’expression de pb (Rn , p).
(d) À partir de quelle valeur de n, on obtient une valeur de pb (Rn , 0.1) ≤ 10−15 ?
(e) Quel est le taux de transmission pour Rn ?
(f) Placer les couples (Rn , log pb (Rn , p)) pour n ∈ {1, 3, 5 . . . , 61} sur un gra-
/Users/dp/a/ens/[Link]
173
2021-08-20 • 15:45:18.
11.4. Exercices Codes correcteurs d’erreur
phique. Qu’observez-vous ?
108. Soit Rn un code à répétition sur Fq . Montrer que
(a) si q = 2 et n est impair alors Rn est parfait,
(b) si q > 2 ou n est pair, alors Rn est imparfait.
Codes de Hamming
112. Décoder par le code de Hamming H AM (7, 4) les messages suivants :
(a) α = 1101011,
(b) α = 0110110,
(c) α = 0100111,
(d) α = 1111111.
113. Calculer toutes les chaînes de bruit b ∈ {0, 1}7 qui donnent un syndrome nul
pour H AM (7, 4).
114. 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 kbk = 2.
6. Hadamard a montré que le déterminant de toute matrice J ∈ Mn,n ([−1, 1]) avec des lignes deux-
à-deux orthogonales est majoré par nn/2 ; cette borne est saturée si, et seulement si, Ji,j = ±1.
7. On peut montrer que si J est une matrice de Hadamard d’ordre n > 2, alors n est divisible par 4.
L’affirmation qu’il existe une matrice de Hadamard pour tout ordre n divisible par 4 reste une conjecture
encore ouverte !
/Users/dp/a/ens/[Link]
174
2021-08-20 • 15:45:18.
Codes correcteurs d’erreur 11.4. Exercices
115. La matrice de contrôle de parité du code H AM (15, 11) 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] 175
2022-01-07 • 10:22:29.
Références Codes correcteurs d’erreur
/Users/dp/a/ens/[Link] 176
2021-12-23 • 14:43:13.
Bibliographie
[1] Robert B. Ash. Information theory. Dover Publications Inc., New York, 1990. Cor-
rected reprint of the 1965 original. 84
[2] Philippe Barbe and Michel Ledoux. Probabilité. EDP Sciences, Les Ulis, 2007.
Deuxième édition, revue et corrigée. 9, 15
[3] Steven M. Bellovin. Frank Miller: Inventor of the one-time pad. Cryptologia, 35, 07
2011. doi:10.1080/01611194.2011.583711. 152
[5] Manabendra Nath Bera, Arnau Riera, Maciej Lewenstein, Zahra Baghali Kha-
nian, and Andreas Winter. Thermodynamics as a consequence of information
conservation. Quantum, 3:121, February 2019. URL: [Link]
q-2019-02-14-121, doi:10.22331/q-2019-02-14-121. 84
[6] Antoine Bérut, Artak Arakelyan, Artyom Petrosyan, Sergio Ciliberto, Raoul
Dillenschneider, and Eric Lutz. Experimental verification of Landauer’s
principle linking information and thermodynamics. Nature, 483, 3 2012.
URL: [Link]
doi:10.1038/nature10872. 102
[7] 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. 125
[8] 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, 13
[9] Ludwig Boltzmann. Vorlesungen über Gastheorie, 1. Theil. Verlag von Johann Am-
brosius Barth, Leipzig, 1896. 84, 85
[10] 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). 85
[11] 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. URL: http:
177
Références BIBLIOGRAPHIE
//[Link]/10.1016/S0169-7552(98)00110-X, doi:10.1016/S0169-7552(98)
00110-X. 60
[14] Yuan Shih Chow and Henry Teicher. Probability theory. Springer Texts in Sta-
tistics. Springer-Verlag, New York, third edition, 1997. Independence, interchan-
geability, martingales. URL: [Link]
doi:10.1007/978-1-4612-1950-7. 37
[15] Kai Lai Chung. A course in probability theory. Academic Press, Inc., San Diego, CA,
third edition, 2001. 37
[16] The Unicode Consortium. Unicode Standard, Version 5.0, The (5th Edition). Addison-
Wesley Professional, 5 edition, 2006. 108
[17] Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley-
Interscience [John Wiley & Sons], Hoboken, NJ, second edition, 2006. 84, 125
[19] Persi Diaconis, Susan Holmes, and Richard Montgomery. Dynamical bias in the
coin toss. SIAM Rev., 49(2):211–235, 2007. URL: [Link]
S0036144504446436, doi:10.1137/S0036144504446436. 17
[20] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE
Trans. Information Theory, IT-22(6):644–654, 1976. URL: [Link]
1109/tit.1976.1055638, doi:10.1109/tit.1976.1055638. 151
[21] Jean-Guillaume Dumas, Jean-Louis Roch, Éric Tannier, and Sébastien Varette.
Foundations of Coding: Compression, Encryption, Error Correction. Wiley, 2015. doi:
10.1002/9781119005940. 150
[22] Paul Ehrenfest and Tatiana Ehrenfest. Über zwei bekannte Einwände gegen das
Boltzmannsche H-Theorem. Physikalische Zeitschrift, 8:311–314, 1907. 57
[23] Peter Elias. Error-free coding. Information Theory, Transactions of the IRE Professional
Group on, 4(4):29–37, 1954. doi:10.1109/TIT.1954.1057464. 2
[24] Peter Elias. The noisy channel coding theorem for erasure channels. Amer. Math.
Monthly, 81(8):853–862, 1974. URL: [Link] doi:
10.2307/2319442. 2
[25] Thomas L. Floyd. Electronic devices. What’s New in Trades & Technology. Pearson
College Division, 10th edition, 2017. 10th edition. 97
/Users/dp/a/ens/[Link] 178
2021-12-23 • 14:43:13.
BIBLIOGRAPHIE Références
[26] Erol Gelenbe and Yves Caseau. The impact of information technology on energy
consumption and carbon emissions. Ubiquity, 2015(June), June 2015. URL: https:
//[Link]/10.1145/2755977, doi:10.1145/2755977. 103
[29] 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
[30] J. Willard Gibbs. Elementary principles in statistical mechanics: developed with especial
reference to the rational foundation of thermodynamics. Dover publications Inc., New
York, 1960. 84
[33] Jeongmin Hong, Brian Lambson, Scott Dhuey, and Jeffrey Bokor. Experimen-
tal test of Landauer’s principle in single-bit operations on nanomagnetic me-
mory bits. Science advances, 2(3):e1501492–e1501492, 2016. doi:10.1126/sciadv.
1501492. 102
[34] Paul Horowitz and Winfield Hill. The art of electronics. Cambridge Unversity Press,
Cambridge, 2015. 97
[37] 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. doi:10.1109/ISCAS.2009.5118356. 122
[38] Mark Kelbert and Yuri Suhov. Information Theory and Coding by Example. Cam-
bridge University Press, Cambridge, 2013. 84
[39] Joseph B. Keller. The probability of heads. Amer. Math. Monthly, 93(3):191–197,
1986. URL: [Link] doi:10.2307/2323340. 17
[40] Auguste Kerchoffs. La cryptographie militaire. Journal des sciences militaires, pages
5–38, 1883. 149
/Users/dp/a/ens/[Link] 179
2021-12-23 • 14:43:13.
Références BIBLIOGRAPHIE
[43] Leon G. Kraft. A device for quantizing, grouping, and coding amplitude-modulated
pulses. PhD thesis, Massachusetts Institute of Technology, 1949. URL: http://
[Link]/1721.1/12390. 112
[44] R. Landauer. Irreversibility and heat generation in the computing process. IBM
Journal of Research and Development, 5(3):183–191, July 1961. doi:10.1147/rd.53.
0183. 97, 102
[45] 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.
URL: [Link] doi:10.1007/BFb0091534. 151
[46] 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. URL: [Link]
S0960129512000783, doi:10.1017/S0960129512000783. 84
[47] Eugene Lukacs. Characteristic functions. Hafner Publishing Co., New York, 1970.
Second edition, revised and enlarged. 37
[48] David J. C. MacKay. Information theory, inference and learning algorithms. Cambridge
University Press, New York, 2003. 84
[49] Ueli M. Maurer. Authentication theory and hypothesis testing. IEEE Trans. Inform.
Theory, 46(4):1350–1356, 2000. URL: [Link] doi:
10.1109/18.850674. 156
[51] Brockway McMillan. The basic theorems of information theory. Ann. Math. Sta-
tistics, 24:196–219, 1953. 114
[52] 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
[53] 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. 55
/Users/dp/a/ens/[Link] 180
2021-12-23 • 14:43:13.
BIBLIOGRAPHIE Références
[55] William A. Pearlman and Amir Said. Digital signal compression : principles and
practice. Cambridge University Press, 2011. 119
[56] Dimitri Petritis. Markov chains on measurable spaces, 2015. Premimi-
nary draft of lecture notes taught at the University of Rennes 1. URL:
[Link]
2_pdfsam_markov.pdf. 48, 55
[57] Dimitri Petritis. Mathematical foundations of quantum mechanics, 2018. Notes
de cours pour le master de cryptographie - version préliminaire, Univer-
sité de Rennes 1. URL: [Link]
enseignement/ptin/[Link]. 152
[58] Dimitri Petritis. Théorie de la complexité, 2018. Notes de cours pour le master
de cryptographie - version préliminaire, Université de Rennes 1. URL: http://
[Link]/[Link]/enseignement/lcm1/[Link]. 125,
155
[59] 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. URL: http:
//[Link]/10.1145/359340.359342, doi:10.1145/359340.359342. 151
[60] Steven Roman. Coding and information theory, volume 134 of Graduate Texts in Ma-
thematics. Springer-Verlag, New York, 1992. 142
[61] 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
[62] Claude E. Shannon. A mathematical theory of communication. Bell System Tech.
J., 27:379–423, 623–656, 1948. 83, 113
[63] Claude E. Shannon. Communication in the presence of noise. Proc. I.R.E., 37:10–
21, 1949. 2
[64] 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, 152, 153
[65] 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, 36, 40
[66] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete
logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. 151
[67] G. J. Simmons. A survey of information authentication. In Contemporary crypto-
logy, pages 379–419. IEEE, New York, 1992. 156
/Users/dp/a/ens/[Link] 181
2021-12-23 • 14:43:13.
Index BIBLIOGRAPHIE
[70] Karlheinz Spindler. Abstract algebra with applications. Vol. II. Marcel Dekker Inc.,
New York, 1994. Rings and fields. 162
[71] G. S. Vernam. Cipher printing telegraph systems for secret wire and radio telegra-
phic communications. Transactions of the American Institute of Electrical Engineers,
XLV:295–301, Jan 1926. doi:10.1109/T-AIEE.1926.5061224. 152
[72] Mark N. Wegman and J. Lawrence Carter. New hash functions and their use
in authentication and set equality. J. Comput. System Sci., 22(3):265–279, 1981.
Special issue dedicated to Michael Machtey. URL: [Link]
0022-0000(81)90033-7, doi:10.1016/0022-0000(81)90033-7. 159
[73] Jacob Ziv. Coding theorems for individual sequences. IEEE Trans. Inform. Theory,
24(4):405–412, 1978. 122
/Users/dp/a/ens/[Link] 182
2023-01-02 • 09:41:54.