Probabilités discrètes

Comme toujours, l'infini n'existe pas en vrai. Toutes nos probabilités seront sur des univers finis.

• univers : $\mathrm{\Omega }$ un ensemble fini.
• probabilité : $P:\mathrm{\Omega }\to [0,1]$ tel que $\sum _{x\in \mathrm{\Omega }}P(x)=1$.

La probabilité $P$ est uniforme si $P(x)=\frac{1}{|\mathrm{\Omega }|}$ pour tout $x\in \mathrm{\Omega }$. Par défaut, toutes les probabilités seront uniforme.

Un évènement $A\subseteq \mathrm{\Omega }$ est de probabilité $P{r}_P[A]=\sum _{x\in A}P(x)$. On a :

• $P{r}_P[U]=1$
• $P{r}_P[U\mathrm{\setminus }A]=1-P{r}_P[A]$
• $P{r}_P[A\cup B]=P{r}_P[A]+P{r}_P[B]-\cdot P{r}_P[A\cap B]$
• $A$ et $B$ sont indépendants si $P{r}_P[A\cap B]=P{r}_P[A]\cdot Pr[B]$

On omettra la probabilité $P$ et écrira $Pr[A]$ à la place de $P{r}_P[A]$ s'il n'y a pas d’ambiguïté.

Les événements se manifestent via des variable aléatoire $X$, définies telle que : $X:\mathrm{\Omega }\to U$ ($U$ quelconque a priori). On note alors :

• $Pr[X=x]=Pr[X^{-1}(v)]$
• $Pr[X\in V]=Pr[X^{-1}(V)]$ avec $V\subseteq U$

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

Deux variables aléatoires $X:\mathrm{\Omega }\to U$ et $Y:\mathrm{\Omega }\to U^{\prime }$ sont indépendantes si les évènements qui les dirigent sont eux mêmes indépendants : $Pr[X\in V,Y\in V^{\prime }]=Pr[X\in V]\cdot Pr[Y\in V^{\prime }]$.

En sécurité, on aura typiquement :

• $\mathrm{\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 : $\mathrm{\Omega }=\{0,1{\}}^L\times \{0,1{\}}^L$ et correspond aux deux mots
• probabilité uniforme
• les variables aléatoires :
  • $M_0:\mathrm{\Omega }\to \{0,1{\}}^L$
  • $M_1:\mathrm{\Omega }\to \{0,1{\}}^L$

TBD : deux trucs qui bougent avec le "sachant B"