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 :

$$ \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}(\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 :

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

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

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 :

$$ u \xleftarrow{\mathbb{P}} \mathcal{U} $$

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

$$ {\Pr}_{u \xleftarrow{\mathbb{P}} \mathcal{U}}[u = x] \coloneqq \mathbb{P}\{(u \xleftarrow{\mathbb{P}} \mathcal{U})^{-1}(x)\} $$

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}'$ :

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

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.