Le problème du collectionneur et la loi de Poisson

A-Un petit problème du collectionneur (généralisé)

Je souhaiterai apprendre une langue comme le chinois par exemple. Pour cela je procède de la façon suivante. J’ouvre un livre, la radio ou la Télé et au hasard, je choisis un mot que j’écris sur un cahier et je l’append. Puis je recommence plusieurs fois. Si je tombe sur un mot que je connais déjà tant pis, je n’apprend rien de nouveau. Pour ce problème on introduit naturellement la loi de probabilité p(i) sur les mots i qui est la fréquence d’utilisation du mot en question dans la langue courante. Au bout de N (grand) itérations combien de mots ai je appris? Soit S une phrase avec quelle probabilité suis je capable de comprendre tous les mots de S? Combien faut-il d’itérations pour que je connaisse enfin tous les mots (Problème du collectionneur généralisé)?

B-Astuce utilisant la loi de Poisson

Il est possible d’obtenir très facilement une solution en modifions un peu le problème de la manière suivante : on remplace le nombre déterministe N d’itérations par un nombre aléatoire tiré suivant une loi de Poisson de moyenne N. Ce changement ne modifie que très légèrement notre problème puisque l’on va tirer N caractères plus ou moins une erreur d’ordre racine de N (TCL). On utilise alors une propriété extrêmement utile de la loi de Poisson : “Soit P une loi de poisson de paramètre d et X(1),X(2),X(3),… des variables aléatoire discrète sur un ensemble A et indépendantes et identiquement distribuées. Alors les variables

pour a dans A forment une famille de variables aléatoires indépendante qui suivent une loi de Poisson de paramètre d fois Prob(X=a)”. On applique cette propriété à notre problème et on a que pour tout mot i, le nombre de fois que ce mot a été tiré est une loi de Poisson de paramètre Np(i). Je connais donc le mot avec proba 1-exp(-Np(i)). Qui plus est, le tirage de chaque mot est indépendant et donc par exemple je connaitrai la phrase ‘ijk’ avec probabilité [1-exp(-Np(i)][1-exp(-Np(j))][1-exp(-Np(k))] Et pour connaitre tous les mots avec proba

Remarquer que pour p(i)=1/|I| (problème du collectionneur usuel), log(p) vaux environ -|I|exp(-N/|I|) et donc p tend vers 1 si N plus grand que |I|log(|I|) et vers 0 si N plus petit que |I|log(|I|).

Pour un problème d’apprentissage élémentaire par ordinateur, ceci donne un idée grossière du nombre de données à utiliser.

C-Le modèle grand canonique en physique statistique

Le modèle grand canonique, universellement utilisé en physique statistique utilise plus ou moins la même astuce. Plutôt que d’étudier le système avec N particules (modèle canonique) on relâche cette contrainte et on laisse le nombre de particules aléatoire dont la loi est centré autour de N. Par exemple : soit un système ayant k états d’énergie E(1),…,E(k) et N particules. L’énergie total E du système est la somme des E(i)N(i) avec N(i) le nombre de particule dans l’état i. La probabilité de chaque état est proportionnel à eβE ce qui revient à dire que chaque particule se place en avec proba

de manière indépendant. Modifions le système en supposant que le nombre de particules est donné par une loi de Poisson de moyenne N. Alors le nombre de particules dans les états i, deviennent des loi de Poisson indépendantes et de paramètre Np(i) que l’on réécrit souvent introduisant le potentiel chimique eβμ qui vaut

D-Un petit modèle de serveur

Voici un troisième petit modèle où cette astuce simplifie considérablement de problème.

On dispose d’un arbre binaire de serveurs pour traiter des requêtes. Les requêtes arrivent à la racines. Si il n’y a qu’une requête, le serveur à la racine la traite. Si il y en a plus qu’une le serveur est saturé et ne fait rien. Par contre chaque requête est redirigée vers l’un des deux serveur fils de l’arbre et de manière aléatoire (Bernoulli p=1/2 ) et indépendante. Les deux serveurs fils se comporte alors exactement de la même manière, traitant une requête si elle est seule, ou redirigeant de manière aléatoire les requêtes vers les serveurs suivant dans l’arbre.

Question : on envoie N requêtes à la racine, quelle profondeur de l’arbre est nécessaire pour traiter ces requêtes.

Réponse : si on remplace le nombre de requêtes à la racine par une loi de poisson de paramètre N, alors après répartition le nombre de requêtes de chaque serveur fils est donné par une loi de Poisson de paramètre N/2 et indépendante. On retrouve ainsi deux copies identiques et indépendantes de notre problème. À la profondeur k il y a 2k copies de Poisson indépendantes de paramètre N∕2k . La probabilité à ce que aucun serveur à cette profondeur n’ai deux requêtes est bornée par 2k (N/2k)ce qui donne la profondeur ≈ 2log2(N).

Deux petits exemples en théorie des jeux

Je présente ici deux petits modèles de théorie des jeux que je trouve intéressant car ils mènent à des conclusions complètement contraire à ce qu’on aurait pu s’attendre à première vu.

Une route trop efficace qui mène à des embouteillages.

Une ville A est connectée à une ville C par deux routes, celle passant par B et celle passant par D. Chacune est composée de deux tronçons : une partie route de campagne  (trait plein) et une partie autoroute (pointillés) comme sur le schéma. Sur la route de campagne la vitesse est limité et le temps pour la parcourir est toujours le même 1 heure. Sur l’autoroute
on peut aller plus vite mais si il y a trop de monde, on doit ralentir à cause des bouchons. Pour la traverser, on met p heure où p entre 0 et 1 est la proportion de personnes circulant sur la route.

Les automobilistes cherchent toujours à mettre le moins de temps possible et choisiront une routes plus rapide si ils en ont l’occasion. Dans la situations présente si une proportion trop importante prennent la route, la deuxième devient plus rapide car moins fréquenté. Des automobilistes changeront alors de trajets les jours suivants. Les
fréquentations s’équilibrent avec la moitié des conducteurs sur chacune des routes. Au finals le temps pour aller de A à C sera 1+0,5=1,5.

Ajoutons maintenant une super-route entre B et D. Extrêmement rapide et sans bouchons, on peut la parcourir presque instantanément.

Dans cette nouvelle situation, les automobilistes peuvent si ils le souhaitent n’utiliser que des autoroutes et la super route. Comme c’est toujours le choix préférable, personne n’a intérêt à ne pas le faire. Au final tout le monde emprunte les autoroutes. Mais cela
provocant des embouteillages, le temps total est alors 2 heures qui est pire que la situation sans la super route.

Se mettre en difficulté est parfois préférable.

Ici c’est un simple jeux à deux joueurs Valérie et Thomas et qui se joue en un seul tour. Valérie commence et choisit entre deux possibilités a ou b, puis c’est au tour de Thomas de choisir entre deux possibilités X ou Y. C’est fini. Chacun des joueurs gagnent le nombre de point selon le tableau suivant.

Chaque joueur vise le plus de gain possible. Valérie est donc capable de prédire le coup de Thomas. Si elle joue a, Thomas aura intérêt à jouer X. Il gagnera alors 2 points et Valérie 4. Si maintenant Valérie joue b, alors elle doit s’attendre à ce que Thomas joue Y
avec pour résultat 2 point pour Valérie et 5 point pour Thomas. Pour Valérie, la meilleur stratégie est donc de choisir a. Résultat final : (4,2).

Changeons maintenant la grille de la manière suivante.

Remarquez que les score de Valérie n’ont pas changés, par contre quelque soit le résultat final Thomas gagne moins de point que la situation précédente.

Reprenons maintenant le jeu: Si Valérie joue a, Thomas choisira Y ce qui n’intéresse pas du tout Valérie. Elle jouera donc b en sachant que Thomas jouera Y. Ici le résultat final est (2,4). Mais alors Thomas gagne plus de points que précédemment.

Conclusion, bien que sur toutes les combinaisons possible le résultat de Thomas est inférieur dans le deuxième jeu que dans le premier, Thomas gagne plus de points dans le deuxième jeu.

La formule de la résolvante et un peu de théorie des perturbations

Formule de la résolvante

Soit A et B deux matrices, la formule de la résolvante est la relation algébrique suivante


Elle est également valables si A et B sont des opérateurs linéaires sur un espace de dimension infini. Si l’énoncé et la preuve sont élémentaires, cette formule peut se révéler incroyablement utile, en particulier pour faire des développements perturbatifs. On a en effet en réinjectant la formule dans son dernier terme :

et par itération on obtient le développement perturbatif suivant

Je donne ici quelques exemples d’application plus ou moins direct.

Le calcul perturbatif d’une valeur propre

Soit A une matrice ayant une valeur propre simple l(0) et B une autre matrice. On souhaiterai avoir le développement en série entière en t de l(t) la valeur propre
de A+t B. Pour cela on peut utiliser la formule de Cauchy


où on intègre sur un petit cercle dans le plan complexe autour de l(0) et alors, on peut utiliser le développement perturbatif. Par exemple avec A la matrice
diagonal lambda, le terme d’ordre 2 est donné par

Exemple 2 : Une variante du principe Huygens Fresnel.

Une source lumineuse en un point x émet une onde de fréquence w et se propage dans un milieu selon un opérateur H. La lumière F(y) en tout point y est alors donnée par

Imaginons que le milieu est composé d’un espace fermé munie d’une ouverture. Dans notre opérateur, H=A si l’ouverture B est fermée et A-B si l’ouverture est ouverte. Lors que l’ouverture est fermée et que y se trouve à l’extérieur par rapport à x aucune lumière n’est reçue. Alors la formule de la résolvante lorsque l’ouverture est ouverte

peut s’interpréter ainsi : « les points z de l’ouverture se comportent comme des sources lumineuses secondaires d’intensité et de phase données par la résolvante lorsque l’ouverture est fermée. »

Exemple 3 : les diagrammes de Feynman.

C’est très certainement l’exemple le plus célèbre et probablement le plus impressionnant d’utilisation de la théorie de perturbation en physique. L’évolution d’un système quantique est décrit par un Hamiltonien H et l’équation de Schrödinger idf(t)=Hf(t)dt qui donne formellement la solution exp(-itH)f(t=0). Il est intéressant d’en étudier la transformé de Fourier (Laplace)

  1. La recette pour les diagrammes de Feynman est la suivante: Le Hamiltonien se décompose en un terme d’évolution libre des particules A et un terme d’interaction B qui en théorie quantique des champs s’exprime comme la création et annihilation
    de particules. On supposera l’interaction B est petit et on fera
    le développement perturbatif.
  2. Pour les calculs on travaillera dans la base de Fourier dans laquelle les termes d’évolutions libre A est diagonal. Les termes d’interaction sont ponctuels (local), dans la base de Fourier ils s’expriment sous forme d’intégrale.

Exemple 1: Une désintégration en deux particules

On considère une particule de masse M au repos qui se désintègre en deux particules m1 et m2 de masses plus petites. Le terme d’ordre 1 fait apparaît l’élément

avec a,b,c: les opérateurs de création/annihilation des particules M, m1, et m2 d’impulsion k. Il se dessine avec le diagramme de Feynman suivant

et permet de calculer le taux de désintégration en choisissant z0=M+it.

Exemple 2 : La diffusion Compton

La diffusion Compton, c’est le choc entre un électron et un photon. Initialement, on a  un photon d’impulsion k0 et un électron d’impulsion p0. Faire le développement à l’ordre 2 donne 4 termes mais seuls les termes

et

sont pertinents où a et c sont des opérateurs de création/annihilation
de l’électron et du photon. Ils correspondent aux diagrammes de Feynman
suivant

Une version simplifiée du théorème de Gauss Bonnet

Un très beau résultat en géométrie différentielle et que j’aime beaucoup est le théorème de Gauss Bonnet qui s’énonce ainsi: « Pour toute surface S fermée, l’intégrale
de sa courbure K est égale à 2 pi fois sa caractéristique d’Euler (nombre de faces – nombre d’arêtes – nombre de sommets)

Ici nous présentons une version un peu simplifiée du théorème de Gauss Bonnet dont l’énoncé et la preuve sont élémentaires. Ils peuvent être présentés à des élèves de collège ou de lycée et donc constitue à mes yeux un sujet parfait pour un exposé de vulgarisation mathématique.

Un petit résultat intermédiaire

Pour un polygone à N cotés la somme des angles vaut (N-2) fois pi. En effet faisons le tour de ce polygone dans le sens des aiguilles d’une montre. Après un tour complet la somme des tournants t(i) vaut toujours 2 pi ceci quelque soit le nombre de tournants réalisés. L’angle a(i) de chaque sommet est égale à pi moins t(i) et on a donc la somme des a(i) est égale à N*pi moins la somme des t(i) soit N*pi-2*pi. Cet exemple n’est pas anodin, car les tournants sont l’équivalent de la courbure en dimension 1.

Les coins alias les défauts d’angles

Considérons maintenant des polyèdre en 3 dimensions. Peut-on définir sur ses sommets une notion de coin? Quelque chose d’équivalent aux angles en 2 dimension et qui mesure de combien le sommet est pointu? Une réponse fut proposée par Descartes. Pour un sommet A, on considère les faces f du polyèdre adjacente à A et leur angle a(f) en ce sommet. On définit alors le coin c(A) (disons aussi le défaut
d’angle) comme 2*pi moins la somme de ces angles a(f).

Exemples

  • Pour un cube, Les trois angles valent pi/2 et donc c(A)=2*pi-3*pi/2=pi/2.
  • Pour un tétraèdre régulier : les trois angles valent pi/3, et donc c(A)=2*pi-3*pi/3=pi.

 

Remarquez qu’il peut y avoir des coins négatifs. Cependant cela ne dépend pas si le coin est s’enfonce ou non dans la figure. Par exemple le coin ci dessous est bien positif. Pour voir si un coin est positif ou négatif on déplie le patron de la figure. Si sur le patron les faces autour du sommet ne se recouvrent pas alors la somme des angles est inférieur à 2 pi et au contraire si elles se recouvrent alors elle est supérieur à 2*pi.

 

Les coins et la caractéristique d’Euler

Quand est il de la somme des coins du polyèdre? On peut reprendre les exemples précédents:

  • Pour le cube, on a 8 sommets, chacun d’un coin égale à pi/2, la somme des coins vaut alors 8*pi/2=4*pi
  • Pour le tétraèdre, on a 4 sommets dont chacun a un coin égale à
    pi et donc la somme vaut 4*pi.

Remarquez que l’on retrouve bien à chaque fois la surface de la sphère. On peut montrer ce théorème de Gauss Bonnet simplifié :

Soit un polyèdre P, alors la somme de ses coins est égale à 2*pi fois sa caractéristique d’euler.

PREUVE:

Le deuxième terme est la somme de tous les angles du polyèdre, c’est donc aussi la somme sur toutes les faces f de la somme des angles de cette face et alors:

avec N(f) le nombre de cotés de la face f. Dans cette somme chaque arête du polyèdre est comptée 2 fois, et elle est donc égale à 2*A  (A le nombre d’arête du polyèdre). Et on peut conclure : la somme des coins vaut bien 2*pi*(F-A+S).

Des surfaces avec trous et sans trous

La caractéristique d’Euler est un des invariants topologique les plus connus, elle permet notamment de classifier les surfaces de dimension 2. Remarquez que pour les polyèdres, la caractéristique d’Euler est bien invariante si on les complexifie en découpant les faces, en ajoutant des sommets ou en déformant la figure. On peut énoncer le résultat suivant : la somme des coins d’un solide (sans trou) vaut toujours 4*pi. Dans le cas général la caractéristique d’Euler vaut 2 moins 2 fois le nombre de « trous ».

Par exemple sur les figures suivantes la somme des coins est égale à 0 et -4*pi:

 

Vers la version continue? Considérons une surface lisse. On peut tout à fait l’approximer par un polyèdre ayant de plus en plus de faces. La somme des coins se comporte alors comme une somme de Riemann qui converge vers l’intégrale de la courbure.

 …  … …  

(somme des coins = intégrale de la courbure = 4*pi)

Et le théorème remarquable de Gauss?}

Il est difficile de parler de Gauss et de courbure sans mentionner le « Theorema egregium » (théorème remarquable) qui affirme que la courbure est invariante par isométrie locale. Énonçons en une variante (très) simplifiée pour les coins :

Soit un polyèdre P qui ne possède que des faces triangulaires, Tout transformation en un polyèdre P’ qui conserve les longueurs des arêtes conserve également la valeur des coins.

La preuve est élémentaire: les longueurs sont conservées, donc les
angles des triangles sont conservés donc par définition les coins
sont conservés.
Par exemple les deux figures précédentes avec le coins qui s’enfonce dans le cube ont les mêmes coins.

L’urne de Polya

Un petit modèle probabiliste

L’urne de Polya est un modèle jouet probabiliste très populaire. Prenez une urne dans laquelle se trouve N boules: r(0) rouges et  b(0) bleus soit r(0)+b(0)=N. On en tire une aléatoirement (uniformément) et on note sa couleur. On replace alors la boule dans l’urne et on y ajoute en plus une autre boule de cette même couleur. Par exemple pour le premier tirage on a la probabilité r(0)/(r(0)+b(0)) d’obtenir une boule rouge. Si on tire effectivement une boule rouge, au deuxième tirage il y aura alors dans l’urne N+1 boules dont r(1)=r(0)+1 rouges et b(1)=b(0) bleus. Puis on recommence ainsi autant de fois qu’on le souhaite (après le n-ième tirage, on a donc r(n) rouges et b(n) bleus avec r(n)+b(n)=N+n).

Qu’est ce que ça donne la limite n tend vers l’infini? Y a t-il (avec grande probabilité) une couleur très majoritaire? C’est à dire b(n)/(r(n)+b(n) ou r(n)/r(n)+b(n)converge vers 0? Ou bien les deux couleurs s’équilibrent-elles et on a b(n)/r(n)+b(n) converge 1/2?
La réponse assez surprenante est ni l’une ni l’autre. On a que presque surement il existe X tel que b(n)/r(n)+b(n) converge vers X mais X est aléatoire sur le segment [0,1]. On peut par ailleurs montrer que X suit une loi bêta B(r(0),b(0)). En particulier si il n’y a au départ une seule boule rouge et une seule boule bleu, X sera équidistribué sur [0,1].

preuve:

Plaçons nous sur le segment [0,1] et tirons N-1 points aléatoirement indépendamment et identiquement distribués que l’on ordonne 0 < x(1) < x(2) < … x(N-1)<1. Fixons le point x(r(0)). On appellera [0,x(r(0))[ la zone rouge et ]x(r(0)),1] la zone bleu. On dira ensuite que  0,x(1),…,x(r(0)-1) sont rouges et que x(r(0)+1),…,1 sont bleus. Continuons
le tirage de points aléatoire iid uniforme sur [0,1] en fonction de zone où il apparait, il est soit rouge soit bleu. Connaissant x(r(0)) on a une Bernoulli : le point est rouge avec probabilité x(r(0)) et le point est bleu avec proba 1-x(r(0))). La loi des grands nombre
nous dit alors que le nombre moyen de point rouge converge vers x(r(0)). Et on connait également la loi de x(r(0)): c’est une loi bêta B(r(0),b(0)) (Remarquez puisqu’il y a au départ r(0)-1 points sur [0,x(r(0))[ et b(0)-1 points sur ]x(r(0)),1] la fonction de densité
est alors proportionnel à  x(r(0)) puissance r(0)-1 fois (1-x(r(0)) puissance b(0)-1).

Oublions maintenant que l’on connaisse x(r(0)) mais que l’on sait combien de points sont tombés dans la zone rouge (resp bleu). Par définition, après le n-ième tirage x(r(0)) est alors le r(n) plus grand point parmi les N-1+n tirés. Tirons alors un nouveau
point. Puisque que tous les tirages sont iid, tous les ordres possibles des différents points sont équiprobable. En particulier ce nouveau point aura r(n)/(b(n)+r(n)) d’avoir un rang plus petit ou égale que r(n) et b(n)/b(n)+r(n)) d’avoir un rang plus grand que r(n). Et on retrouve alors exactement l’urne de Polya! Elle est donc bien équivalente au tirage de Bernoulli iid que l’on vient de décrire.

Le théorème de De Finetti

L’urne de Polya est probablement l’exemple le plus célèbre d’application du théorème de De Finetti. Pouvoir se ramener à des variable iid est extrêmement intéressant mathématiquement parlant. On souhaiterait savoir quand cela est-il possible. Plus précisément à partir d’une suite de tirages non indépendent, est on capable de décomposer la loi de ces tirages en une variable aléatoire d’environnement (notre
x(r(0))) et que conditionnellement à cette variable les tirages soient indépendants (selon une loi qui dépend de l’environnement x(r(0))). On peut facilement voir que si cela était vrai, alors les lois des tirages aléatoires ne dépendraient pas de l’ordre de la réalisation
du tirage en question. Ceci donne donc une condition nécessaire. Le théorème de De Finetti affirme que cette condition est également suffisante si l’on considère un tirage infini (la proba ne dépend pas d’une permutation finie.). Il s’énonce ainsi pour des Bernoulli:

« Soit X(1),X(2),… une suite infini de variable aléatoire de Bernoulli dont la loi de l’ensemble est invariante par permutation finie. Alors il existe une variable aléatoire Y tel que (X(1)+…+X(n)/n converge vers Y presque surement. De plus conditionnellement à cette limite les variables X(i) se comportent comme des variables de Bernoulli indépendantes et identiquement distribuées avec P(X=1|Y=y)=y et P(X=0|Y=y)=1-y. »

Un sujet de recherche actuel: les marches aléatoires renforcées.

Les marches aléatoires sont omniprésentes chez les probabilistes. Un modèle qui retient l’attention de plusieurs groupes de chercheurs actuellement sont les marches aléatoires renforcées (MAR). C’est à dire des marches aléatoires qui ont plus de chance de retourner à un endroit où elles sont déjà passées avant. Plus précisement, on pose quelque chose comme ça : « Si x est voisin de y (x-y), la probabilité que la marche saute de X(n)=x en X(n+1)=y est de la forme (a+n(y))/S où n(y) est le nombre de fois que la marche a visité y, et S est la somme des (a+n(y’)) sur les voisin de x.

Il se trouve que l’on peut appliquer une variante du théorème de De Finetti dans ce cas ci. Pour chaque sommet, on compte le nombre de fois que la marche a visité chacun de ses voisins et cela se comporte alors comme une sorte d’urne de Polya. On pourra alors construire un environnement aléatoire sur lequel est définit un processus de
Markov qui a la même loi que la MAR. Mais quel est cet environnement aléatoire? La marche reste-elle coincée infinitésiment ou part-elle à l’infini? Et plein d’autres questions sur lesquelles travailler…