Probabilités et applications à l’algorithmique, TD numéro 7 Entropie de Shannon et codage, théorie des questionnaires

Natacha Portier lundi 18 avril 2002

Question 1 : l’algorithme de Fano

Fixons D = 2 et supposons p_{1} ≥ p_{2} ≥ ... ≥ p_{k}. On regroupe les u premiers objets où u est le plus petit entier tel que

p_{1} + ... + p_{u} ≥ \frac{1}{2}

Nous obtenons ainsi une partition M de l’ensemble des objets en deux sous-ensemble M_{0} et M_{1}. Soient π_{0} et π_{1} les probabilités respectives de ces ensembles. Nous appliquons à M_{0} l’algorithme de dichotomie pour obtenir une partition M_{0} = M_{00} + M_{01} où M_{00} = {x_{1}, ..., x_{v}} et v est le plus petit entier tel que p_{1} + ... + p_{v} ≥ π_{0}/2. On applique à M_{1} ce même algorithme et on obtient la partition M_{1} = M_{10} + M_{11}. On continue l’algorithme ainsi de suite jusqu’à ce qu’on ne puisse plus appliquer la dichotomie, ce qui se produit quand un ensemble M_{a} ne comporte plus qu’un élément et a est alors le code de cet élément.

Question 1,2

Montrer que ce code est préfixe.

Question 1,3

Montrer que la longueur moyenne L vérifie H_{2}(p) ≤ L ≤ H_{2}(p) + 1.

Question 1,4

Ce codage est-il optimal ?

Question 2 : théorie des questionnaires

Imaginons que nous avons un objet pris parmi les x_{i} et que nous cherchons à l’identifier. Pour cela nous posons des questions auquelles les réponses possibles sont des lettres de l’alphabet A = {α_{1}, ..., α_{D}}. Les questions sont posées les unes après les autres et dépendent des réponses déjà obtenues. Nous avons donc un questionnaire Q = {Q_{m}/m ∈ A^{∗}}. La question Q_{m} appliquée à l’objet x_{j} donne la réponse α_{m,j}, ce qu’on note : Q_{m}(x_{j}) = α_{m,j}. Le questionnaire Q appliqué à x_{i} fournit donc la suite de réponses Q(x_{i}) = (a_{1,i}, a_{2,i}, a_{3,i}, ...) avec a_{k,i} = α_{a_{1,i}...a_{k−1,i},i}. Une règle d’arrêt est un sous-ensemble T de A^{∗}. Le couple (Q, T) où Q est un questionnaire et T une règle d’arrêt est un identificateur. Il lui correspond un codage h définit par : si Q(x_{i}) = (a_{1,i}, a_{2,i}, a_{3,i}, ...) et l_{i} = inf{n|a_{1,i}...a_{n,i} ∈ T } alors h(x_{i}) = a_{1,i}...a_{l_{i},i}. Un identificateur est admissible si h est bien défini et injectif.

Question 2,1

Soit (Q, T) un identificateur admissible. Montrer que h est préfixe.

Question 2,2

Soit h un codage préfixe. Donner un identificateur admissible (Q, T) correspondant au codage h.

La longueur moyenne du code h est le nombre moyen de questions à poser pour identifier un objet choisi au hasard selon la distribution p parmi les x_{i}. L_{inf} est donc le nombre moyen minimum de questions à D réponses que l’on doit poser pour identifier un objet tiré au sort selon la distribution p parmi k objets distinguables entre eux.

Question 2,3 : un problème de billes

On nous présente 15 billes rigoureusement identiques d’aspect et identiques en poids sauf pour l’une d’elles qui est légèrement plus lourde (un centième de poids en plus). Comment faire pour retrouver le plus rapidement possible en moyenne la bille de poids différent ? Et dans le pire des cas ? Et si on a douze billes et qu’on ne sait pas si la fausse est plus lourde ou plus légère ? Et si on le sait ? Et avec une balance qui peut juste renseigner sur l’éventuelle égalité de deux poids ?

Question 3 : H est bien une quantité d’information

Qu’est-ce qui justifie que H soit appelé quantité d’information plutôt que L_{inf} ?

Soit p = (p_{1}, ..., p_{k}) la distribution de probabilité d’entropie H des lettres x_{1}, ..., x_{k}. Soit n un entier. Calculer la distribution de probabilité p^{(n)} des mots de longueur n et son entropie H(p^{(n)}). Soit L_{inf}^{(n)} la longueur moyenne du codage optimal pour p^{(n)}. Donner un encadrement de la “quantité d’information par symbole” L_{inf}^{(n)}/n et conclure.

Question 4 : entropie

Les deux questions suivantes sont indépendantes. La base logarithmique utilisée pour le calcul de l’entropie est quelconque.

Question 4,1

Soit X une variable aléatoire qui prend les valeurs x_{1}, ..., x_{n} avec la distribution finie de probabilités p = (p_{1}, ..., p_{n}) et Y une variable aléatoire indépendante de X qui prend les valeurs y_{1}, ..., y_{l} avec la distribution finie de probabilités q = (q_{1}, ..., q_{l}). On appelle p ⊗ q la distribution de probabilité du couple (X, Y). Calculer l’entropie de p ⊗ q en fonction de celles de p et q.

Question 4,2

Soit p = (p_{1}, p_{2}) une distribution finie de probabilités. Donner les valeurs de p qui minimisent et maximisent son entropie H. Généraliser à une distribution p = (p_{1}, ..., p_{n}). (par convention , H(p_{1}, ..., p_{n−1}, 0) = H(p_{1}, ..., p_{n−1})).