Gentille introduction aux probabilitésGentille introduction aux probabilit es Fr ed eric Havet MASCOTTE, commun I3S(CNRS/UNSA)-INRIA Sophia Antipolis Caf e des Science { Rians { 14

Gentille introduction aux probabilites

Frederic Havet

MASCOTTE, commun I3S(CNRS/UNSA)-INRIA Sophia Antipolis

Cafe des Science – Rians – 14 fevrier 2012

Probabilites (discretes)

espace de probabilites: (Ω,Pr)Ω est un ensemble fini, ensemble des possiblesPr : Ω→ [0, 1] fonction de probabilite t. q.

∑ω∈Ω Pr(ω) = 1.

Exemple: Lancer de de.Ω = ω1, ω2, ω3, ω4, ω5, ω6 avec ωi = le de marque i .Plusieurs fonctions de probabilite possibles:

I de equilibre: Pr1(ωi ) = 16 pour tout i . distribution

uniforme

I de pipe: Pr2(ω6) = 14 , Pr2(ω1) = 1

12 , Pr2(ωi ) = 16 pour

i = 2, 3, 4, 5.

Evenement

evenement: sous-ensemble A de Ω. Pr(A) =∑

ω∈A Pr(ω).

Exemple: A = “le de marque au moins 4”.

Pr(A) = Pr(ω4) + Pr(ω5) + Pr(ω6)

I de equilibre: Pr1(A) = 1/6 + 1/6 + 1/6 = 1/2 = 0, 5.

I de pipe: Pr2(A) = 1/6 + 1/6 + 1/4 = 7/12 = 0.58333....

Probabilites conditionnelles et independance

probabilite (conditionnelle) de A sachant B: Pr(A|B) = Pr(A∩B)Pr(B)

(si Pr(B) = 0 alors Pr(A|B) = Pr(A)).

A est independant de B si Pr(A|B) = Pr(A)i.e. Pr(A ∩ B) = Pr(A) Pr(B).

L’independance n’est pas un etat de choses.Vaclav Havel

Probabilites conditionnelles et independance

Le plus souvent Pr(A|B) > Pr(A∩B)Pr(B) ou Pr(A|B) < Pr(A∩B)

Pr(B) .

Bob achete une voiture au hasard.

Sachant que 20% des voitures sont grises, il se dit que laprobabilite qu’elle soit grise est 0,2.

I Le vendeur lui dit que c’est une Ferrari. Comme 5% desFerraris sont grises, la probabilite qu’elle soit grise est 0,05.

I Le vendeur lui dit que c’est un break. Comme 60% des breakssont gris, la probabilite qu’elle soit grise est 0,6.

Probabilites conditionnelles

Supposons que l’on tire k fois de suite a pile ou face avec unepiece qui retombe sur pile avec probabilite 1/2 et sur face avecprobabilite 1/2.

Quelle est la probabilite qu’au dernier jet la piece donne pile?

Quelle est la probabilite qu’au dernier jet la piece donne pile,sachant qu’elle vient de tomber k − 1 fois sur face?

Probabilites conditionnelles

Quelle est la probabilite qu’au dernier jet la piece donne pile?

PPPP, PPPF, PPFP, PPFF, PFPP, PFPF, PFFP, PFFF,FPPP, FPPF, FPFP, FPFF, FFPP, FFPF, FFFP, FFFF.

Pr = 2k−1/2k = 1/2

Quelle est la probabilite qu’au dernier jet la piece donne pile,sachant qu’elle vient de tomber k − 1 fois sur face?PPPP, PPPF

Pr = 1/2

Jeu des trois portes

Dans une emission tele, un joueur a le choix entre trois portes.Derriere l’ une, le gros lot. Derriere les deux autres, rien.Il gagnera ce qui se cache derriere la porte de son choix. Lepresentateur sait ce qu’il y a derriere les portes mais ne dira rien.

I Le candidat choisit une porte.

I Le presentateur ouvre une des deux autres, derriere laquelle nese trouve rien.

I Le presentateur propose au candidat de changer son choix.

Que doit-faire le candidat ?


Deux possibilites :

Cas 1 le candidat choisit la bonne porte; le presentateur ouvren’importe quelle autre porte; si le candidat change il perd, s’ilne change pas il gagne.

Cas 2 le candidat choisit une mauvaise porte; le presentateur ouvrel’autre mauvaise porte; si le candidat change il gagne, s’il nechange pas il perd.

Dans premier cas il ne faut pas changer, dans le deuxieme il le faut.


Deux possibilites :

Cas 1 le candidat choisit la bonne porte; le presentateur ouvren’importe quelle autre porte; si le candidat change il perd, s’ilne change pas il gagne.

Cas 2 le candidat choisit une mauvaise porte; le presentateur ouvrel’autre mauvaise porte; si le candidat change il gagne, s’il nechange pas il perd.

Dans premier cas il ne faut pas changer, dans le deuxieme il le faut.

Mais pas equiprobables : Pr(Cas 1) = 1/3 et Pr(Cas 2) = 2/3.

Il vaut donc mieux changer.

Hasard, vous avez dit “Hasard”....

Est-ce vraiment un hasard ?

“Paradoxe” des anniversaires

Combien de personnes doit-on reunir dans une piece pour que deuxd’entre elles au moins aient la meme date de naissance ?(pas d’annee bissextile, les dates sont equiprobables)


Combien de personnes doit-on reunir dans une piece pour que deuxd’entre elles au moins aient la meme date de naissance ?(pas d’annee bissextile, les dates sont equiprobables)

Principe des tiroirs: 366 personnesSi 365 personnes, elles peuvent avoir des dates differentes.

MAIS: Cas au pire.Tres peu probable d’avoir 365 personnes, toutes de datesdifferentes. 1 chance sur 365× 364× · · · × 1 = 2, 5× 1079.


Combien de personnes doit-on reunir dans une piece pour qu’avecprobabilite au moins 1/2 deux d’entre elles au moins aient lameme date de naissance ?(pas d’annee bissextile, les dates sont equiprobables)


Combien de personnes doit-on reunir dans une piece pour qu’avecprobabilite au moins 1/2 deux d’entre elles au moins aient lameme date de naissance ?(pas d’annee bissextile, les dates sont equiprobables)

Dk : evenement que k personnes aient toutes des dates differentes.

k = 1: Abel seul, pas de coincidence: Pr(D1) = 1.

k = 2: Boole entre, 364 dates differentes de celle d’Abel:Pr(D2) = 364/365.

k = 3: Cantor entre, 363 dates differentes de celles d’Abel etBoole: Pr(D3) = (364/365)× (363/365).

k quelconque:Pr(Dk) = (364/365)× (363/365)× · · · × (365− k + 1/365).


Pr(Dk) decroit et tend vers 0 quand k tend vers l’infini.Pr(D22) = 0, 524, et Pr(D23) = 0, 493.

Donc, des que 23 personnes sont rassemblees, la probabilite d’unecoıncidence au moins est 1− 0, 493 = 0, 507 : l’evenement estlegerement plus probable que son contraire.

Moralite

Mefiez-vous des coıncidences . . .

. . . elles sont parfois tres probables.

Autre question d’anniversaires

Combien de personnes en plus de vous-meme doivent etre dans lapiece pour que l’evenement “une personne au moins a votre datede naissance” soit plus probable que son contraire ?



Intuition fausse: d365/2e = 183, puisqu’il y a 365 datesdifferentes. Si plus de la moitie de ce nombre de personnes setrouve dans la salle, vous avez plus d’une chance sur deux departager votre date de naissance avec l’une d’elles.



Reponse correcte: 253.Ek : evenement que k personnes aient toutes des dates differentesde la votre.

k = 1: Alembert entre, 364/365 chances d’avoir une datedifferente de la votre: Pr(E1) = 364/365.

k = 2: Bernouilli entre, 364/365 chances d’avoir une datedifferente de la votre: Pr(E2) = (364/365)2.

k quelconque: Pr(Ek) = (364/365)k .

Pour k < 253, Pr(Ek) > 1/2, pour k ≥ 253, Pr(Ek) < 1/2.

Certains pronostiqueurs et faux devins l’avaientabuse de vaine esperance.

Ciceron.

Variables aleatoires et esperance

variable aleatoire: fonction Ω→ R.

esperance d’une variable aleatoire X : E(X ) =∑ω∈Ω

Pr(ω)X (ω).

X1: nombre de points avec le de equilibre.

E(X1) =1

6×1 +

1

6×2 +

1

6×3 +

1

6×4 +

1

6×5 +

1

6×6 =

7

2= 3, 5.

X2: nombre de points avec le de pipe.

E(X2) =1

12×1+

1

6×2+

1

6×3+

1

6×4+

1

6×5+

1

4×6 =

47

12= 3, 9166.

Linearite de l’Esperance Si X =n∑

i=1

Xi , alors E(X ) =n∑

i=1

E(Xi ).

X : nombre de points avec les deux des. E(X ) = 8912 = 7, 4166.

Loto

Mise: 2 euros pour une grille.Choix: 5 numeros entre 1 et 49 et un numero chance entre 1 et 10.

Pr(k bons numeros) = 1/

(49

k

)=

1× 2× · · · × k

49× 48× · · · × (50− k)

Combinaison Rapport Proba5 bons numeros + chance 5 000 000 1/19 068 8405 bons numeros 300 000 1/1 906 8844 bons numeros 2 500 1/211 8763 bons numeros 15 1/18 4242 bons numeros 7 1/1 176numero chance 2 1/10

Esperance de gain inferieure a

5 000 000

19 068 840+

300 000

1 906 884+

2 500

211 876+

15

18 424+

7

1176+

2

10≤ 0, 64

Ecart type et variance

Ecart type: ecart moyen avec l’esperance. σ(X ) = E(|X − E(X )|).

Pour le de equilibre :

σ(X1) =1

6(2, 5 + 1, 5 + 0, 5 + 0, 5 + 1, 5 + 2, 5) = 1, 5.

Pour le de pipe :

σ(X2) =1

12× 35

12+

1

6

(23

12+

11

12+

1

12+

13

12

)+

1

4× 25

12=

103

72

= 1, 4305...

Variance: carre de l’ecart type. var(X ) = σ2(X ) = E(X 2)−E(X )2.

Marche de l’ivrogneUn ivrogne marche. A chaque pas, il titube et se decale d’un pasvers la droite ou vers la gauche de maniere aleatoire.

I l’esperance est nulle ;I la variance vaut n et l’ecart type

√n.

Marche de l’ivrogneUn ivrogne marche. A chaque pas, il titube et se decale d’un pasvers la droite ou vers la gauche de maniere aleatoire.

I l’esperance est nulle ;I la variance vaut n et l’ecart type

√n.

Marche aleatoire de dimension 1

Deviation en√

n.

I avec perspective, impression que l’ivrogne garde son cap.

I detection de des pipes, ... 3, 5 +√nn < 47

12 .(Loi des grands nombres).

I Sondage entre deux propositions sur 1 000 personnes. Ecarttype de

√1000 ' 31, 6 soit environ 3, 16 %.

Pour un ecart type de 1%, il faudrait 10 000 personnes.

Une marche infinie croise n’importe quel niveau un nombre infinide fois.

I Ruine du parieur.

Marche de l’ivrogne (2)

Dans une ville ideale (= grille), un ivrogne essaie de rentrer chezlui. Arrive a chaque intersection, il choisit au hasard une routeparmi les 4 possibles (dont celle d’ou il vient) avec egaleprobabilite (1/4).

C’est une marche aleatoire sur la grille infinie a deux dimensions.

Presque surement, l’ivrogne va finir par passer devant chez lui.

Moralite

Il y a les probabilites pour les ivrognes.

Le hasard, c’est Dieu qui se promene incognito.

Albert Einstein

Toute connaissance degenere en probabilite.

David HumeTraite de la nature humaine

Percolation

On considere la grille infinie.

L’existence de chaque arete est tiree au hasard independamment.

I Avec probabilite p, l’arete existe;

I Avec probabilite 1− p, l’arete n’existe pas.

On fait augmenter p et on regarde l’evolution du graphe.On regarde la taille des composantes.

Percolation

p = 0.4

Percolation et transition de phase

p = 0.5


p = 0.6

Transition de phase

I p < 1/2 : toutes les composantes sont petites (finies). Pleinsde petites ıles dans un grand ocean ouvert.

I p = 1/2 : complexe. Pas de composante infinie, maisbeaucoup de grandes.

I p > 1/2 : UNE composante geante avec une infinite desommets. Un grand continent avec pleins de petits lacs.

Pleins de phenomenes (confiture, transition liquide-gaz, ...)s’expliquent par des modeles de la sorte.


Moralite

Avec les probabilites, on peut faire des confitures.

Il suffit d’ajouter des fruits et du sucre.

Petits mondes

Experience de Milgram (1967) :

I Lettre avec nom, profession, adresse du destinataire.

I Envoyer en faisant passer de connaissance en connaissance.

100 personnes : 20 lettres a destination, chaines de longueur entre2 et 10, en moyenne 5.

Doods, Muhamad et Watts (2003) :Meme experience mais avec courriel.25 000 sources et 12 destinations.∼ 400 a destination par des chaınes de longueur 4 en moyenne(entre 1 et 10).

I Le monde est petit. Pourquoi?

I Comment se fait-il qu’on trouve des chaines courtes?

Le modele de Kleinberg

Idee : les gens connaissent leur voisinage et quelques personneslointaines au “hasard” des rencontres.

Ils connaissent la localisation des personnes dans l’espace(geographie, metier, . . . ).

Modele : graphe de proximite (disons une grille);pour chaque sommet et on rajoute une connaissance au hasarddans le graphe.

Chaque personne fait passer la lettre a sa connaissance la plusproche de la destination.

Le modele de Kleinberg (Exemple)

Le modele de Kleinberg (resultats)

Si on prend une grille a deux dimensions (critere geographiqueseul).

Resultat varie suivant la fonction de probabilite choisie pour laconnaissance supplementaire.

I proba. uniforme : les lettres mettent un temps long(proportionnel a la taille de la grille) pour arriver.

I proba. inversement proportionnelle au carre de la distance :les lettres mettent un temps court (logarithmique en la taillede la grille) pour arriver.

Moralite

Le hasard fait parfois bien les choses.

Documents

Gentille introduction aux probabilitésGentille introduction aux probabilit es Fr ed eric Havet MASCOTTE, commun I3S(CNRS/UNSA)-INRIA Sophia Antipolis Caf e des Science { Rians { 14