Probabilités discrètes
Comme on est en informatique, on va considérer des ensembles finis ou au pire dénombrable.
Probabilités
Définitions
Définition
- univers : $\Omega$ un ensemble fini.
- probabilité : $p : \Omega \rightarrow [0, 1]$ telle que $\sum_{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 uniforme.
On étant la notion de probabilité aux ensembles :
Définition
Un évènement $A \subseteq \Omega$ est de probabilité $\mathbb{P}(A)$ définie telle que :
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}(\cup_n A_n) = \sum_n \mathbb{P}(A_n)$
Le couple $(\Omega, \mathbb{P})$ est appelé espace probabilité.
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$.
TBD exemple avec P(n) = 1/(n + 1)^2 et P(0) = 0
On a les propriétés suivantes :
Proposition
On a :
- $\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)$
- $A$ et $B$ sont indépendants si $\mathbb{P}(A \cap B) = \mathbb{P}(A) \cdot \mathbb{P}(B)$
TBD reprendre les propositions de : http://vonbuhren.free.fr/Prepa/TSI2/probabilites_univers_denombrable_cours.pdf
Conditionnement
Définition
Soit $\mathbb{P}$ une probabilité sur $\Omega$. La probabilité de $B$ sachant $A$ est définie (pour $A, B \subseteq \Omega$) telle que :
Cette probabilité décrit le fait que l'on ne considère que les évènements où $A$ est réalisé. C'est bien une probabilité :
Proposition
Soit un univers $(\Omega, P)$ un espace probabilisé.
Pour tout $A \subseteq \Omega$ la fonction $\mathbb{P}_A : \mathcal{P}(\Omega) \rightarrow [0, 1]$.
preuve
preuve
clair.
TBD thm 4.8 et 4.9 de "probabilité pour les non probabilistes
Variables aléatoires
Les événements se manifestent via des variable aléatoire. L'univers étant souvent soit inconnu soit trop compliqué pour en tirer quoi que ce soit d'utile.
TBD : deux trucs qui bougent avec le "sachant B"
Définitions et notations
Définition
Une variable aléatoire $X$ est une fonction $X : \Omega \rightarrow \mathcal{U}$ ($U$ quelconque a priori) où $(\Omega, \mathbb{P})$ est un espace probabilisé. On note alors :
- $\mathbb{P}\{X = u\} \coloneqq \mathbb{P}(X^{-1}(u))$
- $\mathbb{P}\{X \in U\} \coloneqq \mathbb{P}(X^{-1}(U))$, $u \subseteq \mathcal{U}$
On dira que $X(\omega) = u$ est une réalisation de la variable aléatoire $X$. Cette réalisation est de probabilité $\mathbb{P}\{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 utilisera souvent la notation suivante :
Définition
On définit :
Comme étant une variable aléatoire :
- prenant ses valeurs dans $\mathcal{U}$
- suivant la loi de probabilité $\mathbb{P}$
Ce qui nous permet d'écrire de façon synthétique :
Définition
S'il n'y a pas ambiguïté, on se permettra même d'écrire :
- ${\Pr}[u = x]$ si l'on s'intéresse aux réalisations de la variable aléatoire $X$
- ${\Pr}[X = x]$ si l'on veut expliciter la variable aléatoire $X$
Uniformité et Indépendance
Définition
Une variable aléatoire ets 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 $X^{-1}(U) \cap Y^{-1}(U') = \varnothing$ quelques 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 quelques soient $U \subseteq \mathcal{U}$ et $V \subseteq \mathcal{U}'$ :
Espérance
TBD espérance $\mathbb{E}[X]$ (vous verrez aussi $\mathbb{E}(X)$ ou même $\mathbb{E}X$. Nous on utilise les crochet pour rester cohérente avec notre notation pour les probabilités de variables aléatoires)
- linéarité de l'espérance
- il existe 1 qui vaut l'espérance
Exemple
En sécurité, on aura typiquement :
- $\Omega = \{0, 1\}^n$ l'ensemble des clés
- probabilité uniforme
- la variable aléatoire associée est le chiffre : $E(k, m)$
Ou, si l'on s'intéresse à un couple $(m_0, m_1)$ de deux mots de longueurs $L$ :
- l'univers est tout ce qui arrive : $\Omega = \{0, 1\}^L \times \{0, 1\}^L$ et correspond aux deux mots
- probabilité uniforme
- les variables aléatoires :
- $M_0 : \Omega \rightarrow \{0, 1\}^L$
- $M_1 : \Omega \rightarrow \{0, 1\}^L$
Fonction génératrice
TBD utiliser les fct génératrice pour la combinatoire.
Méthode probabiliste
- simple
- avec alteration
- lemme local de Lova
TBD trouver un exemple pas graphe.