The birthday problem.
Le paradoxe de l'anniversaire.

The "birthday problem" was introduced by John Daugman (iris recognition). This is a simple way to explain entropy and probability.

The familiar "birthday problem" asks how large a group of people must be assembled, chosen at random, before it becomes more likely than not that at least one pair of them have the same birthday. Answer is 23.

There exists an analogous "biometric birthday problem:" for a given similarity threshold yielding some specified False Acceptance Rate (FAR) for single comparisons, how many different persons must a database contain before it becomes likelier than not that there is at least one biometric collision?

Since N persons make N(N-1)/2 pairings, a collision becomes likelier than not when (1-FAR) raised to the power N(N-1)/2 is less than 0.5. This occurs once there are just N=23 or more persons with a FAR=1/365, and with 38 persons with a FAR=0.001 (a very undemanding criterion).

Le "problème de l'anniversaire" a été introduit par John Daugman (inventeur de la reconnaissance par iris). C'est une manière simple d'aborder l'entropie et les probabilités.

Le paradoxe de l'anniversaire est simplement celui de savoir combien il faut mettre de personnes ensemble pour avoir une probabilité supérieure à 1/2 d'avoir deux personnes ayant la même date d'anniversaire. La réponse est 23 (oui, aussi faible, d'où le paradoxe).

Il existe le même problème pour la biométrie. Combien de personnes faut-il mettre ensemble pour que deux personnes soient considérées identiques, pour une biométrie présentant un certain taux de fausses acceptations (FAR)?

Dans une cohorte de N personnes, vous avez au total N(N-1)/2 paires de personnes. Si la probabilité d'avoir une correspondance vaut 1/365 (même date d'anniversaire), et bien il faut trouver N pour que (1-1/365) à la puissance (N(N-1)/2) égale 0.5, une chance sur deux que le groupe ait deux personnes qui correspondent, soit ici 23. Pour un FAR=0.001 (1 chance sur 1000 de se tromper), N vaut 38. Autrement dit, en prenant un groupe de 38 personnes, une fois sur 2, une biométrie ayant une chance sur 1000 de confondre 2 personnes en trouvera deux identiques.


FAR
false acceptance rate
Minimum group size to get 2 identical
persons with a probability of
50% 99%
1/365 (birthday) 23 59
1/1000 = 0.1% 38 97
1/10 000 = 0.01% 119 304
1/50 000 = 0.002% (Apple) 264 680
1/100 000 = 10-5 373 961
1/1 000 000 = 10-611783036