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