Aléatoire : une Introduction aux Probabilités (semaine 1)

J'ai créé ce « notebook » avec iPython Notebook, un système gratuit (et « libre ») qui peut faire des calculs symboliques, créer des graphiques, afficher des expressions mathématiques avec $\LaTeX$ et faire beaucoup d'autres choses utiles.

On commence par configurer plusieurs bibliothèques qu'on va utiliser bientôt.

In [1]:
from sympy.interactive import printing
printing.init_printing()
import sympy as sym
from sympy.mpmath import limit, inf
from sympy import Rational as frac
%pylab inline --no-import-all
Populating the interactive namespace from numpy and matplotlib

Exercice 1 : Le « paradoxe » du chevalier de Méré

$$\begin{aligned} \Omega_1 & = \{1,2,3,4,5,6\}^4 \\ \mathbb{P}_1(\omega_i) & = \left(\frac{1}{6}\right)^4 \\ \mathbb{P}_1(A_1) & = 1-\left(\frac{5}{6}\right)^4 \end{aligned}$$

On calcule la probabilité de $A_1^C$, la probabilité qu'aucun 6 apparaît dans 4 lancers d'un dé à 6 faces, est on utilise ça pour calculer $\mathbb{P}(A_1) = 1-\mathbb{P}(A_1^C)$.

In [2]:
1-frac(5,6)**4
Out[2]:
$$\frac{671}{1296}$$
In [3]:
1-(5.0/6)**4
Out[3]:
$$0.51774691358$$
$$\begin{aligned} \Omega_2 & = (\{1,2,3,4,5,6\} \times \{1,2,3,4,5,6\})^{24} \\ \mathbb{P}_2(\omega_i) & = \left(\frac{1}{36}\right)^{24} \\ \mathbb{P}_2(A_2) &= 1 - \left(\frac{35}{36}\right)^{24} \end{aligned}$$
In [4]:
1-frac(35,36)**24
Out[4]:
$$\frac{11033126465283976852912127963392284191}{22452257707354557240087211123792674816}$$
In [5]:
1-(35.0/36)**24
Out[5]:
$$0.491403876131$$

On peut voir que $\mathbb{P}_1(A_1)$ est superieur à $\mathbb{P}_2(A_2)$, mais par une petite quantité.

In [6]:
def p_a(n):
    denom = 6**n
    num = denom - 1
    return 1 - (num/denom)**(2*denom/3)

x = np.linspace(1,6)
plt.plot(x, p_a(x))
None

La limite de $\mathbb{P}_n(A_n)$ lorsque $n$ tend vers l'infini a l'air d'être un peu moins que 0.49.

$$\begin{aligned} \lim_{n \to \infty} \left[ 1 - \left(\frac{6^n-1}{6^n}\right)^{\frac{2}{3} n} \right] \end{aligned}$$
In [7]:
limit(p_a, inf)
Out[7]:
mpf('0.48658288096740798')

Exercice 2 : Jeu du Blackjack

$$ \Omega = \{ 2,3,4,5,6,7,8,9,10, \text{valet }(10), \text{dame }(10), \text{roi }(10), \text{as }(1\text{ ou }11) \} \times \{ \heartsuit, \diamondsuit, \clubsuit, \spadesuit \} $$

On pioche deux cartes, sans replacement. On a trois cas : Deux as, un as et une autre carte, et deux non-as.

$$\begin{aligned} \mathbb{P}(\text{deux as}) &= \frac{4}{52}\frac{3}{51}\\ \mathbb{P}(\text{as et un non-as}) &= \frac{4}{52}\frac{48}{51} + \frac{48}{52}\frac{4}{51} = 2\left(\frac{4}{52}\frac{48}{51}\right)\\ \mathbb{P}(\text{deux non-as}) &= \frac{48}{52}\frac{47}{51} \end{aligned}$$

Si on pioche deux as, $\mathbb{P}(\text{blackjack} | \text{deux as}) = 0$, car $1+1=2$, $1+11=12$ et $11+11=22$. Si on pioche un as, l'autre carte doit avoir une valeur de 10, et donc $\mathbb{P}(\text{blackjack} | \text{un as et un non-as}) = \frac{4}{12} = \frac{1}{3}$. Et sans au moins un as, on ne peut pas ganger, donc on a $\mathbb{P}(\text{blackjack} | \text{deux non-as}) = 0$.

$$\begin{aligned} \mathbb{P}(\text{blackjack}) = 0 + \frac{2}{3}\left(\frac{4}{52}\frac{48}{51}\right) + 0 \end{aligned}$$
In [8]:
frac(2,3)*frac(4,52)*frac(48,51)
Out[8]:
$$\frac{32}{663}$$

Si le joueur a une dame de $\spadesuit$ et un 5 de $\clubsuit$, il faut qu'il reçoive une carte avec une valeur de 1, 2, 3, 4, 5, 6 ou 7 pour ne pas perdre. Il reste $4 \cdot 7 - 1 = 27$ cartes sur 50 avec la valeur necessaire, et donc il a 27 chances sur 50 de ne pas perdre.

Exercice 3 : La formule d’inclusion-exclusion

On veut démontrer que :

$$ \mathbb{P}(\cup_{m=1}^{n} A_m) = \sum_{k=1}^n (-1)^{k+1} p_k $$

ou

$$ p_k = \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}). $$

Quand $n$ est égal à 1, on a

$$\begin{aligned} \mathbb{P}(A_1) &= (-1)^2 \mathbb{P}(A_1) \\ &= \mathbb{P}(A_1). \end{aligned}$$

Quand $n$ est égal à 2, on a

$$\begin{aligned} \mathbb{P}(A_1 \cup A_2) &= (-1)^2 (\mathbb{P}(A_1) + \mathbb{P}(A_2)) + (-1)^3(\mathbb{P}(A_1 \cap A_2)) \\ &= \mathbb{P}(A_1) + \mathbb{P}(A_2) - \mathbb{P}(A_1 \cap A_2). \end{aligned}$$

Quand on ajoute $\mathbb{P}(A_1)$ à $\mathbb{P}(A_2)$, on compte $\mathbb{P}(A_1 \cap A_2)$ deux fois, et il faut donc le soustraire.

Soit $B$ égal à $\cup_{m=1}^{n} A_m$. On peut voir que

$$\begin{aligned} \mathbb{P}(B \cup A_{n+1}) &= \mathbb{P}(B) + \mathbb{P}(A_{n+1}) - \mathbb{P}(B \cap A_{n+1}) \\ &= \mathbb{P}(B) + \mathbb{P}(A_{n+1}) - \mathbb{P}(\cup_{m=1}^{n} (A_m \cap A_{n+1})) \\ &= \left[\sum_{k=1}^n (-1)^{k+1} p_k\right] + \mathbb{P}(A_{n+1}) - \left[\sum_{k=1}^n (-1)^{k+1} q_k\right] \end{aligned}$$

ou

$$\begin{aligned} p_k &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}) & \text{et}\\ q_k &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k} \cap A_{n+1}). \end{aligned}$$

Et maintenant, on peut voir la correspondance entre nos deux sommations :

$$\begin{aligned} \mathbb{P}(B \cup A_{n+1}) &= p_1 + \left[\sum_{k=2}^{n} (-1)^{k+1} p_{k}\right] + \mathbb{P}(A_{n+1}) - \left[\sum_{k=1}^{n-1} (-1)^{k+1} q_k\right] - (-1)^{n+1} q_n \\ &= p_1 + \mathbb{P}(A_{n+1}) + \left[\sum_{k=2}^{n} (-1)^{k+1} p_{k}\right] - \left[\sum_{k=2}^{n} (-1)^{k} q_{k-1}\right] - (-1)^{n+1} q_n \\ &= p_1 + \mathbb{P}(A_{n+1}) + \left[\sum_{k=2}^{n} (-1)^{k+1} p_{k}\right] + \left[\sum_{k=2}^{n} (-1)^{k+1} q_{k-1}\right] - (-1)^{n+1} q_n \\ &= \left[\sum_{i=1}^n \mathbb{P}(A_i)\right]- \left[\sum_{k=2}^{n} (-1)^{k+1} (p_{k} + q_{k-1})\right] - (-1)^{n+1} \mathbb{P}(A_{1} \cap \cdots \cap A_{n+1}). \end{aligned}$$

Soit

$$\begin{aligned} r_k &= p_k + q_{k-1} \\ &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}) + \sum_{1 \leq i_1 \lt \cdots \lt i_{k-1} \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_{k-1}} \cap A_{n+1}) \\ &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq {n+1}} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}). \end{aligned}$$

Cela nous donne

$$\begin{aligned} \mathbb{P}(\cup_{m=1}^{n+1} A_m) &= r_1 - \left[\sum_{k=2}^n (-1)^{k+1} r_k\right] - (-1)^{n+1} r_{n+1} \\ &= (-1)^{1+1} r_1 - \left[\sum_{k=2}^n (-1)^{k+1} r_k\right] + (-1)^{(n+1)+1} r_{n+1} \\ &= \sum_{k=1}^{n+1} (-1)^{k+1} r_k, \end{aligned}$$

et on peut faire l'induction.

Exercice 4 : Distribution aléatoire du courrier

On va commencer avec un peu d'exploration, et trouver les valeurs correctes pour plusieurs $n$.

In [9]:
from itertools import permutations

# Les lettres et les boîtes ont les indices 0, 1, 2, etc.
# Une lettre est dans boîte correcte quand les deux ont
# la même indice.
def au_moins_une_lettre_correcte(lst):
    for ind, val in enumerate(lst):
        if ind == val:
            return True
    return False

# Quand il y a N boîtes, quelle fraction des distributions sont correctes?
def compter_distributions(n):
    distributions = list(permutations(range(0,n)))
    correctes = [d for d in distributions if au_moins_une_lettre_correcte(d)]
    return [len(correctes), len(distributions)]

map(compter_distributions, [1,2,3,4,5,6])
Out[9]:
$$\begin{bmatrix}\begin{bmatrix}1, & 1\end{bmatrix}, & \begin{bmatrix}1, & 2\end{bmatrix}, & \begin{bmatrix}4, & 6\end{bmatrix}, & \begin{bmatrix}15, & 24\end{bmatrix}, & \begin{bmatrix}76, & 120\end{bmatrix}, & \begin{bmatrix}455, & 720\end{bmatrix}\end{bmatrix}$$

Hélas, il n'y a pas de motif simple ici.

In [10]:
list(permutations(range(0,2)))
Out[10]:
$$\begin{bmatrix}\begin{pmatrix}0, & 1\end{pmatrix}, & \begin{pmatrix}1, & 0\end{pmatrix}\end{bmatrix}$$
In [11]:
list(permutations(range(0,3)))
Out[11]:
$$\begin{bmatrix}\begin{pmatrix}0, & 1, & 2\end{pmatrix}, & \begin{pmatrix}0, & 2, & 1\end{pmatrix}, & \begin{pmatrix}1, & 0, & 2\end{pmatrix}, & \begin{pmatrix}1, & 2, & 0\end{pmatrix}, & \begin{pmatrix}2, & 0, & 1\end{pmatrix}, & \begin{pmatrix}2, & 1, & 0\end{pmatrix}\end{bmatrix}$$
In [12]:
list(permutations(range(0,4)))
Out[12]:
$$\begin{bmatrix}\begin{pmatrix}0, & 1, & 2, & 3\end{pmatrix}, & \begin{pmatrix}0, & 1, & 3, & 2\end{pmatrix}, & \begin{pmatrix}0, & 2, & 1, & 3\end{pmatrix}, & \begin{pmatrix}0, & 2, & 3, & 1\end{pmatrix}, & \begin{pmatrix}0, & 3, & 1, & 2\end{pmatrix}, & \begin{pmatrix}0, & 3, & 2, & 1\end{pmatrix}, & \begin{pmatrix}1, & 0, & 2, & 3\end{pmatrix}, & \begin{pmatrix}1, & 0, & 3, & 2\end{pmatrix}, & \begin{pmatrix}1, & 2, & 0, & 3\end{pmatrix}, & \begin{pmatrix}1, & 2, & 3, & 0\end{pmatrix}, & \begin{pmatrix}1, & 3, & 0, & 2\end{pmatrix}, & \begin{pmatrix}1, & 3, & 2, & 0\end{pmatrix}, & \begin{pmatrix}2, & 0, & 1, & 3\end{pmatrix}, & \begin{pmatrix}2, & 0, & 3, & 1\end{pmatrix}, & \begin{pmatrix}2, & 1, & 0, & 3\end{pmatrix}, & \begin{pmatrix}2, & 1, & 3, & 0\end{pmatrix}, & \begin{pmatrix}2, & 3, & 0, & 1\end{pmatrix}, & \begin{pmatrix}2, & 3, & 1, & 0\end{pmatrix}, & \begin{pmatrix}3, & 0, & 1, & 2\end{pmatrix}, & \begin{pmatrix}3, & 0, & 2, & 1\end{pmatrix}, & \begin{pmatrix}3, & 1, & 0, & 2\end{pmatrix}, & \begin{pmatrix}3, & 1, & 2, & 0\end{pmatrix}, & \begin{pmatrix}3, & 2, & 0, & 1\end{pmatrix}, & \begin{pmatrix}3, & 2, & 1, & 0\end{pmatrix}\end{bmatrix}$$

Essayons les cycles de permutations:

(1)(2)

(1)(23)
(2)(13)
(3)(12)
(1)(2)(3)

(1)(234)
(1)(243)
(2)(134)
(2)(143)
(3)(124)
(3)(142)
(4)(123)
(4)(132)
(1)(2)(34)
(1)(3)(24)
(1)(4)(23)
(2)(3)(14)
(2)(4)(13)
(3)(4)(12)
(1)(2)(3)(4)

Il faut compter les permutations avec les points fixes. Mais j'ai perdu plusieurs heures sans trouver la solution avant d'aller en ligne. Apparament, on peux utiliser la formule d’inclusion-exclusion du troisième exercice pour cette tâche. Je recommence à partir de ça.

$$\begin{aligned} \Omega &= \text{ permutations de }n\text{ objets} \\ |\Omega| &= n! \\ \sigma(i) &= \text{ la lettre qui est déposée dans boîte }i \\ A_i &= \text{ les permutations ou }\sigma(i) = i \\ \mathbb{P}(\cup_{m=1}^n A_m) &= \sum_{k=1}^n (-1)^{k+1} p_k \\ p_k &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}) \\ &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \frac{(n-k)!}{|\Omega|} \\ &= {n \choose k} \frac{(n-k)!}{n!} \\ &= \frac{n!}{(n-k)!k!} \cdot \frac{(n-k)!}{n!} \\ &= \frac{1}{k!} \\ \mathbb{P}(\cup_{m=1}^n A_m) &= \sum_{k=1}^n (-1)^{k+1} \frac{1}{k!} \\ \mathbb{P}(\cup_{m=1}^4 A_m) &= \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} \\ \end{aligned}$$

Verfication

On veut voir 4, 15, 76, 455, comme on a trouver avec le code source ci-dessus.

In [13]:
(frac(1,1) - frac(1,2) + frac(1,6) - frac(1,24)) * 24
Out[13]:
$$15$$
In [14]:
from sympy import binomial as bn, factorial as fact

def probabilite_au_moins_une_correcte(n):
  somme = 0
  for k in range(1,n+1):
    somme += (-1)**(k+1) * frac(1, fact(k))
  return somme

[fact(i) * probabilite_au_moins_une_correcte(i) for i in range(1,7)]
Out[14]:
$$\begin{bmatrix}1, & 1, & 4, & 15, & 76, & 455\end{bmatrix}$$

Le voilà !

Réponses

La probabilité d'une distribution correcte est $\frac{1}{n!}$. La probabilité qu'au moins une lettre parvienne au bon destinataire est donnée par $\mathbb{P}(\cup_{m=1}^n A_m)$ ci-dessus. La probabilité qu'aucune lettre n'arrive au bon destinataire est $1-\mathbb{P}(\cup_{m=1}^n A_m)$. Et $d_n$ est égal à $n!(1-\mathbb{P}(\cup_{m=1}^n A_m))$.

In [14]: