Centrale Mathématiques 1 TSI 2017Sujet et corrigé

Ce problème aborde la question de la mesure quantitative de l'information.
La première partie étudie quelques propriétés de la fonction logarithme népérien utiles pour les autres parties du problème.
La deuxième partie vise à construire les fonctions permettant de modéliser l'information contenue dans les événements de probabilité non nulle d'un espace probabilisé. L'information contenue dans un tel événement correspond intuitivement à l'effet de surprise provoqué par la réalisation de cet événement.
La troisième partie aborde la notion d'entropie d'une variable aléatoire discrète à valeurs entières.
La quatrième partie aborde l'entropie d'un couple de variables aléatoires et la notion d'entropie conditionnelle. L'exemple traité dans la cinquième partie établit le lien entre la quantité d'information contenue dans un message aléatoire et le nombre minimal de questions que le récepteur du message doit poser à son émetteur pour pouvoir identifier sans ambiguïté l'une des réalisations de ce message.

I.A - Représenter graphiquement la fonction logarithme népérien.
I.B - Démontrer que, pour tout x ∈ ℝ^(+ ∗), ln(x) ⩽ x − 1 et que ln(x) = x − 1 si et seulement si x = 1.
I.C - Donner une interprétation graphique de ces deux résultats.
I.D - Montrer que la fonction g définie sur [0, 1] par g(0) = 0 et ∀x ∈ ]0, 1], g(x) = xln(x) est continue sur [0, 1] et dérivable sur ]0, 1]. Représenter graphiquement la fonction g.

Soit ( Ω, P ) un espace probabilisé fini. On convient de modéliser la quantité d'information contenue dans les événements de probabilité non nulle par une fonction S définie par

où f : ]0, 1] → ℝ vérifie les contraintes suivantes :
i. f(1) = 0
ii. f est décroissante sur ]0, 1]
iii. ∀(p, q) ∈ ]0, 1]^2 f(pq) = f(p) + f(q)
iv. f est continue sur ]0, 1]
II.A - Quelle est la quantité d'information de l'événement certain? Interpréter en terme d'effet de surprise.
II.B - Que peut-on dire de la quantité d'information contenue dans l'événement A ∩ B lorsque A et B sont indépendants? Interpréter en terme d'effet de surprise.
II. C - Donner un exemple de fonction f vérifiant les quatre contraintes i, ii, iii et iv.
II. D - On se propose de déterminer l'ensemble des fonctions vérifiant ces quatre contraintes.

Soit f une telle fonction.
II.D.1) Soit p ∈ ]0, 1]. Établir, à l'aide d'un changement de variable, l'égalité

II.D.2) En déduire que f est dérivable sur ]0, 1].
II.D.3) Dans cette question, on fixe p ∈ ]0, 1]. En dérivant par rapport à q l'égalité iii, démontrer l'existence d'un réel a indépendant de p tel que f^′(p) = a/p. Préciser la valeur de a.
II.D.4) L'égalité f^′(p) = a/p étant vraie quel que soit p dans ]0, 1], déterminer l'ensemble des fonctions f vérifiant les quatre contraintes i, ii, iii et iv.
II.D.5) Montrer que parmi ces fonctions, il en existe une et une seule vérifiant en plus l'égalité f(1/e) = 1.

Cette fonction, notée h dans la suite du problème, correspond au choix d'une unité particulière (le logon) pour mesurer la quantité d'information.
Que vaut lim_(p → 0^+)h(p) ? Interpréter ce résultat.
II.D.6) On réalise l'expérience aléatoire consistant à effectuer deux lancers successifs d'un dé équilibré à six faces. On considère les évènements suivants

Ordonner les quantités d'information contenues dans chacun de ces trois événements. Interpréter en terme d'effet de surprise.

III. A - Dans cette sous-partie, toutes les variables aléatoires considérées sont définies sur un même univers fini Ω et prennent leurs valeurs dans [ [0, n] ].
Si X est une telle variable, on note p_k = P(X = k). On définit l'entropie de X par

en convenant que p_k ln(p_k) vaut 0 lorsque p_k = 0.
III.A.1) Interpréter H(X) comme une espérance, puis en terme de quantité d'information.
III.A.2) Montrer que H(X) ⩾ 0 et que H(X) = 0 si et seulement si X est une variable aléatoire certaine, c'est-à-dire

a) X_0 est une variable aléatoire suivant la loi uniforme sur [ [0, n] ]. Calculer H(X_0).
b) En appliquant l'inégalité de la question I.B à un nombre réel x bien choisi, démontrer que

c) En déduire que H(X) ⩽ H(X_0) avec égalité si et seulement si X suit la même loi que X_0 (pour le cas d'égalité on pourra utiliser le cas d'égalité de la question I.B). Interpréter ce résultat en terme de quantité moyenne d'information.
III. B - Dans cette sous-partie, on s'intéresse à des variables aléatoires discrètes définies sur un espace probabilisé ( Ω, P ) et prenant leurs valeurs dans ℕ^∗. Si X est une telle variable pour laquelle P(X = k) est noté p_k, on dit qu'elle est d'entropie finie si la série ∑p_k ln(p_k) est absolument convergente et on définit alors son entropie par

en convenant à nouveau que p_k ln(p_k) vaut 0 lorsque p_k = 0.
III.B.1) Pour p ∈ ]0, 1[, X_1 est une variable aléatoire suivant la loi géométrique de paramètre p.

Rappeler les valeurs de P(X_1 = k) et de l'espérance de X_1 (aucune démonstration n'est demandée).
Démontrer que X_1 est d'entropie finie et que H(X_1) = − (1 − p)/pln(1 − p) − ln(p).
III.B.2) Dans cette question et la suivante, X est une variable aléatoire à valeurs dans ℕ^∗ d'espérance finie.

On note E(X) = ∑_(k = 1)^(+ ∞)kp_k. On se propose de démontrer que X est d'entropie finie.
a) Quelle est la limite de p_k lorsque k tend vers + ∞ ?
b) En déduire que lim_(k → + ∞)√(p_k)ln(p_k) = 0, puis qu'il existe un entier k_0 tel que ∀k ⩾ k_0 0 ⩽ − √(p_k)ln(p_k) ⩽ 1.
c) Soit k ⩾ k_0. Montrer que

c) Démontrer que

d) En déduire que

puis que

On pourra utiliser l'inégalité démontrée dans la question I.B.
Interpréter ce résultat en terme de quantité moyenne d'information.

Dans cette partie, m et n sont des entiers naturels non nuls. ( X, Y ) et ( X^′, Y^′ ) sont deux couples de variables aléatoires discrètes. X et X^′ sont à valeurs dans [ [0, n] ], Y et Y^′ sont à valeurs dans [ [0, m] ]. Pour i ∈ [ [0, n] ] et j ∈ [ [0, m] ], on note p_i = P(X = i), q_j = P(Y = j), λ_(ij) = P(X = i; Y = j) et λ_(ij)^′ = P(X^′ = i; Y^′ = j).
On suppose que, pour tout (i, j) ∈ [ [0, n] ] × [ [0, m] ], λ_(ij) ≠ 0 et λ_(ij)^′ ≠ 0.

On définit l'entropie du couple ( X, Y ) par

On définit l'information entre les couples ( X, Y ) et ( X^′, Y^′ ) par

IV.A.1) Rappeler les valeurs de ∑_(i = 0)^n∑_(j = 0)^m λ_(ij) et de ∑_(i = 0)^n∑_(j = 0)^m λ_(ij)^′ et en déduire que

IV.A.2) À l'aide de l'inégalité de la question I.B, établir que K(X, Y, X^′, Y^′) ⩾ 0, et que l'égalité a lieu si et seulement si les deux couples ( X, Y ) et ( X^′, Y^′ ) ont la même loi conjointe.
IV.A.3) On suppose que les deux variables X^′ et Y^′ sont indépendantes, que X^′ suit la même loi que X et que Y^′ suit la même loi que Y.
Démontrer que K(X, Y, X^′, Y^′) = H(X) + H(Y) − H(X, Y). Déduire de ce qui précède que

Donner une condition nécessaire et suffisante pour que cette inégalité soit une égalité.
Remarque - L'inégalité (IV.1) a été obtenue en supposant, pour tout (i, j) ∈ [ [0, n] ] × [ [0, m] ], λ_(ij) ≠ 0 et λ_(ij)^′ ≠ 0. On admet qu'elle reste vraie même en dehors de cette condition

On définit l'entropie conditionnelle de Y sachant X par H_X(Y) = H(X, Y) − H(X).
Elle mesure l'incertitude restant sur la valeur de Y lorsque la valeur de X est connue.
IV.B.1) Montrer que H_X(Y) ⩽ H(Y). Interpréter cette inégalité.
IV.B.2) On considère m + 1 réels a_0, a_1, …, a_m compris entre 0 et 1 .
a) Dans cette question, on suppose (a_0, a_1, …, a_m) ∈ ]0, 1]^(m + 1).

Démontrer que, pour tout j ∈ [ [0, m] ], ln(a_j) ⩽ ln(a_0 + a_1 + ⋯ + a_m).
En déduire l'inégalité

La fonction g a été définie dans la partie I .
b) L'inégalité (IV.2) reste-t-elle vraie si (a_0, a_1, …, a_m) ∈ [0, 1]^(m + 1) ?
c) Montrer que l'inégalité (IV.2) est une égalité si et seulement s'il existe au plus un indice j ∈ [ [0, m] ] pour lequel a_j ≠ 0.
IV.B.3) Montrer que, pour tout i ∈ [ [0, n] ], ∑_(j = 0)^m g(λ_(ij)) ⩽ g(p_i). En déduire que H_X(Y) ⩾ 0.

Un jeu oppose deux joueurs A et B. Une urne contient 2016 boules indiscernables au toucher numérotées de 0 à 2015. Le joueur A tire une boule au hasard dans l'urne. On note Y la variable aléatoire égale au numéro de la boule tirée par le joueur A. Le joueur B pose alors au joueur A une série de N questions amenant la réponse « oui» ou « non » lui permettant de déterminer sans ambiguïté la valeur prise par Y. Le but de cette partie est de trouver la valeur minimale de N si B procède par dichotomies successives.
V.A - Déterminer l'entropie de Y.
V. B - La première question posée par B est « Y est-il compris entre 1008 et 2015 ? » La réponse fournie par A lui permet de positionner Y par rapport 1008. Si la réponse de A est «oui», B posera X_1 = 1 et cherchera ensuite à positionner Y par rapport à 1512 . Si la réponse à la première question est «non», B posera X_1 = 0 et cherchera à positionner Y par rapport à 504 . Il continue selon le même procédé.
Expliquer pourquoi le joueur B finira par trouver la valeur de Y. Au bout de combien de questions?
V.C - On se propose de donner une interprétation de ce résultat en terme d'entropie. Les variables aléatoires (X_1, X_2, …, X_N) sont renseignées par les réponses données par A à la première, la deuxième, ..., la N-ième question.
On pose X = ∑_(i = 1)^N X_(N + 1 − i)2^(i − 1). On admet que X est une variable aléatoire.
Montrer qu'elle prend ses valeurs dans [ [0, 2^N − 1] ]. On ne cherchera pas la loi de X.
V.D - Démontrer que H(X) ⩽ Nln(2).
On pourra utiliser l'inégalité vue à la question III.A.3.
V.E - Expliquer en langage courant pourquoi H_Y(X) = 0. En déduire que H(X, Y) = H(Y).
V. F - Montrer que H_X(Y) ⩾ ln(2016) − Nln(2).
V.G - En combien de questions le joueur B est-il certain de pouvoir trouver à coup sûr la valeur de Y ? Comparer au résultat de la question V.B.