Cours 6 : Probabilités

Introduction

Où les probas sont-elles présentes en informatique ?

  • Évaluation de performance :

    • complexité
    • correction
    • résultats en moyenne, etc…
  • de façon générale : on utilise les probas quand on ne sait pas faire autrement.

    • quand on est bloqué quelque part, les probas introduites “artificiellment” peuvent aider à “décoincer” la situation

      • exs :

        • protocoles en concurrence, etc…
        • modélisation d’un environnement : c’est beaucoup plus “régulé” qu’avec du non-déterminisme

Débat philosophique : est-ce que les probas relèvent du déterminisme ou non ?

Ex : résultat à un examen :

  • pour le prof : point de vue probabiliste
  • pour un élève donné : non déterministe

Caractère probabiliste = du non-déterministe régulé

Pour un matheux : les probas = une construction mathématique

Pour un physicien / informaticien :

  • l’aspect statistique est très important ⟶ que vaut $P$ ?
  • la pertinence du modèle est très importante

On se sert du peu d’information qu’on a :

ex : élections, etc…

choses qualitatives qui n’intéressent absolument pas les mathématiciens : en quoi l’échantillon de population choisie est-il représentatif de la population ?

Aujourd’hui : tout le monde fait des probas :

  • les biologistes
  • les physiciens
  • les sciences de l’ingénieur
  • les informaticiens
  • les mathématiciens

Attention : les statistiques appliquées ressemblent un peu aux protocoles de chimie :

  • on fait une hypothèse, et on corrobore cette hypothèse

Mais ce qui fait le succès de la démarche, c’est la pertinence de l’hypothèse :

  • elle se base sur un historique de causes-effets
  • etc…

Il faut comprendre quelque chose qui est dur à avaler pour un matheux :

quand on dit “soit $P$” une proba

⟶ on n’obtiendra jamais la vraie valeur de $P$ en pratique

⟶ on n’utilise que des théorèmes de convergence (en loi, en proba, presque sûre, etc …)

NB : on aura une petite bilbiothèque de problèmes qui nous serviront de “boîte à outils” (ex: problème du collectionneur, etc…)

Généralités

Espace de probabilité

Trouver un bon espace de proba : problème qui peut être très difficile en pratique :

  • si l’espace est trop grand : proba nulle
  • si trop petit : proba égale à 1
  • il faut trouver la bonne échelle “mésoscopique” où considérer nos objets

Paradoxe de Bertrand :

On a un triangle équilatéral inscrit dans un cercle.

Question : quelle est la proba qu’une corde prise “au hasard” soit plus grande que la longueur des côtés du triangle.

Trois modélisations possibles incompatibles :

  1. Proba = $1/3$

    • car en fixant un sommet $A$ du triangle, et en traçant une droite passant par ce sommet, on remarque que :

      • si la droite intersecte le côté opposé à $A$ : corde plus longue
      • sinon : corde plus courte
      • on procède de même pour une droite ne passant pas par $A$, en prenant $A$ comme “référentiel”.
  2. Proba = $𝜋𝜌^2/𝜋 = 1/4$ où $𝜌$ est le rayon du cercle inscrit

    • on remarque qu’une corde est entièrement déterminée par son milieu (à part si c’est un diamètre) qui est un point du disque.
    • en considérant le cercle inscrit au triangle : il faut et il suffit que le milieu soit dans ce disque pour que la corde soit plus grande
  3. Proba = $1/2$

    • en utilisant la symétrie circulaire : toute corde est déterminée par son point d’intersection avec le rayon qui lui est orthogonal.
    • si elle est dans la moitié du rayon la plus proche du centre : la corde est plus grande
    • sinon : elle est plus petite.

Soit $𝛺$ un ensemble.

Tribu $𝒯⊆𝒫(𝛺)$ sur $𝛺$ :
  1. $𝛺∈𝒯$
  2. Si $A∈𝒯$, $A^c∈𝒯$
  3. Si $(A_n)_{n∈ℕ} ∈ 𝒯^ℕ$, l’union le reste
Espace probabilisable :

la donnée d’un couple $(𝛺, 𝒯)$, où $𝒯⊆𝒫(𝛺)$.

Propriétés :

  1. $∅∈𝒯$
  2. Si $(A_n)_{n∈ℕ} ∈ 𝒯^ℕ$, l’intersection le reste
  3. De même : toute intersection/union finie d’événements reste un événement.
  4. Si $A, B ∈ 𝒯, A∩B^c ∈𝒯$

ex :

  • $\lbrace ∅, 𝛺\rbrace$ : tribu grossière
  • $𝒫(𝛺)$ : tribu discrète
  • notion de tribu engendrée par un ensemble : la plus petit le contenant

NB : Il nous faut un arsenal mathématique nous permettant de mesurer les éléments d’une tribu sans être capable pour autant de les décrire explicitement.

Probabilité $P : 𝒯 ⟶ [0,1]$ sur $(𝛺, 𝒯)$ :
  1. $P(𝛺)=1$
  2. Si $(A_n)_{n∈ℕ} ∈ 𝒯^ℕ$ et $∀i≠j, A_i ∩ A_j ≠ ∅$, alors

    P(\bigcup_i A_i) = \sum\limits_{i≥0} P(A_i)

On a alors :

3) Si $A∈𝒯$, P(A)+P(A^c) = 1

Dém : on montre facilement que $P(∅)=0$, avec la propriété 2).

Puis : avec $𝛺 = A \sqcup A^c$

4) Croissance : si $A⊆B$, $P(A)≤P(B)$

Dém : avec la propriété précédente, et $B = B\backslash A \sqcup A$

5) Si $(A_n)_{n∈ℕ} ∈ 𝒯^ℕ$ est une suite croissante :

P(\bigcup_i A_i) = \lim_{i⟶∞} A_i

Dém :

La suite $(P(A_i))_i$ est convergente (croissante et bornée).

En posant, pour tout $i≥1$ :

  • B_i = A_i\backslash A_{i-1}
  • $B_0 = A_0$

Les $B_i$ sont deux à deux disjoints.

P(\bigcup_i A_i) = P(\bigcup_i B_i) = \sum\limits_{i∈ℕ} P(B_i) \\ = \lim_{n⟶∞} \underbrace{\sum\limits_{i=0}^n P(B_i)}_{ = P(A_i)}

NB : les séries à termes positifs ne posent aucun problème, car il se s’agit que de suites croissante. Mais attention quand le signe n’est pas constant !

6) De même :

Si $(A_n)_{n∈ℕ} ∈ 𝒯^ℕ$ est une suite décroissante :

P(\bigcap_i A_i) = \lim_{i⟶∞} A_i

2. Indépendance

$(𝛺, 𝒯, P)$ espace probabilisé.

Famille d’événements $(A_i)_{i∈I}$ indépendants :

$∀J⊆I, J \text{ finie }$, P(\bigcap\limits_{j∈J} A_j) = \prod\limits_{j∈J} P(A_j)

Ex :

Deux événements $A, B$ sont indépendants ssi :

P(A∩B) = P(A)P(B)

Propriétés :

Si $A$ et $B$ sont indépendants :

  • $A$ et $B^c$ le sont
  • $A^c$ et $B^c$ aussi
  • Pour toute famille d’événements $(A_i){i∈I}$ indépendants : la famille $(B_i){i∈I}$ le reste, où :

    • $B_i = A_i$ OU $B_i = A_i^c$

3. Variables aléatoires

$(𝛺, 𝒯, P)$ espace probabilisé.

$E$ : espace probabilisable.

Variable aléatoire $X : 𝛺 ⟶ E$ munie de la proba :

$X$ est munie d’une proba $P_X$ définie par : P_X(x) = P( \underbrace{X^{-1}(x)}_{≝ X=x} )

Il y a deux cas :

  1. $E$ discret : $x∈E; (X=x)∈𝒯$
  2. $(E, 𝒰)$ espace probabilisable tel que

    $X : 𝛺 ⟶ E$ mesurable :

    $∀U∈𝒰, \, \, \underbrace{X^{-1}(U)}_{≝ X∈U} ∈ 𝒯$

    et on pose :

    P_X(U) = P( \underbrace{X^{-1}(U)}_{≝ X∈U} )

lorsque la variable $X$ est réelle ($E⊆ℝ$), on peut éventuellement lui associer une espérance est une variance.

Espérance de $X$ :
E(X) ≝ \sum\limits_{x∈E} x P(X=x)
  • \vert E(X) \vert ≤ E(\vert X \vert)
Variance de $X$ :
V(X) ≝ E((X-E(X))^2) = E(X^2) - E(X)^2

si ces quantités existent (même si elles valent $+∞$)

  • Si $X, Y$ sont indépendantes, et si ceci a un sens :

    V(X+Y) = V(X) + V(Y)

NB :

  • Si $E = ℝ$ : variable à densité.
  • L’ensemble des fonctions de carré intégrable est préhilbertien (en quotientant par les fonctions de mesure nulle) :

    Cauchy-Schwartz :

    E(XY) ≤ \sqrt{E(X^2)}\sqrt{E(Y^2)}

Quelques lois classiques

Loi de Bernoulli $B(p)$

Prend deux valeurs : 0 et 1.

Avec $q=1-p$

  • P(X=0) = P(X=1) = \frac 1 2
  • E(X) = p
  • V(X) = pq

Loi Binomiale $B(n,p)$

Compte le nombre de 1 obtenus après $n$ expériences indépendantes de Bernoulli de paramètre $p$.

$X_1, ⋯, X_n \rightsquigarrow B(p)$ indépendantes.

X = \sum\limits_{k=1}^n X_i

compte le nombre de 1.

Avec $q=1-p$

  • P(X=k) = \binom{n}{k} p^k q^{n-k}
  • E(X) = np Dém: linéarité de l’espérance.
  • V(X) = npq Dém : variance d’une somme de variables indépendante = la somme des variances (car les covariances sont nulles, car les espérances des produits sont les produits des espérances (car variables indépendantes)).

Loi Géométrique $𝒢(p)$

Donne le range d’arrivée du premier 1 obtenus dans une suite d’expériences indépendantes de Bernoulli de paramètre $p$.

$∀i∈ℕ^\ast, X_i \rightsquigarrow B(p)$, les $X_i$ étant indépendantes.

X = \begin{cases} +∞ \, \, \text{ si } \, \, ∀i, X_i = 0 \\ j \, \, \text{ si } \, \, ∀i<j; X_i = 0 ∧ X_j = 1 \end{cases}

Avec $q=1-p$

  • Si $j ∈ ℕ^\ast$,

    • $P(X=j) = q^{j-1}p$ si $j>0$
    • $P(X=+∞) = 0$
  • E(X) = \sum\limits_{j≥1} j(1-p)^{j-1}p = \frac 1 p
  • V(X) = \sum\limits_{j≥1} j^2(1-p)^{j-1}p - \frac 1 p = \frac{q}{p^2}

Loi de Poisson $𝒫(𝜆)$

Compte des choses qui n’arrivent pas souvent : c’est la limite en loi de $B(n, \frac{𝜆}{n})$.

Avec $q=1-p$

  • P(X=n) = {\rm e}^{-𝜆} \frac{𝜆^n}{n!}
  • E(X) = {\rm e}^{-𝜆} \sum\limits_{n≥0} n \frac{𝜆^n}{n!} = 𝜆
  • V(X) = 𝜆

Exemples

Le problème des anniversaires

Dans une classe de $n$ étudiants, quelle est la proba que (au moins) deux étudiants soient nés le même jour ? (En supposant les dates de naissance uniformément réparties dans l’année).

“Les $n$ étudiants nés tous à des dates différentes” se modélise par un événement :

\{(d_1, ⋯, d_n) \vert ∀i≠j, d_i ≠d_j\} ⊆ [1, 365]^n

de proba

\frac{365×364×⋯×(365-(n-1))}{365^n} \\ = \Big(1-\frac{1}{365 }\Big)\Big(1-\frac{2}{365 }\Big) ⋯ \Big(1-\frac{n-1}{365 }\Big)

Un calcul assure que la proba que deux étudiant au moins soient nés le même jour est

  • $≥0,5$ pour $n≥23$
  • $≥0,89$ pour $n≥40$

Le problème du collectionneur de coupons

Quel est le nombre moyen de boîtes de céréales à acheter pour avoir toute la collection des $N$ photos de basketteurs à collectionner ?

Pour $i∈\lbrace 1, ⋯, N\rbrace$, soit $T_i$ le nombre de boîtes à acheter une fois obtenus $(i-1)$ objets pour obtenir le $i$-ième

  • $T_1 = 1$
  • Pour $k≥1$ : $P(T_2 = k) = \big(\frac 1 N\big)^{k-1} \big(1 - \frac 1 N\big)$

    Donc $T_2 \leadsto 𝒢\big(1-\frac 1 N\big)$

  • Pour $k≥1$ : $P(T_i = k) = \big(\frac{(i-1)}{N}\big)^{k-1} \big(1 - \frac{(i-1)}{N}\big)$

    Donc $T_i \leadsto 𝒢\big(1-\frac{(i-1)}{N})$

La v.a comptant le nb de boîtes achetées est

\sum_1^N T_i

Le nb moyen de boîtes achetées est :

E\left(\sum_1^N T_i\right) = \sum_1^N E(T_i) \\ = N \sum_1^N \frac{1}{N-(i-1)} \\ = N \sum_1^N \frac{1}{i} \\ = N H_N \sim N \log N

NB :

  • On peut démontrer que c’est quand les objets sont uniformément répartis que cette espérance est minimale.

  • Si on diminue la proba d’un seul objet arbitrairement, l’espérance peut devenir arbitrairement grande.

Le problème de l’expéditeur étourdi

Un très mauvais expéditeur insère $n$ lettres dans $n$ enveloppes destinées à une adresse, au hasard.

Cette attribution aléatoire définit une permutation de $𝕾_n$.

Dérangement :

permutation sans point fixe.

NB : dans les algorithmes de tri, ce sont souvent ces permutations qui provoquent le pire cas.

Quelle est la proba d’avoir un dérangement ?

Dans $𝕾_n$ :

Si $i∈⟦1,n⟧$,

F_i ≝ \{𝜎∈𝕾_n \vert 𝜎(i)=i\}

Si $i_1 < ⋯ <i_p$,

F_{\lbrace i_1, ⋯, i_p \rbrace} ≝ F_{i_1} ∩ ⋯ ∩ F_{i_p}

\vert F_I \vert = (n-\vert I \vert)!

Par la formule du Crible :

\vert \lbrace \text{permutations avec au moins un point fixe}\rbrace \vert = \vert \bigcup\limits_{i=1}^n F_i \vert \\ = \sum\limits_{i=1}^n \vert F_i \vert - \sum\limits_{\vert I \vert = 2} \vert F_I \vert + \sum\limits_{\vert I \vert = 3} \vert F_I \vert + ⋯ + (-1)^{n-1} \sum\limits_{\vert I \vert = n} \vert F_I \vert \\ = n(n-1)! - \binom{n}{2}(n-2)! + ⋯ + (-1)^{n-1}

La proba cherchée vaut donc :

\frac{1}{2!} - ⋯ + \frac{(-1)^{n}}{n!}

La proba d’avoir un dérangement tend vers $1/e$ lorsque $n$ tend vers $+∞$.

II. Probabilités conditionnelles

Cadre mathématique

$(𝛺, 𝒯, p)$ espace probabilisé.

Soit $B$ un événement non négligeable.

La proba conditionnée par $B$ est :

P(\bullet \vert B) = A \mapsto P(A∩B)/P(B)

Proposition : on vérifie aisément que ça reste une probabilité.

NB :

  1. Si $A⊆ B^c$, $P(A\vert B) = 0$
  2. Si $A$ et $B$ sont indépendants,

    P(A\vert B) = P(A)

Formule des probablités totales :

Soit $\lbrace B_i \rbrace_{i∈I}$ un système complet d’événements, i.e une famille d’événement

  • non négligeables
  • deux à deux disjoints
  • dont la réunion vaut l’espace entier

Alors pour tout événement $A$, P(A) = \sum_{i∈I} \underbrace{P(A\vert B_i) P(B_i)}_{= P(A∩B_i)}

Formule de Bayes :

Si $A$ et $B$ sont non négligeables,

P(A\vert B) P(B) = P(B\vert A) P(A)

$(= P(A∩B))$

Conditionnement d’une variable aléatoire par une autre

$X, Y$ deux variables aléatoires discrètes.

$Y$ prend ses valeurs dans un ensemble $E$ tq

∀x∈E, P(Y=x)≠0

On peut conditionner $X$ par $(Y=x)$

$(X \vert Y=x)$ est une v.a de loi :

P(X=z \vert Y=x) pour $z∈E$.

On définit $(X \vert Y)$ la v.a définie par :

pour tout $x∈E$, elle prend la valeur

(X \vert Y=x)

III. Chaînes de Markov (à ensemble d’états fini et homogènes)s

Introduction

Chaîne de Markov homgoène à ensemble d’états fini :

c’est une promenade aléatoire sur un graphe fini.

Exemples

Jeu de Penney (cf. TD7)

Alice et Bob jouent à pile ou face, et l’un des deux gagne dès qu’il/elle tombe sur son motif.

Ex :

  • Motif d’Alice : PFF
  • Motif de Bob : PPF
digraph {
        rankdir=LR;
    	0 -> 0[label="F"];
		0 -> 1[label="P"];
        1 -> 2[label="P"];
        2 -> 2[label="P"];
        2 -> Bob_gagne[label="F"];
        1 -> 3[label="F"];
        3 -> 1[label="P"];
        3 -> Alice_gagne[label="F"];
	}

Chaque arête est de proba $1/2$ (si la pièce est équilibrée).

Une partie correspond à la lecture d’un mot dans cet automate.

Collectionneur d’objets

digraph {
        rankdir=LR;
        kplus[label="k+1"];
        ⋯2[label="⋯"];
		0 -> 1[label="1"];
        1 -> 1[label="1/N"];
        1 -> 2[label="(N-1)/N"];
        2 -> 2[label="2/N"];
        2 -> 3[label="(N-2)/N"];
        3 -> ⋯;
        ⋯ -> k;
        k -> k[label="k/N"];
        k -> kplus[label="(N-k)/N"];
        kplus -> ⋯2;
        ⋯2 -> N;
	}

Leave a comment