07 · Lois discrètes usuelles¶
Intuition
Quelques situations reviennent sans cesse, et chacune a sa loi.
- Une seule épreuve, succès ou échec → Bernoulli.
- \(n\) épreuves indépendantes, on compte les succès → binomiale.
- On répète jusqu'au premier succès → géométrique.
- Tirage sans remise dans une urne → hypergéométrique.
- Événements rares sur une longue période → Poisson.
Reconnaître la loi, c'est éviter tout calcul : espérance, variance et formules sont tabulées. Le vrai travail est la reconnaissance, pas le calcul.
1. Loi uniforme¶
\(X\) suit la loi uniforme sur \(\{1,\dots,n\}\) si \(P(X=k)=\frac1n\).
Exemple : le résultat d'un dé équilibré. \(\mathbb{E}=3{,}5\), \(\operatorname{V}=\frac{35}{12}\) ✓
2. Loi de Bernoulli¶
\(X\sim\mathcal{B}(p)\) prend la valeur 1 (« succès ») avec probabilité \(p\) et 0 avec probabilité \(1-p\).
Démonstration de la variance : \(\mathbb{E}[X^2] = 1^2\cdot p = p\), donc \(\operatorname{V} = p-p^2 = p(1-p)\).
La variance est maximale en \(p=\frac12\)
\(p(1-p)\) atteint son maximum \(\frac14\) en \(p=\frac12\) : c'est l'épreuve la plus imprévisible. Aux extrêmes (\(p\to0\) ou \(p\to1\)), la variance tend vers 0 : le résultat devient certain.
C'est aussi l'indicatrice d'un événement de probabilité \(p\) — l'outil du chapitre précédent.
3. Loi binomiale¶
Définition
\(X\sim\mathcal{B}(n,p)\) compte le nombre de succès dans \(n\) épreuves de Bernoulli identiques et indépendantes.
Les trois conditions à vérifier :
- nombre d'épreuves fixé à l'avance ;
- épreuves indépendantes ;
- probabilité de succès constante.
Sans remise, ce n'est PAS une binomiale
Un tirage sans remise viole la condition 3 : la proportion change à chaque tirage. La loi correcte est l'hypergéométrique (§5).
Espérance et variance, par la linéarité. \(X = \sum_{i=1}^n X_i\) avec \(X_i\sim\mathcal{B}(p)\) indépendantes :
(La seconde utilise l'indépendance ; la première non.)
Contrôle : \(\sum_k P(X=k) = (p+(1-p))^n = 1\) par le binôme de Newton ✓
4. Loi géométrique¶
Définition
\(X\sim\mathcal{G}(p)\) est le rang du premier succès dans une suite d'épreuves de Bernoulli indépendantes.
Contrôle : \(\sum_{k\geqslant1}(1-p)^{k-1}p = \frac{p}{1-(1-p)} = 1\) ✓ (somme géométrique).
Interprétation de l'espérance : si un événement a une chance sur 6, il faut en moyenne 6 essais. C'est immédiatement mémorisable.
Absence de mémoire
« Sachant qu'on a déjà échoué \(n\) fois, la loi du nombre d'essais restants est la même qu'au début. »
C'est la réfutation mathématique du sophisme du joueur — voir l'exercice 7 du chapitre 04. La loi géométrique est la seule loi discrète sans mémoire.
5. Loi hypergéométrique¶
Définition
Tirage simultané (ou sans remise) de \(n\) objets dans une population de \(N\) dont \(K\) possèdent un caractère. \(X\) compte les objets possédant le caractère.
Comparer avec la binomiale
En posant \(p = \frac KN\) :
- Même espérance : \(np\) dans les deux cas.
- Variance plus petite d'un facteur \(\frac{N-n}{N-1}\), appelé facteur d'exhaustivité.
Ce facteur vaut 1 pour \(n=1\) et 0 pour \(n=N\) (on tire toute la population : aucun aléa). Le tirage sans remise est donc moins dispersé.
Quand approximer par une binomiale
Si \(\frac nN \leqslant 0{,}1\) — on prélève moins de 10 % de la population — le facteur d'exhaustivité dépasse 0,9 et l'approximation binomiale est acceptable.
C'est ce qui justifie de traiter un sondage sur 1000 personnes dans une population de 60 millions comme une binomiale.
6. Loi de Poisson¶
Définition
\(X\sim\mathcal{P}(\lambda)\) avec \(\lambda>0\) :
Contrôle : \(\sum_{k\geqslant0}e^{-\lambda}\frac{\lambda^k}{k!} = e^{-\lambda}e^{\lambda}=1\) ✓ (série exponentielle).
L'égalité espérance = variance
C'est la signature de la loi de Poisson, et un test de diagnostic : si des données de comptage ont une variance très supérieure à leur moyenne, elles ne sont pas poissonniennes (on parle de surdispersion).
Approximation de la binomiale
Si \(n\) est grand, \(p\) petit, et \(np = \lambda\) modéré, alors
Règle usuelle : \(n\geqslant30\), \(p\leqslant0{,}1\), \(np\leqslant10\).
Domaine d'application : événements rares dans un grand nombre d'occasions — pannes, arrivées de clients, désintégrations radioactives, requêtes sur un serveur, fautes de frappe dans un livre.
7. Tableau récapitulatif¶
| Loi | Situation | \(P(X=k)\) | \(\mathbb{E}\) | \(\operatorname{V}\) |
|---|---|---|---|---|
| Uniforme | Tirage équiprobable | \(\frac1n\) | \(\frac{n+1}{2}\) | \(\frac{n^2-1}{12}\) |
| Bernoulli | 1 épreuve | \(p\) ou \(1-p\) | \(p\) | \(p(1-p)\) |
| Binomiale | \(n\) épreuves, avec remise | \(\binom nk p^k q^{n-k}\) | \(np\) | \(npq\) |
| Géométrique | Premier succès | \(q^{k-1}p\) | \(\frac1p\) | \(\frac{q}{p^2}\) |
| Hypergéom. | \(n\) tirages sans remise | \(\frac{\binom Kk\binom{N-K}{n-k}}{\binom Nn}\) | \(n\frac KN\) | \(n\frac KN\frac{N-K}{N}\frac{N-n}{N-1}\) |
| Poisson | Événements rares | \(e^{-\lambda}\frac{\lambda^k}{k!}\) | \(\lambda\) | \(\lambda\) |
(avec \(q=1-p\))
L'arbre de décision
Combien d'epreuves ?
├─ Une seule ......................... Bernoulli
├─ Nombre fixe n
│ ├─ avec remise / independantes ... Binomiale
│ └─ sans remise ................... Hypergeometrique
├─ Jusqu'au premier succes ........... Geometrique
└─ Comptage sur une periode
└─ evenements rares .............. Poisson
Exemples traités¶
Exemple 1 — Binomiale
Un QCM a 20 questions à 4 réponses. Un étudiant répond au hasard.
\(X\sim\mathcal{B}(20\,;0{,}25)\).
Probabilité d'avoir au moins 10 bonnes réponses ?
Environ 1,4 % — le hasard ne suffit pas à obtenir la moyenne.
Exemple 2 — Géométrique
On lance un dé jusqu'à obtenir un 6.
\(X\sim\mathcal{G}\!\left(\frac16\right)\).
L'écart-type presque égal à l'espérance signale une loi très dispersée : il faut « en moyenne 6 lancers », mais il n'est pas rare d'en faire 15.
Exemple 3 — Hypergéométrique vs binomiale
Une urne contient 100 boules dont 30 rouges. On tire 10 boules.
Sans remise (hypergéométrique) :
Avec remise (binomiale) :
Même espérance, variance inférieure de 9 % sans remise. Comme \(\frac{n}{N}=0{,}1\), on est à la limite d'acceptabilité de l'approximation.
Exemple 4 — Poisson
Un standard reçoit en moyenne 3 appels par minute. Probabilité d'en recevoir exactement 5 dans une minute donnée ?
\(X\sim\mathcal{P}(3)\).
Probabilité d'en recevoir au moins un ?
Sur 5 minutes : le paramètre devient \(\lambda = 15\) (proportionnel à la durée). C'est une propriété fondamentale du processus de Poisson.
Erreurs fréquentes¶
| Erreur | Correction |
|---|---|
| Binomiale pour un tirage sans remise | Hypergéométrique |
| Oublier \(\binom nk\) dans la binomiale | Il compte les positions |
| Géométrique commençant à 0 | Ici \(k\geqslant1\) (convention du cours) |
| Poisson avec un mauvais \(\lambda\) | \(\lambda\) est proportionnel à la durée |
| \(\operatorname{V} = np\) pour la binomiale | C'est \(np(1-p)\) |
| Approximer une hypergéométrique avec \(n/N\) grand | Vérifier \(n/N \leqslant 0{,}1\) |
Exercices¶
★ Exercice 1. Identifier la loi et donner ses paramètres.
a) Nombre de piles en 10 lancers d'une pièce équilibrée b) Nombre de lancers de dé jusqu'au premier 1 c) Nombre de rois dans une main de 5 cartes sur 32 d) Nombre de coquilles sur une page, sachant qu'il y en a 2 en moyenne
★ Exercice 2. \(X\sim\mathcal{B}(8\,;0{,}3)\). Calculer :
a) \(\mathbb{E}[X]\) et \(\operatorname{V}(X)\) b) \(P(X=2)\) c) \(P(X\leqslant1)\)
★★ Exercice 3. Un joueur de basket réussit 70 % de ses lancers francs.
a) Probabilité qu'il réussisse exactement 7 tirs sur 10. b) Probabilité qu'il en réussisse au moins 8. c) Combien de tirs en moyenne pour son premier échec ?
★★ Exercice 4. \(X\sim\mathcal{P}(4)\). Calculer :
a) \(P(X=0)\), \(P(X=1)\), \(P(X=2)\) b) \(P(X\geqslant3)\) c) \(\mathbb{E}[X]\) et \(\sigma(X)\)
★★ Exercice 5. Une usine produit 1 % de pièces défectueuses. On prélève 200 pièces.
a) Quelle est la loi exacte du nombre de défectueuses ? b) Justifier l'approximation de Poisson et donner \(\lambda\). c) Comparer \(P(X=0)\), \(P(X=2)\) et \(P(X\geqslant4)\) dans les deux modèles.
★★★ Exercice 6. Démontrer que pour \(X\sim\mathcal{G}(p)\) :
a) \(P(X>n) = (1-p)^n\) b) \(P(X>n+k\mid X>n) = P(X>k)\) (absence de mémoire) c) \(\mathbb{E}[X]=\frac1p\) Indication : \(\mathbb{E}[X] = \sum_{n\geqslant0}P(X>n)\).
★★★ Exercice 7. Un serveur reçoit en moyenne 120 requêtes par heure.
a) Loi du nombre de requêtes en 1 minute ? En 10 secondes ? b) Probabilité de recevoir plus de 5 requêtes en une minute. c) Le serveur ne peut traiter que 6 requêtes simultanées. Probabilité de saturation par minute ? d) Sur une journée de 8 heures, combien de minutes de saturation en moyenne ?
★★★ Exercice 8. Démontrer que si \(X\sim\mathcal{B}(n,p)\) avec \(n\to+\infty\), \(p\to0\) et \(np\to\lambda\), alors \(P(X=k)\to e^{-\lambda}\frac{\lambda^k}{k!}\).
Indication : écrivez \(\binom nk p^k(1-p)^{n-k}\) avec \(p=\frac\lambda n\) et passez à la limite terme à terme.
★★★★ Exercice 9. Le collectionneur de coupons. Une marque offre un autocollant au hasard parmi \(n\) modèles à chaque achat. Combien d'achats en moyenne pour la collection complète ?
a) Soit \(T_i\) le nombre d'achats pour passer de \(i-1\) à \(i\) modèles distincts. Quelle est la loi de \(T_i\) ? b) En déduire \(\mathbb{E}[T]\) où \(T = \sum T_i\). c) Montrer que \(\mathbb{E}[T] = n H_n \approx n\ln n\). d) Application : \(n=50\) et \(n=500\).
★★★★ Exercice 10 — lien informatique. Une table de hachage à \(m\) alvéoles reçoit \(n\) clés.
a) Loi du nombre de clés dans une alvéole donnée ? b) Approximation de Poisson : quel \(\lambda\) ? c) Pour \(n=m\), probabilité qu'une alvéole contienne au moins 3 clés ? d) Espérance de la longueur de la plus longue chaîne — on admet qu'elle est en \(\Theta\left(\frac{\ln n}{\ln\ln n}\right)\). Vérifier numériquement pour \(n=10^6\) et commenter le choix de la structure de collision.
Corrigés¶
Corrigé — Exercice 1
a) Binomiale \(\mathcal{B}(10\,;0{,}5)\). b) Géométrique \(\mathcal{G}\!\left(\frac16\right)\). c) Hypergéométrique, \(N=32\), \(K=4\), \(n=5\). d) Poisson \(\mathcal{P}(2)\).
Corrigé — Exercice 2
a) \(\mathbb{E}=8\times0{,}3 = 2{,}4\) ; \(\operatorname{V} = 8\times0{,}3\times0{,}7 = 1{,}68\) ; \(\sigma\approx1{,}296\).
b)
c) \(P(X=0) = 0{,}7^8 \approx 0{,}05765\) ; \(P(X=1) = 8\times0{,}3\times0{,}7^7 \approx 0{,}19765\).
Corrigé — Exercice 3
\(X\sim\mathcal{B}(10\,;0{,}7)\).
a) \(\binom{10}{7}(0{,}7)^7(0{,}3)^3 = 120\times0{,}0823543\times0{,}027 \approx 0{,}2668\).
b)
c) Le premier échec suit une géométrique de paramètre \(p = 0{,}3\) :
Corrigé — Exercice 4
\(e^{-4}\approx0{,}018316\).
a) \(P(X=0) = e^{-4}\approx0{,}0183\) ; \(P(X=1) = 4e^{-4}\approx0{,}0733\) ; \(P(X=2) = 8e^{-4}\approx0{,}1465\).
b) \(P(X\geqslant3) = 1-(0{,}0183+0{,}0733+0{,}1465) = 1-0{,}2381 = 0{,}7619\).
c) \(\mathbb{E}=4\), \(\sigma = 2\).
Corrigé — Exercice 5
a) Binomiale \(\mathcal{B}(200\,;0{,}01)\) — si l'on considère les prélèvements indépendants (production continue).
b) \(n=200\geqslant30\), \(p=0{,}01\leqslant0{,}1\), \(np = 2\leqslant10\) : conditions vérifiées. \(\lambda = 2\).
c) Comparaison.
| Binomiale exacte | Poisson \(\mathcal{P}(2)\) | |
|---|---|---|
| \(P(X=0)\) | \(0{,}99^{200}=0{,}13398\) | \(e^{-2}=0{,}13534\) |
| \(P(X=2)\) | \(0{,}27203\) | \(2e^{-2}=0{,}27067\) |
| \(P(X\geqslant4)\) | \(0{,}14197\) | \(0{,}14288\) |
Écart relatif inférieur à 1,1 % : l'approximation est excellente et dispense de calculer des \(\binom{200}{k}\).
Corrigé — Exercice 6
a) \(X>n\) signifie que les \(n\) premières épreuves sont des échecs :
(Ou par sommation : \(\sum_{k>n}(1-p)^{k-1}p = p\frac{(1-p)^n}{1-(1-p)} = (1-p)^n\).)
b)
\(\blacksquare\)
c) Pour une variable à valeurs dans \(\mathbb{N}^*\) :
\(\blacksquare\)
(La première égalité vient de l'interversion de sommes : \(\sum_k kP(X=k) = \sum_k\sum_{n<k}P(X=k) = \sum_n P(X>n)\).)
Corrigé — Exercice 7
a) 120 requêtes/heure = 2 par minute. En 1 minute : \(\mathcal{P}(2)\). En 10 secondes : \(\lambda = 2\times\frac{10}{60} = \frac13\), soit \(\mathcal{P}\!\left(\frac13\right)\).
b) \(X\sim\mathcal{P}(2)\).
c) Saturation = plus de 6 requêtes :
d) Sur \(8\times60 = 480\) minutes :
La limite du modèle
Ce calcul suppose un débit constant de 2 requêtes par minute. En réalité le trafic est fortement non stationnaire — pics à midi, creux la nuit. Le modèle de Poisson homogène sous-estime donc gravement la saturation aux heures de pointe.
C'est exactement le type de critique que demande le module de modélisation.
Corrigé — Exercice 8
Posons \(p = \frac\lambda n\) et faisons tendre \(n\to+\infty\) à \(k\) fixé.
Limite de \((A)\). C'est un produit de \(k\) facteurs \(\frac{n-j}{n} = 1-\frac jn \to 1\). Donc \((A)\to1\).
Limite de \((B)\). C'est la limite classique \(\left(1+\frac xn\right)^n\to e^{x}\) avec \(x=-\lambda\) : \((B)\to e^{-\lambda}\).
Limite de \((C)\). \(k\) est fixé et \(\frac\lambda n\to0\), donc \((C)\to1\).
Le nom historique
Ce résultat est la loi des petits nombres, démontrée par Poisson en 1837. Il explique pourquoi la loi de Poisson apparaît partout où l'on compte des événements rares parmi un très grand nombre d'occasions.
Corrigé — Exercice 9
a) Supposons qu'on possède déjà \(i-1\) modèles distincts. La probabilité qu'un nouvel achat apporte un modèle nouveau est
Chaque achat est indépendant, donc \(T_i\) suit une loi géométrique de paramètre \(p_i\).
b) \(\mathbb{E}[T_i] = \frac{1}{p_i} = \frac{n}{n-i+1}\).
Par linéarité de l'espérance :
c) Changeons d'indice, \(j = n-i+1\) qui va de \(n\) à 1 :
Et \(H_n\sim\ln n + \gamma\) (chapitre Analyse 09, exercice 8), donc
d) Applications.
| \(n\) | \(H_n\) | \(\mathbb{E}[T] = nH_n\) | \(n\ln n\) |
|---|---|---|---|
| 50 | 4,4992 | 225 | 195,6 |
| 500 | 6,7928 | 3396 | 3107,3 |
Pour 50 autocollants, il faut en acheter 225 en moyenne — quatre fois et demie la collection. Pour 500, il en faut 3396, soit près de sept fois.
Où passe le temps
Le dernier autocollant coûte à lui seul \(\mathbb{E}[T_n] = n\) achats — soit 50 sur 225, plus de 20 % du total. C'est la queue de la collecte qui coûte, pas le début.
C'est le même phénomène en test logiciel : couvrir les 90 premiers pour cent des cas est rapide, les 10 derniers sont interminables.
Corrigé — Exercice 10
a) Chaque clé tombe dans l'alvéole considérée avec probabilité \(\frac1m\), indépendamment. Le nombre de clés suit donc
b) \(n\) grand, \(p=\frac1m\) petit, \(np = \frac nm\) modéré : approximation de Poisson avec
(le facteur de charge de la table).
c) Pour \(n=m\), \(\lambda=1\) :
8 % des alvéoles contiennent au moins 3 clés.
(À rapprocher des 37 % d'alvéoles vides du chapitre 03 : la répartition est très inégale.)
d) Longueur de la plus longue chaîne.
import math
n = 10**6
borne = math.log(n) / math.log(math.log(n))
print(f"ln n = {math.log(n):.3f}")
print(f"ln ln n = {math.log(math.log(n)):.3f}")
print(f"ln n / ln ln n = {borne:.2f}")
Sortie :
ln n = 13.816
ln ln n = 2.626
ln n / ln ln n = 5.26
La plus longue chaîne fait environ 5 à 6 éléments pour un million de clés — et cette valeur croît extrêmement lentement : pour \(10^{12}\) clés, elle vaut environ 8.
Conséquence sur le choix de structure.
- Listes chaînées : parfaitement adaptées. Une recherche dans le pire cas parcourt 6 éléments, ce qui est comparable au coût d'un défaut de cache. C'est le choix de la plupart des implémentations.
- Arbres équilibrés par alvéole : inutiles à cette échelle — un arbre de 6 éléments est plus lent qu'une liste de 6, à cause des indirections.
Java 8 a néanmoins introduit une bascule liste → arbre rouge-noir au-delà de 8 éléments dans une alvéole. La raison n'est pas le comportement moyen calculé ici, mais la protection contre une attaque : un adversaire qui choisit ses clés peut forcer toutes les collisions dans une même alvéole, transformant le \(O(1)\) en \(O(n)\) — une attaque par déni de service.
La leçon
Le calcul probabiliste décrit le cas moyen sur des entrées aléatoires. Il ne dit rien du pire cas adversarial. Les deux analyses sont nécessaires, et confondre l'une avec l'autre a produit des vulnérabilités réelles dans PHP, Python, Java et Ruby entre 2003 et 2012.
Chapitre suivant : Variables aléatoires continues.