La Température et le Théorème de Cramer

Lorsque l’on considère une sommes de variables indépendantes et identiquement distribuées, on pense d’abords à la loi des grands nombres puis au théorème centrale limite. En troisième position, bien que moins connus viennent les principes de grandes déviations qui affirment que la probabilité d’observer un écart significatif par rapport à la moyenne est exponentiellement petit. Les principes de grandes déviations sont également omniprésent en thermodynamique. Pour illustrer cela je refait ici pas à pas la démonstration du Théorème de Cramer.

Celle ci fait utilise plusieurs idées et notions qui ont leurs analogue en physique et que j’explicite ci dessous.

La borne supérieure et l’énergie libre

Par inégalité de Markov on a

et donc

Il convient ensuite de choisir le βE qui minimise le terme de droite pour obtenir la borne supérieure. Chaque terme ici a son importance et une signification physique. Je note

Quelques remarques :

  1. Boltzmann définit l’entropie comme kB log |Ω|. Ici on peut imaginer Ω comme un sous ensemble d’un plus grand ensemble Ω0 fixé et qu’il y a la probabilité associée  (Ω) = |Ω|/|Ω0|. La définition ci dessus = log (Ω) est alors essentiellement la même (aux constantes près).
  2. Le second principe de la thermodynamique : “le système maximise l’entropie” peut aussi être vu ici de manière quantitative comme “La probabilité d’observer un écart avec le maximum d’entropie est exponentiellement petite”.
  3. Le lien entre l’entropie et l’énergie libre via la transformé de Legendre apparait explicitement dans le Théorème de Cramer et on a bien la relation

La borne inférieure et la loi de Gibbs

L’idée ici consiste à modifier la loi aléatoire selon

avec une fonction positive. L’astuce ici est que les lois conditionnelles à la somme restent inchangées :

Ceci est bien sur une évidence mais cela signifie que si on s’intéresse à (X)i par exemple conditionnellement à ce que la somme soit égale à NE, on dispose d’une certaine liberté pour modifier la loi aléatoire. Un bon choix est alors

car alors les Xi restent alors des variables iid.

La deuxième astuce est de choisir β de telle sorte que pour cette nouvelle mesure, la moyenne de X soit égale à E. Cela correspond au même β βE que pour la borne supérieure. L’intérêt est qu’ici, par la loi des grand nombre, la somme des Xi  divisé par N converge vers E avec f-grande probabilité. On s’attend alors à ce que en conditionnant à l’égalité entre la somme et Non ne change pas trop la loi des (Xi):

D’un point de vue physique, ce changement de mesure de probabilité est ce qu’on appelle la distribution de Boltzmann (ou distribution de Gibbs). Cette dernière est omniprésente dans toute la physiques statistiques et décrit parfaitement le comportement de gaz ou de réactions chimiques. Elle peux même servir de définition à la notion de température : un système est à telle température ssi sa statistique obéit celle de Boltzmann avec le paramètre correspondant. Mathématiquement il semble que cela va beaucoup plus loin que juste la preuve du Théorème de Cramer et reflète quelque chose de plus fondamental à savoir comment est modifiée la loi de chacune des variables aléatoires lorsque l’on conditionne à un événement exceptionnel.

Si tout ceci n’est pas tout à fait rigoureux on a tout de même que

par le théorème centrale limite et que d’un autre coté

Ce qui termine la preuve de la borne inférieure.

De la cryptographie partagée

Je présente ici une idée très jolie signée Adi Shamir (le “S” dans “RSA”). Celle ci a déjà fait l’objet d’un article sur le site d’Images des Maths et comme elle est superbe je me permet de la réexpliquer ici.

Un groupe et un coffre fort

Un groupe de personnes partage un coffre fort (avec codes à chiffre) et décide d’organiser ensemble la sécurité. Le premier membre propose de simplement donner le code à chacun. Mais le reste du groupe n’est pas d’accord car la sécurité ne serait alors pas très élevée. Il suffit d’un membre soit malhonnête pour que tout soit compromis. Le deuxième membre propose de diviser la clef de sécurité en morceau et d’en donner un à chacun à la même manière des pirates découpant une carte au trésor. La seule façon d’ouvrir le coffre est alors que le groupe tout entier se réunisse. Mais cette idée est également rejetée car contre trop contraignante. Si un membre n’est plus là ou si il a oublié son code, le contenu du coffre est perdu. Un troisième membre ne propose pas de solution mais fait alors remarquer que plusieurs personnes du groupe (mais on ignore lesquelles mais moins que (k-1)) se mettraient volontiers ensemble pour partager leurs informations et ouvrir le coffre au détriment du reste du groupe.
Tout le monde se met alors d’accord sur le cahier des charges suivant:
Si au moins k membres du groupe se réunissent ils doivent toujours être capables d’ouvrir le coffre mais si il n’y a seulement que (k-1) personnes, alors il doit leur être impossible de deviner la combinaison.”
La difficulté ici est qu’il faut ces conditions doivent être valides quelques soient les sous ensembles de k ou (k-1) personnes. Une solution très élégante utilise de l’algèbre linéaire et je la présente maintenant.

Un simple système linéaire

Soit une famille de n vecteurs de dimension k : (a1,…,an) telle que pour toute sous famille de k vecteurs forme une base. Le code consiste maintenant en un vecteur c de de dimension k. À la i-ème personne du groupe on donne comme information le vecteur ai et le réel bi = (ai,c). Pourquoi cela fonctionne ? Pour tout sous ensemble L on a un système avec |L| équations dont l’ensemble des solutions est un espace affine de dimension k-|L| et qui admet donc une infinité de solution pour |L|<k. Par contre avec k personnes il suffit de résoudre (par exemple avec le pivot de Gauss) un système à k équations et k inconnus dont, avec la propriété des (ai), admet une unique solution.
Voici un exemple avec groupe de n=5 personnes A,B,C,D et E et k=3.
Si on suppose que B,C et E se réunissent, ils obtiennent ensemble le système suivant qu’ils peuvent facilement résoudre.
Mais bien sur avec seulement les équations de B et C ou seulement celles de C et E, le système admettrait une infinité de solution.
Il reste la question de comment construire une telle famille de vecteurs ai.
Une première méthode un peu bête mais très efficace et de simplement tirer des vecteurs aux hasards. Puisque sur l’ensemble des matrices k par k, det = 0 est une sous variété de dimension inférieur, la probabilité de toucher cet espace est nulle avec une probabilité continu.
Une deuxième méthode (et celle proposée initialement) et de se placer dans l’espace des polynômes de degré k-1. Le code consiste en les coefficients d’un polynôme P et on donne comme information à chacun « (x,P(x)) » pour des valeurs x différents. Si on revient à notre exemple à 5 personnes, on pourrait avoir
Ceci satisfait les conditions du problème car le déterminant de Vandermond est non nul dès que les x sont différents. Ici résoudre le système est également facile en utilisant les polynômes d’interpolation de Lagrange.