T HÉORIE DE L’ INFORMATION Session 1
Remarque préliminaire : Les exercices (ou parties d’exercice) marqués d’une étoile (F)
sont facultatifs et ne concernent que les élèves motivés et intéressés.
Exercice I :
Considérons deux dés (à six faces) l’un pipé et l’autre non. Soit X la v.a. résultat du tirage
sur le dé non-pipé et Y la v.a. résultat du tirage sur le dé pipé. Supposons que la distribution
de probabilités de Y soit :
1 2 3 4 5 6
0.1 0.17 0.15 0.19 0.17 0.22
La distribution de X est bien entendu uniforme sur J1, 6K.
a- Quelle est la probabilité d’avoir un double 6
1. en tirant deux fois le dé non-pipé ?
2. en tirant deux fois le dé pipé ?
3. en tirant le dé non-pipé puis le dé pipé ?
4. en tirant le dé pipé puis le dé non-pipé ?
b- Pour une fonction f quelconque, exprimer E[f (X)] et E[f (Y )].
c- Quelle est l’entropie de chaque dé ?
F d- On observe la séquence 1, 1, 4, 6. Sachant qu’un seul des deux dés a été utilisé, lequel
selon vous a été choisi ?
Solution de l’exercice I :
a1) p = (1/6) · (1/6) ' 2.8 %
a2) p = 0.22 · 0.22 ' 4.8 %
a3) p = (1/6) · 0.22 ' 3.7 %
a4) L’ordre de tirage ne change pas les probabilités, c’est donc la même probabilité que
ci-dessus.
b)
X
E[f (X)] = PX (x) f (x)
x∈X
6
X
= PX (i) f (i)
i=1
X6
= (1/6) · f (i)
i=1
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 1/8
FÉ DÉR A L E D E L A U S A N N E
T HÉORIE DE L’ INFORMATION Session 1
6
1 X
= f (i)
6 i=1
6
X
E[f (Y )] = PY (i) f (i)
i=1
= 0.1 · f (1) + 0.17 · f (2) + 0.15 · f (3) + 0.19 · f (4) + 0.17 · f (5) + 0.22 · f (6)
c) Puisque X a une distribution uniforme, on sait que H(X) est maximal et vaut H(X) =
log 6 ' 2.6 bit1 .
H(Y ) = 0.1 log 1/0.1 + 0.17 log 1/0.17 + 0.15 log 1/0.15 + 0.19 log 1/0.19
+0.17 log 1/0.17 + 0.22 log 1/0.22
' 2.55 bit
H(Y ) < H(X) : le dé pipé est (évidemment) moins incertain que le dé non pipé (c’est
justement pour cela que l’on pipe les dés !).
F d) L’approche « empirique » consiste à calculer les probabilités que la séquence 1,1,4,6
ait été produite dans chacun des deux cas, puis à choisir le cas où cette probabilité est
maximale (c.-à-d. que l’on suppose que les deux dé ont une chance a priori égale d’avoir
été choisi).
Cette approche empirique donne :
– dans le cas de l’utilisation du dé non-pipé :
P (1, 1, 4, 6) = (1/6)4 ' 7.7 · 10−4
– dans le cas de l’utilisation du dé pipé :
P (1, 1, 4, 6) = 0.12 · 0.19 · 0.22 ' 4.2 · 10−4
L’approche empirique favoriserait donc l’hypothèse de l’utilisation du dé non-pipé.
En regardant moins empiriquement le problème, ce qui nous préoccupe est de trouver
le dé le plus probable étant donnée cette séquence observée ; c.-à-d. le dé qui maximise
P (dé|séquence = 1, 1, 4, 6). Or, ce que nous savons facilement calculer c’est (comme nous
l’avons fait ci-dessus dans l’approche empirique) P (séquence = 1, 1, 4, 6|dé). On passe de
l’un à l’autre à l’aide de la formule de Bayes :
P (séquence = 1, 1, 4, 6|dé) · P (dé)
P (dé|séquence = 1, 1, 4, 6) =
P (séquence = 1, 1, 4, 6)
1
Remarque : le log est ici le logarithme en base 2, c.-à-d. log x = ln x/ ln 2.
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 2/8
FÉ DÉR A L E D E L A U S A N N E
T HÉORIE DE L’ INFORMATION Session 1
La séquence observée étant fixée, maximiser P (dé|séquence = 1, 1, 4, 6) revient donc à
maximiser le produit P (séquence = 1, 1, 4, 6|dé)·P (dé). Ce qui fait le lien avec l’approche
empirique : sans autre information a priori (c.-à-d. sans la connaissance de la distribution
P (dé)), on fait l’hypothèse d’incertitude maximale, c.-à-d. d’équirépartition des choix a
priori des dés. On retrouve alors l’approche qualifiée ici d’« empirique » et qui s’appelle
plus généralement approche « maximum de vraissemblance ».
Exercice II :
Soit une v.a. X à valeurs dans {0, 1, 2} de distribution de probabilité :
P (X = 0) = 0.1 P (X = 1) = 0.2 P (X = 2) = 0.7
a- Que vaut E [P (X)] ? E [log10 P (X)] ? E [1/P (X)] ?
F b- Quelle est la probabilité que P (X) ∈ [0.12, 0.39] ?
P(X)
c- Que vaut Pr log10 0.2 > 0.034 ?
Solution de l’exercice II :
E [P (X)] = 0.1 · 0.1 + 0.2 · 0.2 + 0.7 · 0.7 = 0.54
E [log P (X)] = 0.1 · log 0.1 + 0.2 · log 0.2 + 0.7 · log 0.7 ' −1.16
E [1/P (X)] = 0.1/0.1 + 0.2/0.2 + 0.7/0.7 = 3
De façon générale, E [1/P (X)] = |X|, i.e. le nombre de valeurs possibles pour X.
F Pour b), introduisons Z la v.a. booléenne définie par Z = g(X), avec :
vrai si P (X = x) ∈ [0.12, 0.39]
g(x) =
faux sinon
Ainsi quand X = 0, Z = faux, quand X = 1, Z = vrai et quand X = 2, Z = faux. D’où :
Pr (Z = vrai) = P (X = 1) = 0.2
Pour c), introduisons de même W = h(X) avec :
(
P(X)
vrai si log 0.2 > 0.034
h(x) =
faux sinon
On a :
Pr (W = vrai) = Pr (X = 0 ou X = 2) = P (X = 0) + P (X = 2) = 0.8
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 3/8
FÉ DÉR A L E D E L A U S A N N E
T HÉORIE DE L’ INFORMATION Session 1
Exercice III :
Qu’est-ce qui est le plus incertain : jouer au Loto simple (c.-à-d. trouver 6 bons numéros
parmi 45), au quarté sur 12 chevaux ou tirer un carré d’as dans un jeu de 52 cartes (en ne
tirant que 4 cartes) ? Calculer les entropies de ces trois « jeux ».
Solution de l’exercice III :
Si nous supposons qu’aucun de ces trois jeux ne soit truqués. Nous sommes donc à chaque
fois dans une situation d’équirépartition. Le plus incertain est donc celui qui offre le plus
de possibilités.
45
Pour le Loto, le nombre de possibilité est = 8145060 (trouver un sous-ensemble à 6
6
éléments parmi 45).
Pour le quarté, il y a 12 · 11 · 10 · 9 résultats possibles, soit 11880.
52
Pour le carré d’as enfin, nous avons une chance sur = 270725.
4
Le plus incertain est donc le Loto2 .
Puisqu’il y a équiprobabilité, l’entropie est maximale et vaut :
H(Loto) = log(8145060) ' 23.0 bit
H(quarté) = log(11880) ' 13.5 bit
H(poker) = log(270725) ' 18.0 bit
Exercice IV :
a- On tire à pile ou face avec une pièce non truquée jusqu’à obtenir pile. Quels sont les
nombres moyens de piles et de faces obtenus ?
b- Même question avec une pièce truquée.
c- Quelle est l’entropie du nombre de faces obtenu ?
Solution de l’exercice IV :
Que la pièce soit truquée ou non, le nombre de piles obtenu est 1 par définition !
Notons à présent p la probabilité d’avoir face lors d’un tirage et F la v.a. « nombre de faces
obtenus » (au cours de toute l’expérience).
2
avec les règles simples utilisées ici. Pour le vrai Loto le calcul est sensiblement plus compliqué !
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 4/8
FÉ DÉR A L E D E L A U S A N N E
T HÉORIE DE L’ INFORMATION Session 1
Remarquons que si l’on a eu face au premier jet3 , on se retrouve en ce qui concerne le
tirage dans une situation identique à celle de départ (à savoir : tirer jusqu’à avoir un pile)
dont le nombre moyen de faces est le même qu’avant d’avoir tiré ce premier face (car le
processus stochastique "tirer à pile ou face jusqu’à obtenir pile" est sans mémoire) ; on a
donc en moyenne dans ce cas là le nombre moyen de faces plus 1 (celui que l’on vient de
tirer).
Si par contre on tire directement un pile, le nombre de face (et donc a fortiori le nombre
moyen) est 0.
La première situation se produisant avec une probababilité p et la seconde avec une proba-
bilité 1 − p, on peut donc écrire :
E[F ] = p · (1 + E[F ]) + (1 − p) · 0
d’où :
p
E[F ] =
1−p
qui vaut 1 pour une pièce non truquée (p = 0.5).
Pour les personnes peu convaincues par cette démonstration subtile, sortons les marteaux-
pilons : la probabilité que l’on ait n faces est :
Pr (F = n) = pn · (1 − p)
et donc :
∞ ∞
X X p p
E[F ] = n Pr (F = n) = n pn (1 − p) = (1 − p) 2
=
n=0 n=0
(1 − p) 1−p
qui vaut 1 pour une pièce non truquée. Ceci confirme bien l’intuition que pour une pièce
non truquée le nombre moyen de faces est intuitivement égal au nombre de pile(s) (puis-
qu’on a une chance sur deux d’avoir pile, en moyenne au bout de 2 tirages on a pile, c.-à-d.
en moyenne après avoir tiré une fois face).
c) En ce qui concerne le calcul de l’entropie :
∞
X
−H(F ) = pn (1 − p) log (pn (1 − p))
n=0
" ∞ ∞
#
X X
= (1 − p) n pn log p + pn log(1 − p)
n=0 n=0
p 1
= (1 − p) log(p) 2
+ (1 − p) log(1 − p)
(1 − p) (1 − p)
p
= log(1 − p) + log p
1−p
3
ceci se produit avec une probabilité p.
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 5/8
FÉ DÉR A L E D E L A U S A N N E
T HÉORIE DE L’ INFORMATION Session 1
Pour p = 0.5, on obtient : H(F ) = 2 bit.
Exercice V :
F Montrer que pour une v.a. (discrète) X quelconque, on a :
H(X) = log |X| − D(PX ||U )
où |X| est le nombre de valeurs (presque sûrement) prises par X et U est la distribution
uniforme sur ces valeurs.
Intéret de l’exercice : Faire le lien entre l’entropie et la divergence par rapport à la distri-
bution uniforme.
Solution de l’exercice V :
X
H(X) = − PX (x) log PX (x)
x∈X
X X
= log |X| − [PX (x) log |X|] − PX (x) log PX (x)
x∈X x∈X
X
= log |X| − PX (x) [log PX (x) + log |X|]
x∈X
X
= log |X| − PX (x) log(PX (x) · |X|)
x∈X
X PX (x)
= log |X| − PX (x) log
x∈X
1/|X|
= log |X| − D(PX ||U )
avec U la distribution de probabilité uniforme 1/|X| sur toutes les valeurs de X.
Exercice VI :
F Soient P et Q deux distributions de probabilité sur {0, 1}. Calculer D(P||Q) et D(Q||P).
Quid si Q est uniforme ?
Intéret de l’exercice : Montrer que D(P ||Q) n’est pas une distance au sens mathématique.
Solution de l’exercice VI :
Soit p et q la probabilité de 0 respectivement dans les distributions P et Q. Alors :
p 1−p
D(P ||Q) = p log + (1 − p) log
q 1−q
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 6/8
FÉ DÉR A L E D E L A U S A N N E
T HÉORIE DE L’ INFORMATION Session 1
= p log p + (1 − p) log(1 − p) − p log q − (1 − p) log(1 − q)
= −h(p) − [p log q + (1 − p) log(1 − q)]
q 1−q
D(Q||P ) = q log + (1 − q) log
p 1−p
= −h(q) − [q log p + (1 − q) log(1 − p)]
Si Q est uniforme, alors q = 0.5 et
D(P ||Q) = 1 − h(p)
1
D(Q||P ) = −1 −
log (p (1 − p))
2
qui sont différentes pour p 6= 0.54 (cf figure page suivante).
4
D(P ||Q) n’est donc pas une distance au sens mathématique.
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 7/8
FÉ DÉR A L E D E L A U S A N N E
T HÉORIE DE L’ INFORMATION Session 1
4
D(x,0.5)
D(0.5,x)
3.5
2.5
1.5
0.5
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
ÉC O L E P O L Y T E C H N I Q U E
DI-LIA 8/8
FÉ DÉR A L E D E L A U S A N N E
