[ENS]
[Élèves ENS]
[David Madore]
[Mathématiques]
[Informatique]
[Programmes]
[Linux]
[Littérature]
J'ai rassemblé ici quelques résultats curieux et contre-intuitifs en théorie des probabilités afin de mettre en lumière certaines bêtises qu'on a naturellement tendance à commettre dans ce domaine.
Les autorités chinoises ont décrété qu'une famille ne peut avoir que deux enfants, et encore, seulement si le premier est une fille. On demande si cela peut modifier la proportion de garçons et de filles. (On fera l'hypothèse habituelle - fausse dans la pratique - que les différentes naissances dans une même famille sont indépendantes les unes des autres, et que la probabilité d'avoir un garçon est la même à chaque naissance.)
Oui, cela modifie la proportion de garçons et de filles. De cette façon, il y aura plus de filles que de garçons. En effet, le dernier enfant né dans une famille a une chance sur deux d'être un garçon et une chance sur deux d'être une fille, tandis que l'enfant précédent s'il y en a un est forcément une fille.
Oui, il y aura plus de garçons. En effet, une famille qui veut un garçon a droit à deux ``essais'' pour cela, et donc a une chance sur quatre de ne pas réussir à en avoir un. Alors qu'une famille qui veut une fille n'a pas ``droit à l'erreur''.
Non, la proportion de garçons et de filles n'est pas modifiée.
Chaque naissance produit un garçon avec une probabilité p1 et une fille avec une probabilité p2=1-p1. Ces probabilités, par hypothèses, sont toujours les mêmes (pour simplifier, 1/2 et 1/2, mais ce n'est pas une hypothèse nécessaire) quels que soient les événements antérieurs. Il y aura donc toujours une proportion p1 de garçons et une proportion p2 de filles. Aucune décision sur une naissance fondée uniquement sur les naissances antérieures (par opposition, par exemple, à une décision d'avortement si l'enfant est une fille) ne peut influencer cette proportion.
Une famille qui choisit d'avoir deux enfants si elle le peut aura une probabilité p1 d'avoir exactement un garçon, p2*p1 d'avoir une fille puis un garçon, et p22 d'avoir deux filles. L'espérance du nombre de garçons est donc p1+p2*p1=p1(1+p2) et celle du nombre de filles est p2*p1+2*p22=p2(1+p2), ce qui est bien en proportion p1 pour p2.
Dans la première solution erronnée donnée ci-dessus, c'est la phrase « le dernier enfant né dans une famille a une chance sur deux d'être un garçon et une chance sur deux d'être une fille » qui est incorrecte. Dans la seconde solution erronnée, on oublie de noter qu'une famille qui cherche à avoir un garçon pourra se retrouver avec une ou des filles…
En fait, un couple dont le premier enfant est une fille a plus de chances d'avoir une autre fille en seconde naissance. Si on tient compte de ce phénomène, la proportion garçons/filles sera légèrement modifiée en faveur des filles.
Je rends visite à la famille Martin. Je sais que Monsieur et Madame Martin ont deux enfants. Je frappe à la porte, et une fille me répond. Quelle est la probabilité que l'autre enfant soit également une fille ?
Ben, une chance sur deux, pardi !
Non. Parce que : il y a quatre possibilités équiprobables pour la composition de la famille (fille/fille, fille/garçon, garçon/fille ou garçon/garçon) et le fait qu'une fille réponde à la porte exclut la dernière possibilité, ce qui fait qu'on a deux chances sur trois que l'autre enfant soit un garçon et une chance sur trois que ce soit une fille.
Le problème est posé de façon trop vague pour qu'on puisse trancher entre ces deux réponses. Si on dit « l'enfant le plus âgé répond à la porte et c'est une fille », ou bien « l'un ou l'autre des enfants (avec même probabilité pour chacun) ouvre la porte et c'est une fille », alors la première solution proposée est correcte. Si en revanche on dit « les garçons ne répondent jamais à la porte, et on m'a répondu à la porte », ou bien « les garçons ne répondent à la porte que s'il n'y a pas de fille dans la famille, et c'est une fille qui répond », alors c'est la seconde solution qui l'est (voir le problème des portes au trésor). De façon générale, je penche plutôt pour la première solution (la seconde solution est sortie de l'esprit des gens qui ont trop médité sur le problème des portes au trésor), mais si on ne donne pas plus de renseignements, on ne peut pas répondre.
Parmi les familles ayant deux enfants, et dont un des deux enfants est une fille, les deux tiers ont un garçon (pour l'autre enfant). En revanche, parmi les familles ayant deux enfants, et dont l'aîné est une fille, la moitié ont un garçon (pour cadet). C'est un fait, c'est indiscutable (et il n'y a pas de probabilités là-dessous).
Un candidat à un jeu télévisé est placé devant trois portes fermées. Derrière l'une d'elles il y a un trésor. Le candidat commence par se placer devant une des trois portes, puis le présentateur (qui connaît l'emplacement du trésor) ouvre (obligatoirement) une autre porte derrière laquelle il n'y a pas de trésor (ce qui est toujours possible puisqu'il n'y a qu'un trésor et qu'il y a deux autres portes). Enfin, le candidat a le choix entre ouvrir la troisième porte (celle que le présentateur a laissée fermée) ou bien celle devant laquelle il se trouve. Qu'a-t-il intérêt à faire ?
Les deux portes encore fermées ont chacune une chance sur deux de receler le trésor, donc il n'a pas particulièrement intérêt à changer.
Le trésor a une chance sur trois de se cacher derrière la porte devant laquelle se trouve le candidat, et deux chances sur trois de se trouver derrière l'autre. Le candidat a donc intérêt à changer.
Pour commencer, imaginez un nombre extrêmement élevé de portes, le présentateur les ouvrant toutes sauf une. On peut même imaginer le jeu suivant : un nombre réel entre 0 et 1 est tiré au hasard, le candidat propose un nombre réel, et le présentateur annonce un autre nombre réel tel que le nombre tiré au hasard soit égal ou bien au nombre choisi par le candidat ou bien au nombre annoncé par le présentateur ; le candidat doit alors choisir un des deux. Qui serait assez stupide pour rester sur son choix initial ?
En fait, l'analyse est très simple : ou bien le candidat a choisi une mauvaise porte au départ, ce qui a deux chances sur trois d'être le cas, et alors la porte laissée fermée par le présentateur est nécessairement la porte au trésor. Ou bien le candidat a choisi la bonne porte au départ, ce qui a une chance sur trois de se produire. Finalement, il y a deux chances sur trois que la porte laissée fermée par le présentateur soit la bonne, et seulement une chance sur trois que la porte choisie par le candidat soit la bonne…
Je dois dire que j'ai du mal à comprendre ce que certains trouvent de difficile à ce problème.
Certains attaquent ce problème en mettant en cause le rôle du présentateur. Il faut cependant noter que le choix de la porte sans trésor fait par le présentateur n'a pas d'importance. Mais :
En revanche, on peut décider que le présentateur ne connaît pas l'emplacement du trésor. Le jeu est alors le suivant : le candidat se place devant une porte, et le présentateur ouvre une des deux autres portes au hasard. Il ne connaît pas l'emplacement du trésor. Il se trouve simplement (par hasard) qu'il ouvre une porte sans trésor.
Il faut bien comprendre que ce déroulement des événements change complètement le raisonnement. Cette fois, s'il est vrai que la probabilité initiale que le candidat soit devant la bonne porte était une chance sur trois, cette probabilité change et passe à une chance sur deux lorsque le présentateur ouvre une porte sans trésor, puisque la possibilité dans laquelle le présentateur ouvrait la porte du trésor a été éliminée et qu'il ne reste donc que deux portes en jeu. (Il faut bien comprendre qu'une probabilité peut changer lorsqu'on réalise un conditionnement, et c'est le cas ici, tandis que dans la présentation antérieure du problème il n'y avait pas de conditionnement puisque le présentateur était toujours capable d'ouvrir une porte sans trésor en utilisant sa connaissance de l'emplacement du trésor.)
D'ailleurs, un principe de symétrie permet de conclure, puisque les deux portes non ouvertes sont identiques. (Le fait que le présentateur n'avait pas le droit d'ouvrir la porte du candidat est sans importance, puisqu'il ne connait pas l'emplacement du trésor donc toutes les portes sont identiques pour lui.)
Encore une fois, si on imagine une nombre très élevé de portes, et qu'on suppose que le présentateur les ouvre toutes sauf deux (celles devant laquelle se trouvait le candidat et une autre), et que par un hasard surprenant aucune d'elles ne contient le trésor, le problème est alors beaucoup plus intuitif.
C'est peut-être cette variation du jeu (plus complexe finalement) qui rend le problème de départ confus dans l'esprit de nombre de personnes.
Trois prisonniers sont condamnés à mort. On apprend cependant que l'un d'eux est grâcié, mais on ne sait pas lequel. L'un des prisonniers réfléchit de la sorte : « sur mes deux compagnons, l'un sera nécessairement exécuté, et on peut donc l'oublier ; mais alors nous ne sommes que deux à rester en jeu pour la grâce (moi et un autre), donc j'ai finalement une chance sur deux d'être grâcié ».
C'est idiot. Que dire de plus ?
Ce jeu se joue à deux joueurs. Le premier joueur choisit deux nombres réels distincts comme il lui plaît (insistons bien sur ce point : les nombres ne sont pas nécessairement tirés au hasard). Puis il tire à pile ou face : si la pièce tombe sur pile, il communique le plus petit nombre au second joueur, sinon, il lui communique le plus grand. C'est la seule information dont dispose le second joueur. Son but est de déterminer si la pièce était tombée sur pile ou face, autrement dit, si l'autre nombre était plus grand ou plus petit. On demande s'il existe une façon pour le second joueur de faire son choix qui lui assure d'avoir raison avec une probabilité strictement supérieure à 1/2.
C'est absolument impossible ! Tout ce qu'on communique au second joueur, c'est un nombre réel, et on lui demande de déterminer si un autre nombre réel (absolument sans rapport, et qui ne lui est pas donné) est plus grand ou plus petit. C'est absurde !
Il faut noter qu'on autorise le second joueur à utiliser un élément de hasard dans sa procédure de décision. On formalisera cet élément de hasard par une variable aléatoire Y.
La formalisation est alors la suivante : on considère une variable aléatoire i égale à 0 avec probabilité 1/2 et à 1 avec probabilité 1/2, et on demande s'il existe une variable aléatoire Y, indépendante de i, à valeur dans un espace A non spécifié et une fonction f (mesurable), la fonction de décision, de R*A vers {0,1}, telle que si x1<x2 sont des nombres réels quelconques et x=x1+i(x2-x1) alors l'événement f(x,Y)=i a une probabilité strictement supérieure à 1/2.
On insiste bien sur le fait qu'on ne demande aucunement que cette probabilité soit uniformément minorée (indépendamment de x1 et x2) par une constante strictement supérieure à 1/2 : on demande seulement qu'elle soit strictement supérieure à 1/2 quelles que soient les valeurs de x1 et x2.
Et pourtant il existe une méthode ! Elle est même très simple.
Appelons x1 et x2 les deux nombres réels choisis par le premier joueur, avec x1<x2, et x celui de ces deux réels qui est communiqué au second joueur (ainsi, x=x1 avec probabilité 1/2, et x=x2 avec probabilité 1/2). Le second joueur emploie alors la méthode suivante : il tire au hasard un nombre réel x0 suivant une loi, disons, Gaussienne (la seule condition étant que x0 a une probabilité strictement positive de se trouver dans un intervalle non trivial donné quelconque). Si x<x0, le second joueur répond « la pièce était tombée sur pile » (c'est-à-dire que x=x1, et donc x2>x), tandis que si x>=x0, le second joueur répond « la pièce était tombée sur face » (c'est-à-dire que x=x2, et donc x1<x).
Comment cela fonctionne-t-il ? Appelons p la probabilité pour que le nombre réel x0 tiré au hasard par le second joueur soit compris entre x1 et x2 (précisément, la probabilité qu'on ait x1<x0<=x2). Si effectivement, x0 est compris entre x1 et x2, alors le second joueur répond juste, qu'on lui propose x1 ou x2, donc à tous les coups. Si en revanche, x0 est inférieur ou égal à x1, alors le second joueur répond que la pièce est tombée sur face, et il a une chance sur deux d'avoir raison. De même, si x0 est supérieur à x2, alors le second joueur a une chance sur deux d'avoir raison avec cette méthode. Finalement, la probabilité qu'il ait raison est p+(1-p)/2=(1+p)/2, et celle-ci est strictement supérieure à 1/2 puisque p>0.
Ainsi, quels que soient les nombres réels x1 et x2, la probabilité de répondre juste est strictement supérieure à 1/2. Cependant, on ne peut naturellement pas la minorer uniformément par une constante strictement supérieure à 1/2 (en choisissant les nombres x1 et x2 arbitrairement proches l'un de l'autre, le premier joueur peut rendre la probabilité que le second joueur ait raison arbitrairement petite). Naturellement, les nombres x1 et x2 peuvent être tirés au hasard par le premier joueur si celui-ci le désire - cela ne change rien au problème (l'espérance d'une variable presque surement strictement supérieure à 1/2 est strictement supérieure à 1/2).
Cette fois, le problème est un peu différent : un candidat à un jeu télévisé se voit proposé deux enveloppes, chacune contenant une certaine somme d'argent (et les deux sommes étant différentes). Il choisit une de ces deux enveloppes, en examine le contenu, puis décide s'il préfère garder cette enveloppe ou bien choisir l'autre. Mais il ne pourra plus changer d'avis ensuite.
La méthode proposée pour le jeu précédent fonctionne ici, et permet d'avoir une espérance de gain strictement supérieure à la demi-somme des quantités d'argent dans l'une et l'autre enveloppe. On changera donc d'enveloppe lorsque la quantité trouvée dans la première est inférieure à un certain nombre réel x0 préalablement tiré au hasard (suivant une loi quelconque donnant une probabilité non nulle à chaque intervalle).
Si les quantités x1 et x2 d'argent contenues dans les deux enveloppes sont tirées au hasard suivant une loi de probabilité connue du candidat, il a intérêt non pas à tirer x0 au hasard, mais à le choisir égal à l'espérance de la loi.
Le jeu est le même avec une condition supplémentaire : la quantité d'argent contenue dans une enveloppe doit être le double (ou la moitié !) de celle contenue dans l'autre enveloppe. Autrement dit, les enveloppes doivent contenenir x1=t et x2=2t pour une certaine somme t>0. Le candidat choisit l'enveloppe contenant x (égal à x1=t avec probabilité 1/2, et à x2=2t avec probabilité 1/2), et on appelle x' la somme contenue dans l'autre enveloppe.
Quelle que soit la somme x découverte par le candidat, la somme x' contenue dans l'autre enveloppe a une chance sur deux d'être 2x et une chance sur deux d'être x/2. Son espérance est donc 5x/4>x, et le candidat a donc toujours intérêt à changer d'enveloppe.
Ce raisonnement montre que, x étant une variable aléatoire égale à t avec probabilité 1/2 et 2t avec probabilité 1/2, et x' la variable complémentaire, l'espérance de la variable aléatoire x'/x est égale à 5/4. Il en va de même de l'espérance de la variable aléatoire x/x'. Cela n'a rien de contradictoire (même si c'est un peu surprenant). Cela ne signifie pas pour autant que le candidat ait intérêt (avant même d'avoir ouvert son enveloppe) à changer d'enveloppe, puisque les espérances de x et x' sont égales (toutes deux à 3t/2). Il est faux que l'espérance de x' soit égale à 5/4 fois celle de x.
Maintenant, supposons que x soit connu (ce n'est plus une variable aléatoire). Quelle est l'espérance de x' ? Cela n'a aucun sens : il n'y a plus de variable aléatoire dans le problème. x' est un nombre réel égal soit à 2x soit à x/2, mais il est absurde de parler de probabilité pour l'un ou l'autre cas (précisément, la probabilité que x'=2x est 1 si t=x, et 0 si t=x/2).
On peut cependant le faire si on suppose que t a été en fait tiré au hasard suivant une certaine loi fixée. Par exemple, pour une loi uniforme entre 0 et T, l'espérance de x' est 3x/2 si x est compris entre 0 et T, et x/2 si x est compris entre T et 2T (et le candidat a donc intérêt à changer d'enveloppe lorsque x est compris entre 0 et T, ce qui lui assure ainsi une espérance de gain de 15T/16). (Voir aussi plus bas pour une autre manière de s'assurer une espérance de gain minimale.)
Cependant, en l'absence de tout renseignement sur t, le candidat peut tout de même s'assurer une espérance de gain meilleure que 3t/2, en choisissant l'autre enveloppe lorsque l'enveloppe qu'il ouvre renferme une somme inférieure à x0, où x0 est un réel qu'il a préalablement tiré au hasard.
On suppose encore une fois qu'il y a une certaine somme t dans une enveloppe et le double 2t dans l'autre. Mais on suppose de plus que t doit au moins être égal à t0, où t0 est un certain réel strictement positif.
Nous avons déjà noté que le candidat pouvait s'assurer une espérance de gain meilleure que 3t/2. Cependant on ne pouvait pas la minorer uniformément par (3/2+e)t pour aucune quantité strictement positive e, ni même par 3t/2+e. La nouveauté est que maintenant c'est possible. Pour être précis, le candidat peut s'assurer une espérance de gain de 3t/2+t0/4.
Comment cela ? Il suffit que le candidat change d'enveloppe avec une probabilité t0/x, où x est la somme trouvée dans l'enveloppe ouverte en premier. En effet, si x=t (il prend l'enveloppe ayant le moins d'argent, et x'=2t) alors il change avec probabilité t0/t et son espérance est (1-t0/t)t+(t0/t)(2t)=t+t0. Si x=2t (il prend l'enveloppe ayant le plus d'argent, et x'=t) alors il change avec probabilité t0/2t et son espérance est (1-t0/2t)(2t)+(t0/2t)t=2t-t0/2. Ainsi, globalement son espérance est 3t/2+t0/4, soit t0/4 de mieux, uniformément que ce qu'on obtient par la méthode naïve.
(Pour se rapprocher de la solution donnée plus haut, on peut dire qu'on tire le nombre réel x0 de décision avec une densité de probabilité de (t0/x2)dx.)
On suppose maintenant, par rapport à la variante déjà étudiée, que t est un entier (naturel non nul).
Alors on écrit x=r2s où r est un entier impair (le plus grand diviseur impair de x, qui est aussi le plus grand diviseur impair de t) et s est l'exposant de la plus grande puissance de 2 divisant x. On changera alors d'enveloppe avec probabilité 2-s. Un raisonnement semblable à celui fait précédemment montre que cela apporte une espérance de gain de 3t+2+r/4, soit r/4 de mieux que la méthode naïve.
Un singe tape au hasard sur une machine à écrire, à raison d'une lettre par seconde. Toutes les 26 lettres ont même probabilité, et le choix de chacune est indépendant des précédentes lettres tapées. On appelle t1 le temps moyen qu'il faut attendre pour que le singe tape le mot « abracadabra », et t2 le temps moyen pour le mot « abracadabrx ». A-t-on t1<t2, t1=t2 ou bien t1>t2 ?
On a t1=t2 puisque les lettres sont indépendantes : à un instant donné, la probabilité que les prochaines lettres tapées par le singe soient « abracadabra » et la probabilité qu'elles soient « abracadabrx » sont les mêmes.
En fait, t1>t2. Pour être précis, t1=3670344487444778 (en secondes), alors que t2=3670344486987776.
On considère l'ensemble des suites (indicées par les naturels) à valeurs dans {a...z}, qu'on munit de la probabilité produit de la probabilité uniforme sur {a...z} (qui donne à chaque lettre la probabilité 1/26). Sur cet ensemble de suites on considère la variable aléatoire T1 qui à une suite associe le temps d'apparition de la première sous-chaîne « abracadabra » (i.e. le nombre de lettres qui ont été tapées quand cette chaîne apparaît pour la première fois, avec bien entendu la valeur plus l'infini si la chaîne n'apparaît pas), et T2 le temps correspondant pour « abracadabrx ». On appelle t1 l'espérance de T1 et t2 l'espérance de T2.
Le fait est que t1>t2, autrement dit que la variable T1-T2 a une espérance strictement positive. En revanche, cette variable a une médiane nulle, ce qui est probablement la source de la confusion (il est aussi fréquent que « abracadabra » apparaisse avant qu'après « abracadabrx »).
Supposons qu'il n'y ait que deux lettres, a et x. On considère alors les deux mots « aa » (t1 l'espérance du temps qu'il faut attendre pour voir « aa » apparaître) et « ax » (t2 l'espérance correspondante). Il s'agit de montrer que t1>t2. Pour être précis, que t1=6 tandis que t2=4.
Commençons par une expérience numérique. Le programme utilisé est le suivant :
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NBATTEMPTS 100000
typedef enum { a,x } letter;
letter
randomletter (void)
{
if ( rand () % 2 ) return x;
else return a;
}
int
waitfor_aa (void)
{
letter last, before_last;
int t;
last = randomletter(); t = 1;
do
{
before_last = last;
last = randomletter ();
t++;
}
while ( before_last != a || last != a );
return t;
}
int
waitfor_ax (void)
{
letter last, before_last;
int t;
last = randomletter (); t = 1;
do
{
before_last = last;
last = randomletter ();
t++;
}
while ( before_last != a || last !=x );
return t;
}
int
main (void)
{
int i,t;
srandom (time (NULL));
t = 0;
for ( i=0 ; i<NBATTEMPTS ; i++ )
t += waitfor_aa ();
printf ("Waiting for aa: %7d/%7d\n", t, NBATTEMPTS);
t = 0;
for ( i=0 ; i<NBATTEMPTS ; i++ )
t += waitfor_ax ();
printf ("Waiting for ax: %7d/%7d\n", t, NBATTEMPTS);
exit (0);
}
Et en lançant ce programme on voit quelque chose comme :
Waiting for aa: 599872/ 100000 Waiting for ax: 399556/ 100000ce qui confirme bien les chiffres annoncés.
Calculons la probabilité que la variable aléatoire T2 (le temps d'apparition du premier « ax », dont l'espérance est t2) soit au moins égale à n. L'événement « T2>n » correspond à la frappe de n touches formant une chaîne de longueur n, dans laquelle la sous-chaîne « ax » n'apparaît pas. Une telle chaîne est formée de k fois la lettre « x », suivies de n-k fois la lettre « a », et il y a donc n+1 telles chaînes (n+1 valeurs possibles pour k). Ceci montre que l'événement « T2>n » a une probabilité (n+1)/2n, donc que l'événement « T2=n » a la probabilité (n-1)/2n (du moins si n>1). L'espérance t2 de T2 est alors la somme des n(n-1)/2n, qui vaut 4.
Passons à T1 : on cherche le nombre de chaînes de longueur n ne contenant pas la sous-chaîne « aa ». Or il est bien connu (et cela se vérifie facilement par récurrence) que ce nombre est le (n-1)-ième nombre de Fibonacci, Fn-1 (où F0=F1=1). La probabilité de « T1>n » est donc Fn-1/2n, et la probabilité de « T1=n » est alors (Fn-2-Fn-3)/2n. On calcule alors l'espérance en utilisant l'expression des nombres de Fibonacci en fonction des nombres d'or, et on trouve t2=6.
Ainsi, l'espérance de la variable T1-T2 est 2. Il est cependant intéressant de noter que la médiane de cette variable est 0. Autrement dit, il y a autant de chances que le singe tape « aa » avant « ax » que « ax » avant « aa ». En effet, dès qu'il tape le premier « a », il est sur le point de taper l'un de ces deux mots, et il y a alors une chance sur deux que ce soit l'un et une chance sur deux que ce soit l'autre.
Appelons t2a et t2x l'espérance de T2 (le temps d'apparition de la première chaîne « ax ») sachant que la première lettre tapée par le singe est « a » (resp. « x »). On a t2=(t2a+t2x)/2, et de plus il est clair que t2x=1+t2. Par ailleurs, en considérant la seconde lettre, qui peut être a ou x, on voit que t2a=((1+t2a)+2)/2. Ces équations se résolvent en t2a=3, t2=4, t2x=5. (Bien sûr, ce calcul suppose que T2 est intégrable, mais c'est assez clair.)
Le calcul semblable pour t1 donne les équations t1=(t1a+t1x)/2, t1x=1+t1 et t1a=(2+(1+t1x))/2. On trouve alors t1x=7, t1=6, t1a=5.
Si le singe tape pendant un temps tendant vers l'infini, et qu'on considère la proportion de « aa » (c'est-à-dire le nombre de lettres « a » précédées d'une autre lettre « a ») d'une part, et la proportion de « ax » d'autre part (c'est-à-dire le nombre de lettres « x » précédées d'une lettre « a »), ces proportions tendent (presque sûrement) vers 1/4 toutes deux. Ici, une chaîne comme « aaaxaaxxaaa » compte pour 5 occurrences de la chaîne « aa » (et 2 de la chaîne « ax »). En effet, le comptage des « aa » revient à attendre le premier « aa » (on sait qu'on attend en moyenne 6 secondes pour celui-ci), puis le second, sachant qu'un premier « a » a déjà été tapé (et pour cela on attend en moyenne t1a-1=4 secondes), puis le troisième, sachant qu'un premier « a » a déjà été tapé, et ainsi de suite. Le comptage des « ax » revient de même à attendre t2=4 secondes pour le premier, puis t2x-1=4 secondes pour chaque suivant.
En revanche, si on décide que « aaaxaaxxaaa » ne comprend que 3 fois la chaîne « aa » (c'est-à-dire qu'on ne permet pas de superposition), alors la proportion n'est plus 1/4 mais 1/6, puisque le comptage revient à attendre chaque « aa » en partant de rien du tout, et pour cela il faut en moyenne 6 secondes. C'est finalement l'expérience qui a été tentée plus haut avec le programme en C.
Quatre arguments différents (un expérimental, deux théoriques et un heuristique) ont été donnés pour montrer que dans le problème simplifié on a t1<t2. Il n'est pas difficile de concevoir que ceci reste valable dans le problème initial. Finalement, la raison peut se résumer ainsi : si on attend « abracadabra » et que le singe tape « abracadabrx », tout est fini et on repart essentiellement à zéro ; en revanche, si on attend « abracadabrx » et qu'il tape « abracadabra », alors tout n'est pas si mal puisqu'on a déjà le « abra » nécessaire pour taper « abracadabrx ».
Pour le calcul explicite des temps moyens, la « recette » est la suivante : pour chaque chaîne de caractères commune au début et à la fin du mot (y compris le mot entier mais sans compter la chaîne vide), ici « abracadabra », « abra » et « a », on ajoute le nombre de lettres à la puissance de la longueur de la chaîne, soit ici t1=2611+265+26, tandis que t2=2611.
Il s'agit d'expliquer ici un « paradoxe » dans le processus de Poisson. L'ennui c'est que ce paradoxe est un peu compliqué (plus compliqué en tout cas que ceux que nous avons exposés ci-dessus). Il va donc falloir passer par quelques préliminaires. Si on ne souhaite pas entrer dans les détails mathématiques, on pourra sauter directement à la formulation du paradoxe en terme de trains.
Les désintégrations radioactives sont l'exemple typique du processus de Poisson. Tout d'abord, il faut partir de la loi exponentielle d'espérance T. Celle-ci a une densité de probabilité de exp(-t/T)dt/T, ce qui donne une probabilité de exp(-t1/T)-exp(-t2/T) d'avoir une valeur entre t1 et t2, et entre autres une probabilité de exp(-t/T) d'avoir une valeur supérieure à t. T est l'espérance de la loi. Dans un phénomène radioactif, la variable sera le temps avant la désintégration d'une particule. (Les physiciens ont l'habitude d'utiliser la demi-vie plutôt que l'espérance T. La demie-vie est la valeur de t pour laquelle exp(-t/T) vaut 1/2, soit t=ln(2)*T. Cela ne change pas grand-chose. D'ailleurs, c'est la médiane de la loi.)
Le phénomène remarquable, et passablement contre-intuitif, avec la loi exponentielle, est que si on conditionne une variable t de loi exponentielle (d'espérance T) par la condition t>t0, alors la variable t résultante a pour loi la même loi exponentielle simplement translatée de t0. En langage plus clair, cela signifie que si au bout de t0 la particule ne s'est toujours pas désintégrée, son espérance de vie n'a cependant pas décrû, et la loi de probabilité de sa désintégration (mesurée à partir de la nouvelle origine t0) est toujours la même.
Considérons maintenant deux variables aléatoires u et u', indépendantes, toutes deux de loi exponentielle d'espérance T. Leur somme, v=u+u', suit une loi non exponentielle mais de loi (v/T2)exp(-v/T)dv (d'espérance 2T bien entendu). (Il s'agit là de l'attente du deuxième événement dans un processus de Poisson.) Chose amusante, si on conditionne par v=v0, alors les lois de u et u' deviennent uniformes sur l'intervalle [0;v0]. Autrement dit, si on sait que la deuxième désintégration va se produire à l'instant v0, alors la première désintégration suit une loi uniforme entre 0 et v0.
Un processus de Poisson d'origine 0 s'obtient en sommant des variables aléatoires indépendantes de loi exponentielle d'espérance T. Ainsi, l'événement 0 se produit à l'instant 0, l'événement 1 a une loi en (1/T)exp(-t/T)dt (d'espérance T), l'événement 2 a une loi en (t/T2)exp(-t/T)dt (d'espérance 2T), et ainsi de suite.
On peut aussi regarder la variable aléatoire N(t0) correspondant au nombre d'événements du processus se produisant entre 0 (exclu) et t0. La probabilité que N(t0) soit au moins 1 est la probabilité que le premier événement se produise avant t0, soit 1-exp(-t0/T). La probabilité que N(t0) soit au moins 2 est la probabilité que le deuxième événement se produise avant t0, soit 1-exp(-t0/T)-(t0/T)exp(-t0/T). Donc la probabilité que N(t0) soit 0 est exp(-t0/T), la probabilité que N(t0) soit 1 est (t0/T)exp(-t0/T), et plus généralement la probabilité que N(t0) soit k est [(t0/T)k/k!]exp(-t0/T). C'est la distribution de Poisson, dont l'espérance est t0/T, reflétant le fait qu'il y a « en moyenne » t0/T événements jusqu'à t0, et donc aussi sur n'importe quel intervalle de longueur t0, bref « un événement tous les T en moyenne ».
Il est intéressant de noter que malgré le choix d'une origine, on obtient le même résultat, i.e. exactement la même loi pour N(t0), si on compte les événements entre t1 et t2=t1+t0, c'est-à-dire sur n'importe quel intervalle de longueur t0. Nous ne ferons pas le calcul de cette variable N(t1,t2)=N(t2)-N(t1), mais on peut au moins se persuader que son espérance est (t2/T)-(t1/T) ce qui donne bien (t2-t1)/T.
On peut prolonger le processus de Poisson avec origine aux événements négatifs : on prend pour l'événement -1 une variable aléatoire indépendante des autres et ayant loi opposée à une loi exponentielle d'espérance T, et ainsi de suite. Les considérations sur la distribution de Poisson restent les mêmes (dans un intervalle de longueur t0, le nombre moyen d'événements est t0/T), avec une exception de taille : pour les intervalles contenant 0, la variable N est décalée de 1 par rapport à sa loi habituelle (et, notamment, le nombre moyen d'événements est 1+t0/T pour un intervalle de longueur t0 contenant 0). Cette exception conduit à penser que le processus de Poisson avec origine n'est pas le bon processus de Poisson.
Dans le processus de Poisson avec origine, on compte les temps à partir d'un moment où un événement s'est produit. Cette donnée supplémentaire brise la symétrie (l'invariance par translation désirée) du processus de Poisson. Dans un véritable processus de Poisson, on veut mesurer les temps à partir d'un moment quelconque.
L'approche naïve serait de prendre un réel aléatoire comme origine. Seulement, cela n'a pas de sens car il n'y a pas de loi de probabilité uniforme sur les réels. Une autre solution (peut-être préférée des « vrais » probabilistes) serait de faire tendre l'origine vers moins l'infini et espérer une convergence (je suppose, une convergence en loi, mais j'ai toujours été nul en probas) des processus. C'est là une méthode un peu compliquée. Il existe une méthode plus simple mais beaucoup plus surprenante.
Le procédé est le suivant : pour obtenir une loi de Poisson sans origine, on part d'une loi de Poisson avec origine, et on retire tout simplement l'événement 0 (on renumérote les événements positifs pour que le numéro 1 devienne le numéro 0 et ainsi de suite).
À première vue cela paraît complètement faux, parce que, dira-t-on, l'écart moyen entre l'événement 0 (anciennement événement 1) et l'événement -1 est de 2T alors que l'écart moyen entre deux autres événements consécutifs est seulement T.
Pourtant, on voit bien qu'il n'y a pas d'erreur possible. On part d'une origine quelconque (plutôt que d'une origine où un événement se produit). On attend l'événement 0 : par l'invariance par translation de la loi exponentielle cet événement a pour temps, à partir de l'origine choisie, une loi exponentielle d'espérance T. L'événement 1 a pour loi la somme de deux lois exponentielles, donc une espérance 2T, et ainsi de suite. La symétrie du passé et du futur donne les événements -1, -2 et ainsi de suite. Et il faut bien se rendre à l'évidence : l'événement 0 a espérance T, l'événement 1 espérance 2T, l'événement 2 espérance 3T, et ainsi de suite, mais l'événement -1 a espérance -T, l'événement -2 espérance -2T et ainsi de suite. Il y a « comme un trou » a l'espérance 0.
Là où on sait qu'on ne s'est pas trompé, c'est qu'en virant l'événement 0 on a éliminé l'anomalie du compte du nombre d'événements dans un intervalle de longueur t0.
Imaginons que la complexité du système ferroviaire soit telle que l'arrivée des trains dans une gare est vraiment imprévisible (suivant un processus de Poisson). Autrement dit, quel que soit le moment où on arrive, même s'il s'avère qu'un train vient de partir, l'attente moyenne jusqu'au train suivant sera une certaine durée T. C'est le propre d'une loi exponentielle que d'avoir ce comportement.
En particulier, si on compte à partir du départ d'un train, il faut attendre en moyenne T jusqu'au train suivant. Cela signifie que le nombre moyen de trains par unité de temps est 1/T (un train tous les T).
Mais si j'arrive à la gare à un instant (aléatoire) donné, le temps moyen jusqu'au prochain train est T. Cela dit, le temps moyen écoulé depuis le dernier train est également T, car il y a symétrie du passé et du futur. Ainsi, le temps moyen entre le dernier train et le prochain est 2T, et cela, quel que soit le moment où j'arrive.
Le « paradoxe » de la loi de Poisson est donc le suivant : le temps moyen entre deux événements est toujours T ; pourtant, quel que soit l'instant de référence choisi, le temps moyen entre le dernier événement avant cet instant et le premier événement après lui est 2T.
Le programme ci-dessous commence par afficher des statistiques (moyenne et écart-type) sur la loi exponentielle pure (pour vérifier que la fonction utilisée pour la construire fonctionne apparemment), d'espérance 1, en effectuant 10000 essais (on s'attend à trouver une moyenne de 1 et un écart-type de 1). Ensuite, pour différentes valeurs du « temps de référence », il affiche des statistiques successivement sur : le temps du dernier événement du processus de Poisson avant le temps de référence, le temps du premier événement du processus après le temps de référence, et l'intervalle entre les deux.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PRECISION 20
char
randombit (void)
/* Return 0 or 1 with probability 1/2 for each. This is our
* basic randomness function. */
{
return rand () % 2;
}
char
randombit_prob(double p)
/* Return 1 with probability p and 0 with probability 1-p. */
{
while ( 1 )
{
if ( p >= 1. )
return 1;
if ( p <= 0. )
return 0;
if ( randombit () )
p = 2.*p;
else
p = 2.*p - 1.;
}
}
double
exponential_between (double a, double b, int pre)
/* Return a random number following an exponential law (with
* average 1), but subject to the constraint that it be between a
* and b. This is not a user-serviceable function: use the next
* one instead. */
{
if ( pre >= PRECISION )
return a;
if ( randombit_prob ((exp (-a)-exp (-((a+b)/2.)))
/(exp (-a)-exp (-b))) )
return exponential_between (a, (a+b)/2., pre+1);
else
return exponential_between ((a+b)/2., b, pre+1);
}
double
exponential(void)
/* Returns a random number following an exponential law (with
* average 1) */
{
int n;
n = 0;
while ( randombit_prob (exp (-1.)) )
n++;
return exponential_between (n, n+1, 0);
}
void
statistics (int nbruns, double (*variable)(void),
double *avg, double *stddev)
/* Perform statistics on variable. Calculate it nbrun times and
* report the average and the standard deviation. */
{
int n;
double s, ssq;
double x;
s = 0;
ssq = 0;
for ( n=0 ; n<nbruns ; n++ )
{
x = variable ();
s += x;
ssq += x*x;
}
*avg = s/nbruns;
*stddev = sqrt ((ssq-s*s/nbruns)/nbruns);
}
double base;
double
poisson_before (void)
/* Return the greatest event in the Poisson process (without
* origin) time line that does not exceed time base. */
{
double x, y;
x = exponential ();
if ( x < base )
{
while ( x < base )
{
y = x;
x += exponential ();
}
return y;
}
else
{
x = -exponential ();
while ( x >= base )
x -= exponential ();
return x;
}
}
double
poisson_after (void)
/* Return the least event in the Poisson process (without origin)
* time line that does exceeds time base. */
{
double x, y;
x = -exponential ();
if ( x >= base )
{
while ( x >= base )
{
y = x;
x -= exponential ();
}
return y;
}
else
{
x = exponential ();
while ( x < base )
x += exponential ();
return x;
}
}
double
poisson_interval (void)
/* Return the length of the interval in the Poisson process
* (without origin) time line that surrounds base. */
{
double x, y;
x = exponential ();
if ( x < base )
{
while ( x < base )
{
y = x;
x += exponential ();
}
return x - y;
}
else
{
y = x;
x = -exponential ();
while ( x >= base )
{
y = x;
x -= exponential ();
}
return y - x;
}
}
int
main (void)
{
int i;
const static double bases[] = { 0., 0.6, 1.2, 1.8 };
const static int nbbases = 4;
double avg;
double stddev;
printf ("Pure exponential law:\n");
statistics (10000, &exponential, &avg, &stddev);
printf ("Average: %7.4f\nStd.dev: %7.4f\n\n", avg, stddev);
for ( i=0 ; i<nbbases ; i++ )
{
base = bases[i];
printf ("Base set to %7.4f\n", base);
printf ("Last event before base:\n");
statistics (10000, &poisson_before, &avg, &stddev);
printf ("Average: %7.4f\nStd.dev: %7.4f\n", avg, stddev);
printf ("First event after base:\n");
statistics (10000, &poisson_after, &avg, &stddev);
printf ("Average: %7.4f\nStd.dev: %7.4f\n", avg, stddev);
printf ("Interval around base:\n");
statistics (10000, &poisson_interval, &avg, &stddev);
printf ("Average: %7.4f\nStd.dev: %7.4f\n\n", avg, stddev);
}
return 0;
}
Un exemple de résulat expérimental est le suivant :
Pure exponential law: Average: 1.0096 Std.dev: 1.0047 Base set to 0.0000 Last event before base: Average: -0.9969 Std.dev: 1.0026 First event after base: Average: 1.0098 Std.dev: 1.0140 Interval around base: Average: 2.0232 Std.dev: 1.4073 Base set to 0.6000 Last event before base: Average: -0.4115 Std.dev: 1.0070 First event after base: Average: 1.5981 Std.dev: 1.0140 Interval around base: Average: 1.9853 Std.dev: 1.3985 Base set to 1.2000 Last event before base: Average: 0.2337 Std.dev: 0.9697 First event after base: Average: 2.1869 Std.dev: 0.9817 Interval around base: Average: 2.0037 Std.dev: 1.4076 Base set to 1.8000 Last event before base: Average: 0.8007 Std.dev: 1.0061 First event after base: Average: 2.8130 Std.dev: 1.0181 Interval around base: Average: 1.9824 Std.dev: 1.4102autrement dit, on constate bien que la moyenne de la loi exponentielle utilisée est 1 (donc, l'intervalle moyen entre deux événements), mais pourtant que quel que soit le temps de base choisi (0, 0.6, 1.2 ou 1.8), l'intervalle moyen entre l'événement précédent le temps de base et l'événement suivant est 2.
Il y a deux choses à expliquer. La première c'est comment il se peut que l'intervalle moyen entre deux événements dans un processus de Poisson soit T tandis que l'intervalle moyen autour d'un instant donné est 2T. La seconde c'est le manque apparent d'invariance par translation de notre construction du processus de Poisson sans origine.
Pour ce qui est du problème des intervalles, l'explication est vraiment simple : si on a une grande distance divisée en intervalles, la longueur moyenne d'un intervalle est la distance totale divisée par le nombre d'intervalles. Ce n'est pas la même chose que la longueur moyenne de l'intervalle contenant un point aléatoire, tout simplement parce qu'un point tiré au hasard dans la distance a plus de chance de tomber dans un grand intervalle que dans un petit.
(Un exemple idiot : si un des intervalles a longueur 1 et l'autre a longueur 999, la longueur moyenne est 500, tandis que la longueur moyenne de l'intervalle contenant un point aléatoire est 998.002.)
On peut d'ailleurs quantifier ce phénomène : la longueur moyenne est la somme des longueurs sur le nombre d'intervalle (la somme des 1), c'est l'espérance E(l) de la variable aléatoire l qui vaut la longueur d'un intervalle tiré au hasard avec même probabilité pour chacun. La longueur moyenne de l'intervalle contenant un point aléatoire est l'espérance d'une autre variable (qui donne à chaque intervalle une probabilité proportionnelle à sa longueur), c'est le rapport de la somme des longueurs au carré sur la somme des longueurs. Et cela s'écrit encore comme E(l)+(V(l)/E(l)) où V(l) est la variance de l. C'est donc toujours plus grand que E(l).
Dans le cas de Poisson, même si ce raisonnement n'est pas entièrement rigoureux, E(l) vaut 1, V(l) vaut 1, et donc la longueur moyenne de l'intervalle contenant un point (aléatoire — ou donné indépendamment du processus) est 2.
En revanche, si on prend un point et qu'on considère non pas la longueur de l'intervalle qui le contient mais celle de l'intervalle suivant ou précédent, on n'a pas de raison de trouver plus ou moins que E(l) (il s'agit là plutôt d'une affirmation intuitive, car cela dépend naturellement de la configuration des intervalles). Pour un processus de Poisson, c'est bien 1 partout ailleurs que pour l'intervalle contenant le point considéré.
Reste à expliquer pourquoi, dans la construction proposée du processus de Poisson sans origine, il y a une apparente brisure dans la symétrie par translation. C'est-à-dire que l'espérance de l'événement k est (k+1)T (en donnant le numéro 0 à l'événement qui suit l'origine arbitrairement choisie) et l'espérance de l'événement -k est -kT.
En vérité c'est ce que nous venons de faire. Le problème vient de la numérotation. Car c'est dans la numérotation des événements qu'est le choix d'une origine. La vérification expérimentale montre bien que quelle que soit l'origine choisie on a le même phénomène (et pourtant dans cette vérification le processus de Poisson était construit en partant de zéro).
Ce qu'on appelle « l'événement 2 » c'est le troisième événement suivant l'origine choisie, et ce ne peut pas être réinterprété comme le premier événement suivant une certaine origine. Le premier événement suivant l'instant 2T pourra être l'événement 0, 1, 2 ou même plus. La numérotation est donc fondamentalement dépendante du choix de l'origine, même si le processus lui-même n'en dépend pas.
Ou bien, si on veut, le processus de Poisson doit être considéré comme une loi de probabilité sur les ensembles fermés discrets infinis (par exemple) de R, ce qui n'est pas la même chose que les suites (non bornées, disons) de réels indicées par Z. C'est la même chose après quotient par une translation arbitraire des indices.
[ENS]
[Élèves ENS]
[David Madore]
[Mathématiques]
[Informatique]
[Programmes]
[Linux]
[Littérature]