# Didier Villers, UMONS - wiki

## Énoncé

• Quelle est la probabilité qu'au moins deux personnes aient leur anniversaire le même jour dans un groupe de 40 personnes ?

## Solution

Il est plus simple de passer par le calcul de la probabilité complémentaire Pcomp(N), que toutes les N personnes présentes aient leur anniversaire des jours différents. Si on considère une personne à la fois, on multipliera les probabilités indépendantes d'“avoir un anniversaire un jour différent des personnes précédentes” :

• Pcomp(1) = 1 = 365/365 (trivial pour une seule personne)
• Pcomp(2) = (365/365) * (364/365) (pour la deuxième personne, seuls 364 jours sur 365 sont adéquats pour avoir des dates différentes)
• Pcomp(3) = pcomp(2) * (363/365) = 1 * (364/365) * (363/365) (pour la troisième personne, seuls 363 jours sur 365 sont adéquats pour avoir des dates différentes)
• Pcomp(N) = (365 * 364 * 363 * … * (365 - N + 1)/ (365)^N = (365)! / ( (365-N)! * (365)^N)

Pour 40 personne, la réponse 1-Pcomp(40) = 0.89123

Remarque : discuter de la non-validité de l'approximation de Stirling utilisée.

## Programme Python

multiples-occurences-anniversaires.py
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
Petit programme destiné à répondre à la question suivante :
- Quelle est la probabilité qu'au moins deux personnes aient leur anniversaire
le même jour dans un groupe de 40 personnes.
Hypothèses : l'année fait 365 jours et les naissances des personnes
se distribuent uniformément (pas de jumeaux,...)
Remarque : la solution doit pouvoir être généralisée !
"""

from math import log, exp

# nombre de possibilités différentes
# (= nombre de jours d'une année dans les exemples)
poss = 365

# nombre d'items (personnes présentes)
n = 40

# solution : p = poss ! / ( (poss-n) !  * poss^n)

pcomp = 1.
for i in range(poss, poss-n, -1):
pcomp = pcomp * i / poss

print("calcul exact : ", pcomp, 1.-pcomp)

# calcul suivant l'approximation de Stirling ( ln(j!) ~= j ln(j) - j
# l'approximation est d'autant plus valable que poss est grand et n << poss
pcomps = exp(poss*log(poss)-poss - (poss-n)*log(poss-n) + (poss-n) - n*log(poss))

print("Approximation de Stirling : ", pcomps, 1.-pcomps)

## Problème analogue

• Quelle est la probabilité de recevoir 40 cartes cadeaux différentes (aucun “double”) sur 216 types différents de cartes distribuées comme jeu-concours aux caisses d'un supermarché
• Si ce genre d'événement se produit fréquemment, que pouvez-vous en conclure ?
• Discuter des stratégies appliquées par les personnes qui organisent ce genre de jeu-concours

• You can think of the birthday paradox by asking the probability of drawing 23 people successively so that each one has a birthday not yet seen. This gives the probability of no collision, so the probability of a collision is 1 minus this. The general formula for the probability of a collision when making k choices from a collection of N possibilities looks like . By using some approximations for the factorials, it so happens that the inflection point where things shift from collisions being very unlikely to instead being likely is around sqrt(N). More specifically, it happens a little above sqrt(N). For example, sqrt(365) = 19.105…, and it's at 23 people that you're more likely to have a birthday collision than not. In the phone numbers example, sqrt(10,000) = 100, and the 50% point happens with 118 people. In the card example, sqrt(52) = 7.2, and it took 9 draws. Specifically, if you have a hash function with N possible outputs (say 2^128), and your system's security depends on collisions never happening, you might initially think an attacker needs around 2^128 brute force attempts, but really it's much *much* smaller: 2^64. 