Probabilités discrètes

Comme on est en informatique, on va considérer des ensembles finis ou au pire dénombrables.

Probabilités

Définitions

Définition
  • univers : $\Omega$ un ensemble fini.
  • probabilité : $p : \Omega \rightarrow [0, 1]$ telle que $\sum\limits_{x \in \Omega} p(x) = 1$.

La probabilité $p$ est dite uniforme si $p(x) = \frac{1}{\vert \Omega \vert}$ pour tout $x \in \Omega$.

Par défaut, toutes les probabilités seront uniformes.

On étend la notion de probabilité aux ensembles :

Définition

On définit la probabilité $\mathbb{P}(A)$ d'un évènement $A \subseteq \Omega$ comme étant :

$$ \mathbb{P}(A) \coloneqq \sum_{x \in A}p(x) $$

Cette définition se généralise simplement aux ensembles dénombrables (ce qui est réaliste, à défaut d'être réel, en informatique) :

Définition
  • univers : $\Omega$ un ensemble dénombrable.
  • probabilité : $\mathbb{P} : \mathcal{P}(\Omega) \rightarrow [0, 1]$ telle que :
    • $\mathbb{P}(\Omega) = 1$.
    • Pour toute suite $(A_n)_{n\in \mathbb{N}}$ d'éléments deux à deux disjoints de $\mathcal{P}(\Omega)$, on a : $\mathbb{P}(\bigcup\limits_n A_n) = \sum\limits_n \mathbb{P}(A_n)$

Le couple $(\Omega, \mathbb{P})$ est appelé espace probabilisé. On dit aussi que $\mathbb{P}$ est une probabilité sur $\Omega$.

Notez que la définition dénombrable généralise bien la définition du cas fini puisqu'une suite finie $(A_n)_{1\leq n \leq N}$ d'éléments deux à deux disjoints peut s'écrire comme une suite infinie où $A_n =\emptyset$ pour tout $n > N$.

Un exemple d'espace probabilisé pourrait être $(\mathbb{N}, \mathbb{P})$ avec $\mathbb{P}$ défini uniquement sur les entiers : $\mathbb{P}(\{n\}) = \frac{n}{2^{n+1}}$. On a alors $\mathbb{P}(A) = \sum_{x\in A} \mathbb{P}(\{x\})$. Cet exemple montre que, comme dans le cas fini, on n'a besoin que de peu d'évènements pour inférer toute la probabilité. Ce ne sont plus forcément des singletons mais des partitions de $\Omega$ que l'on appelle systèmes complets d'évènements :

Définition

Soit $\Omega$ un ensemble dénombrable. Un système complet d'évènements est une partition $\Omega$, c'est à dire une suite $(A_n)_{n\in \mathbb{N}}$ d'éléments deux à deux disjoints de $\mathcal{P}(\Omega)$ telle que $\bigcup_n A_n = \Omega$.

On a les propriétés suivantes dont les preuves sont triviales :

Proposition

Pour tout espace probabilisé $(\Omega, \mathbb{P})$ on a :

  • $\mathbb{P}(\varnothing) = 0$
  • $\mathbb{P}(\Omega) = 1$
  • $\mathbb{P}(\Omega\backslash A) = 1 - \mathbb{P}(A)$
  • $\mathbb{P}(A \cup B) = \mathbb{P}(A) + \mathbb{P}(B) - \mathbb{P}(A \cap B)$

Indépendance

Une notion que l'on utilisera souvent est la notion d'indépendance entre 2 ensembles. L'ensemble $A$ est dit indépendant de l'ensemble $B$ si la probabilité d'être dans $A$ pour un élément de l'univers ($\frac{\mathbb{P}(A)}{\mathbb{P}(\Omega)}$) est la même que la probabilité d'être dans $A$ pour les éléments de $B$ ($\frac{\mathbb{P}(A \cap B)}{\mathbb{P}(B)}$). Comme $\mathbb{P}(\Omega) = 1$ on utilise la définition suivante :

Définition

Soit $\mathbb{P}$ une probabilité sur $\Omega$. Les ensembles $A$ et $B$ sont dits indépendants si :

$$ \mathbb{P}(A \cap B) = \mathbb{P}(A) \cdot \mathbb{P}(B) $$

Conditionnement

Le pendant de l'indépendance est le conditionnement où on ne considère que les probabilités où un évènement donné est réalisé. Cela permet de répondre aux questions de type "quelle est la probabilité de $A$ sachant que $B$ est vrai ?". On peut alors définir la notion ainsi :

Définition

Soit $\mathbb{P}$ une probabilité sur $\Omega$ et $B$ un évènement tel que $\mathbb{P}(B) > 0$. La probabilité de $A$ sachant $B$ est définie telle que :

$$ \mathbb{P}_B(A) \coloneqq \mathbb{P}(A \vert B)\coloneqq \frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)} $$

C'est bien une probabilité :

Proposition

Si $(\Omega, \mathbb{P})$ est un espace probabilisé alors $\mathbb{P}_B$ est une probabilité sur $\Omega$ quel que soit $B \subseteq \Omega$ tel que $\mathbb{P}(B) > 0$.

preuve

  • $\mathbb{P}_B(\Omega) = \frac{\mathbb{P}(B\cap \Omega)}{\mathbb{P}(B)} = 1$.
  • Pour toute suite $(A_n)$ d'éléments deux à deux disjoints de $\mathcal{P}(\Omega)$ la restriction de la suite $(A^\prime_n)_{n\in \mathbb{N}}$ définie telle que $A^\prime_n = A_n \cap B$ est également d'éléments deux à deux disjoints. De là : $\mathbb{P}_B(\bigcup\limits_n A_n) = \frac{\mathbb{P}((\bigcup\limits_n A_n) \cap B)}{\mathbb{P}(B)} = \frac{\mathbb{P}(\bigcup\limits_n (A_n \cap B))}{\mathbb{P}(B)} = \frac{\mathbb{P}(\bigcup\limits_n A^\prime_n)}{\mathbb{P}(B)} = \sum\limits_n \frac{\mathbb{P}(A^\prime_n)}{\mathbb{P}(B)} = \sum\limits_n \frac{\mathbb{P}(A_n \cap B)}{\mathbb{P}(B)} = \sum\limits_n \mathbb{P}_B(A_n)$

On a alors les deux propositions suivantes qui vont servir de cadre à l'utilisation du conditionnement :

Proposition (Formule des probabilités totales)

Si $(\Omega, \mathbb{P})$ est un espace probabilisé et $(B_n)$ un système complet d'évènements, on a pour tout évènement $A$ :

$$ \mathbb{P}(A) = \sum\limits_n(\mathbb{P}(B_n)\cdot \mathbb{P}(A \mid B_n)) $$

preuve

$$ \mathbb{P}(A) = \mathbb{P}(A \cap \Omega) = \mathbb{P}(A \cap (\bigcup_n B_n)) = \mathbb{P}( \bigcup_n (A \cap B_n)) = \sum\limits_n\mathbb{P}(A \cap B_n) = \sum\limits_n(\mathbb{P}(B_n)\cdot \mathbb{P}(A \mid B_n)) $$

Proposition (Théorème de Bayes)

Si $(\Omega, \mathbb{P})$ est un espace probabilisé, pour tous évènements $A$ et $B$ de probabilités non nulles on a :

$$ \mathbb{P}(A \mid B) =\frac{\mathbb{P}(A)\cdot \mathbb{P}(B \mid A)}{\mathbb{P}(B)} $$

preuve

Par définition :

$$ \mathbb{P}(A \cap B) = \mathbb{P}(A) \cdot \mathbb{P}(B \mid A) = \mathbb{P}(B) \cdot \mathbb{P}(A \mid B) $$

Variables aléatoires

Les événements se manifestent via des variables aléatoires. L'univers étant souvent soit inconnu soit trop compliqué pour en tirer quoi que ce soit d'utile.

Définitions et notations

Définition

Une variable aléatoire $X$ est une fonction $X : \Omega \rightarrow \mathcal{U}$ ($\mathcal{U}$ quelconque a priori) où $(\Omega, \mathbb{P})$ est un espace probabilisé. On note alors :

  • ${\Pr}[X = u] \coloneqq \mathbb{P}(X^{-1}(\{u\}))$
  • $\Pr[X \in U] \coloneqq \mathbb{P}(X^{-1}(U))$,
  • $\Pr[X \in U \, , \, Y \in V] \coloneqq \mathbb{P}(X^{-1}(U) \cap Y^{-1}(V))$ (les deux variables aléatoires sont sur le même espace probabilisé)

On dira que $X(\omega) = x$ est une réalisation de la variable aléatoire $X$. Cette réalisation est de probabilité $\Pr[X = u]$.

Ne confondez pas la variable aléatoire et ses réalisations.

Comme une variable aléatoire est indissociable de sa mesure de probabilité associée et que l'espace $\Omega$ sous-jacent est très souvent inutile (et inconnu), on l'omettra la plupart du temps.

À retenir

S'il n'y a pas ambiguïté, on écrira :

  • ${\Pr}[x = k]$ si l'on s'intéresse aux réalisations $X(\omega) = x$ de la variable aléatoire $X$
  • ${\Pr}[X = k]$ si l'on veut expliciter la variable aléatoire $X$

Enfin, pour nos cas d'application on utilisera toujours ces types de variables aléatoires :

Définition

Une variable aléatoire est dite :

  • réelle si elle prend ses valeurs dans $\mathbb{R}$
  • simple si elle prend un nombre fini de valeurs,
  • discrète si elle prend au plus un nombre dénombrable de valeurs.
À retenir

Lorsque l'on parlera de :

  • variable aléatoire dans le cours, elle sera réelle et simple.
  • variable aléatoire discrète, elle sera de plus réelle.

Les variables aléatoires discrètes s'écrivent trivialement comme une somme d'indicatrices :

Définition

La fonction $\mathbb{1}_{A}$ est appelée indicatrice, fonction indicatrice ou encore fonction caractéristique et est définie telle que :

$$ \mathbb{1}_{A}(x) = \begin{cases} 1 & \text{si } x \in A\\ 0 & \text{sinon} \end{cases} $$

Proposition

Soit $X$ une variable aléatoire discrète de valeurs $(x_i)$ ($i \in \mathbb{N}$). On peut l'écrire sous la forme :

$$ X = \sum\limits_i x_i \mathbb{1}_{\{X = x_i\}} $$

Réciproquement, si $(A_i)$ est un système complet d'évènements d'un espace probabilisé $(\Omega, \mathbb{P})$, et $(x_i)$ une suite dénombrable de réels (pas forcément distincts) alors la fonction :

$$ X = \sum\limits_i x_i \mathbb{1}_{A_i} $$

est une variable aléatoire discrète.

Nos notations permettent d'étendre les définitions des évènements aux variables aléatoires.

Conditionnement

Définition

Pour deux expressions $A$ et $B$ on définit le conditionnement comme étant :

$$ {\Pr}[A \,\vert\, B] \coloneqq \frac{\Pr[A\, , \, B]}{\Pr[B]} $$

Uniformité et Indépendance

Définition

Une variable aléatoire est dite uniforme si $\Pr[X = x]$ est une constante pour tout $x \in U$. On la notera $u \xleftarrow{U} \mathcal{U}$.

Définition

Deux variables aléatoires $X : \Omega \rightarrow \mathcal{U}$ et $Y : \Omega \rightarrow \mathcal{U}'$ sur le même espace probabilisé sont indépendantes si les évènements qui les dirigent sont eux-mêmes indépendants, c'est-à-dire que $\mathbb{P}(X^{-1}(U) \cap Y^{-1}(V)) = \mathbb{P}(X^{-1}(U)) \cdot \mathbb{P}(Y^{-1}(V))$ quels que soient $U \subseteq \mathcal{U}$ et $V \subseteq \mathcal{U}'$.

Comme on a rarement accès à l'espace probabilisé sous-jacent, ce qui va nous intéresser lorsque deux variables aléatoires sont indépendantes c'est la conséquence suivante (triviale) :

Proposition

Pour deux variables aléatoires indépendantes $X$ et $Y$ prenant leurs valeurs dans $\mathcal{U}$ et $\mathcal{U}'$ respectivement, on a quels que soient $U \subseteq \mathcal{U}$ et $V \subseteq \mathcal{U}'$ :

$$ \Pr[X \in U, Y \in V] = \Pr[X \in U] \cdot \Pr[Y \in V] $$

Espérance

La notion d'espérance en probabilité généralise la notion de moyenne.

Définition

Soit $X$ $X : \Omega \rightarrow \mathbb{R}$ une variable aléatoire simple sur l'espace probabilisé $(\Omega, \mathbb{P})$. L'espérance de $X$ est définie telle que :

$$ \mathbb{E}[X] \coloneqq \sum\limits_{\omega \in \Omega}X(\omega)\mathbb{P}(\{\omega\}) $$

L'ensemble $\Omega$ étant (presque) tout le temps inconnu, on utilise plutôt la formule suivante, clairement équivalente à la définition, pour calculer l'espérance d'une variable aléatoire réelle simple :

Proposition

Soit $X$ une variable aléatoire réelle simple de valeurs $x_i$ ($1\leq i \leq p$). Son espérance vaut :

$$ \mathbb{E}[X] = \sum\limits_{i=1}^px_i\cdot \Pr[X=x_i] $$

Cette proposition se généralise mutatis mutandis aux variables aléatoires discrètes si la somme converge et permet de donner une définition de l'espérance pour celle ci :

Définition

Soit $X$ une variable aléatoire discrète de valeurs $(x_i)$ ($i \in \mathbb{N}$).

Si $\sum\limits_{i=0}^{+\infty} x_i\cdot \Pr[X=x_i]$ est définie, on l'appelle espérance de $X$ et on la note $\mathbb{E}[X]$.

Une conséquence immédiate, qui généralise un résultat similaire pour la moyenne, mais que l'on utilise souvent lorsque l'on fait des preuves par la méthode probabiliste est :

Proposition

Pour toute variable aléatoire $X$ (réelle et simple), si $\mathbb{E}[X] = M$, alors il existe une valeur de $X$ plus grande ou égale à $M$.

preuve

Si toutes les valeurs de $X$ étaient strictement plus petites que $M$, on aurait :

$$ \mathbb{E}[X] = \sum\limits_{i=1}^px_i\cdot \Pr[X=x_i] < \sum\limits_{i=1}^pM\cdot \Pr[X=x_i] = M \cdot \sum\limits_{i=1}^p \Pr[X=x_i] = M $$

ce qui est impossible.

Partitionnement de l'espace

Les deux propositions suivantes sont très utilisées :

Proposition

Soit $X$ une variable aléatoire (discrète admettant une espérance) que l'on écrit sous la forme $X = \sum_i a_i\mathbb{1}_{A_i}$ (les $a_i$ ne sont pas forcément distincts) où $(A_i)$ est une partition (système complet d'évènements) de $\Omega$. Alors :

$$ \mathbb{E}[X] = \sum\limits_{i} (a_i\cdot \mathbb{P}(A_i)) $$

preuve

Si la partition $(A_i)$ est finie ou dénombrable on peut rassembler ceux qui ont même valeur pour former une partition $(A'_i)$ où toutes les valeurs sont distinctes.

Une variation de la proposition précédente pour des variables aléatoires prenant des valeurs entières, très utilisée en pratique :

Proposition

Soit $X$ une variable aléatoire (discrète admettant une espérance) prenant ses valeurs dans $\mathbb{N}$. On a :

$$ \mathbb{E}[X] = \sum\limits_{i \geq 0} i \cdot \Pr[X = i] = \sum\limits_{i \geq 1}\Pr[X \geq i] $$

preuve

La première égalité est claire puisque les $X^{-1}(\{ i \})$ forment une partition de $\Omega$. Pour la seconde, on remarque que $i \cdot \Pr[X = i] = \sum_{1 \leq k \leq i} \Pr[X = i]$, et on échange les sommes :

$$ \sum_{i \geq 0} \sum_{1 \leq k \leq i} \Pr[X = i] = \sum_{k \geq 1} \sum_{i \geq k} \Pr[X = i] = \sum_{k \geq 1}\Pr[X \geq k] $$

Linéarité de l'espérance

Sûrement la plus utilisée des propriétés de l'espérance. On ne démontrera ici que le cas qui nous est utile, à savoir pour les variables aléatoires simples, mais il se généralise au cas discret moyennant quelques résultats de convergence de séries infinies que nous ne verrons pas dans ce cours.

Proposition

Soient $X$ et $Y$ deux variables aléatoires. On a :

$$ \mathbb{E}[\alpha \cdot X + \beta\cdot Y] = \alpha \cdot \mathbb{E}[X] +\beta \cdot \mathbb{E}[Y] $$

preuve

On note $X$ et $Y$ avec leurs fonctions indicatrices :

  • $X = \sum\limits_i x_i \mathbb{1}_{\{X = x_i\}}$
  • $Y = \sum\limits_j y_j \mathbb{1}_{\{Y = y_j\}}$

On a alors que la variable aléatoire :

$$ \alpha \cdot X = \sum\limits_i (\alpha\cdot x_i) \mathbb{1}_{\{X = x_i\}} $$

est telle que :

$$ \mathbb{E}[\alpha \cdot X] = \alpha \cdot \mathbb{E}[X] $$

Il nous reste à montrer que pour deux variables aléatoires $X$ et $Y$ telles que :

  • $X = \sum\limits_i x_i \mathbb{1}_{\{X = x_i\}}$
  • $Y = \sum\limits_j y_j \mathbb{1}_{\{Y = y_j\}}$

On a bien $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$ pour conclure.

Pour cela on considère la variable aléatoire $X+Y = \sum\limits_{i, j} (x_i + y_j) \mathbb{1}_{\{X = x_i\} \cap \{Y = y_j\}}$. C'est bien une variable aléatoire puisque les $\{X = x_i\} \cap \{Y = y_j\}$ forment une partition de l'univers. Les $x_i + y_j$ ne sont pas forcément distincts mais on a vu juste avant que ce n'est pas grave.

On peut alors calculer son espérance :

$$ \begin{array}{lcl} \mathbb{E}[X+Y] &=& \sum_{i, j}(x_i + y_j) \Pr[X = x_i, Y=y_j]\\ &=& \sum_{i}\sum_{j}(x_i + y_j) \Pr[X = x_i, Y=y_j]\\ &=& \sum_{i}(x_i \cdot (\sum_{j}\Pr[X = x_i, Y=y_j])) + \sum_{j}(y_j \cdot (\sum_{i}\Pr[X = x_i, Y=y_j]))\\ &=& \sum_{i}(x_i \cdot \Pr[X = x_i]) + \sum_{j}(y_j \cdot \Pr[Y=y_j])\\ &=& \mathbb{E}[X] + \mathbb{E}[Y]\\ \end{array} $$