$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Introduction à la théorie de l'information

  On considère une épreuve aléatoire, et une variable aléatoire X associée à cette épreuve. Comment mesurer l'information moyenne apportée par la connaissance de X sur l'épreuve aléatoire? Prenons l'exemple suivant : on lance un dé non pipé et on considère les 3 variables aléatoires suivantes :
  • X1 qui vaut 0 si le nombre tiré est pair, 1 s'il est impair.
  • X2 qui vaut 0 si le nombre tiré est 1 ou 2, 1 si le nombre tiré est 3 ou 4, 2 si le nombre tiré est 5 ou 6.
  • X3 qui vaut le nombre tiré.
  Il est intuitivement clair que la connaissance de X3 renseigne plus sur le déroulement de l'épreuve aléatoire que la connaissance de X2, qui elle-même renseigne plus que celle de X1. La notion d'entropie permet de mathématiser cette heuristique :
Définition : Si X est une variable aléatoire discrète, l'entropie de X est définie par :
Dans cette définition, la base du logarithme est souvent choisie égale à 2. L'entropie se mesure alors en shannons, ou en bits (binary information unit).

  Il nous faut encore mesurer l'incertitude ou le désordre, liée à l'expérience aléatoire. Si {a1,...,aN} est l'ensemble des issues possibles de l'expérience, l'entropie vaut :
On retrouve ici la définition physique (ou mieux, thermodynamique) de l'entropie : mesure du désordre d'un système. La variable aléatoire X renseigne totalement sur le déroulement de l'expérience E si H(X)=H(E).

Ex :
  1. Si X est une variable aléatoire équidistribuée qui peut prendre n valeurs, l'entropie de X est :
    Il est facile de voir que parmi les variables à n valeurs, l'entropie H(X) est maximale lorsque X est équirépartie : une variable aléatoire apporte en moyenne un maximum d'informations lorsqu'elle peut prendre chaque valeur avec une égale probabilité.
  2. Dans l'exemple du dé, on vérifie que :
    Dans cet exemple, l'incertitude totale liée à l'expérience est log 6.
  3. On vous présente 10 cartons sur lesquels sont inscrits sur la face cachée un nombre (tous les nombres sont différents). Vous pouvez poser des questions du type : "Est-ce que le nombre sur ce carton est plus élevé que sur celui-là". Vous payez un franc par question, et vous en recevez 15 lorsque vous savez réordonner les cartons. Acceptez-vous de jouer?

      Il y a 10! façons d'ordonner les cartons. L'incertitude sur l'ordre dans lequel ils sont rangés vaut donc log(10!)=21,8 shannons environ. Chaque réponse apporte au plus un shannon d'information. Il faudra, du point de vue de la théorie de l'information, 22 questions en moyenne pour reconstituer l'ordre. Il ne faut pas jouer!

      L'argument précédent est toutefois heuristique. Il ne dit pas en particulier quelles sont les questions à poser pour retrouver l'ordre après 22 questions.
La théorie de l'information a été mise au point par Shannon en 1947. Son projet était de quantifier la sécurité des méthodes de cryptographie. En particulier, il a montré que l'algorithme utilisé pour chiffrer le téléphone rouge entre Moscou et Washington était le plus sûr possible.