Probabilités discrètes
Comme on est en informatique, on va considérer des ensembles finis ou au pire dénombrable.
Probabilités
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)$
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
TBD reprendre les propositions de : http://vonbuhren.free.fr/Prepa/TSI2/probabilites_univers_denombrable_cours.pdf
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)$
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.
Définition
Une variable aléatoire $X$ est une fonction $X : \Omega \rightarrow U$ ($U$ quelconque a priori). On note alors :
- $\mathbb{P}\{X = v\} \coloneqq \mathbb{P}(X^{-1}(v))$
- $\mathbb{P}\{X \in V\} \coloneqq \mathbb{P}(X^{-1}(V))$, $V \subseteq \Omega$
Pour bien faire la différence entre les deux notions, on utilisera la notation :
Définition
S'il n'y a pas ambiguïté, on omettra la probabilité $p$ et on écrira $\Pr[X]$ à la place de $\Pr_p[X]$. On peut complètement ignorer l'univers sous-jacent et ne travailler qu'avec les variables aléatoires.
Une variable aléatoire sera dite uniforme si $\Pr[X = x]$ est une constante pour tout $x \in U$. On la notera $X \xleftarrow{R} \mathcal{U}$
Deux variables aléatoires $X : \Omega \rightarrow U$ et $Y : \Omega \rightarrow U'$ sont indépendantes si les évènements qui les dirigent sont eux mêmes indépendants : $\Pr[X \in V, Y \in V'] = \Pr[X \in V] \cdot \Pr[Y \in V']$.
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$
TBD : deux trucs qui bougent avec le "sachant B"
Fonction génératrice
TBD