QED

In het zomernummer van PC-Active gaat m’n Denkwerk-artikel over de verjaardagsparadox. Dit gaat als volgt: wanneer je dit jaar met 367 mensen in dezelfde ruimte zit, zullen er minstens twee op dezelfde dag jarig zijn. Met hoeveel mensen moeten we zijn zodat de kans op twee dezelfde verjaardagen 50% is? Geen 183 (de helft van het aantal dagen in dit jaar), maar slechts 23. Ik leid de formule voor deze kans hieronder even af, omdat het eigenlijk niet zo moeilijk is. Daarbij veronderstel ik overigens dat we niet in een schrikkeljaar zitten, maar voor een schrikkeljaar gelden ongeveer dezelfde resultaten.

Het is eenvoudiger om te berekenen wat de kans is dat alle N personen verschillend zijn. We bekijken de mogelijkheden voor de eerste persoon: die kan op 365 van de 365 dagen jarig zijn, dus 365/365 = 1. De tweede persoon kan nog op 364 dagen van de 365 jarig zijn, dus 364/365, de derde op 363 van de 365 dagen, enzovoort, tot persoon N die nog op (366 - N) van de 365 dagen mag jarig zijn. De kans dat alle N verjaardagen verschillend zijn, is het product van deze N kansen, dus:

Dit is echter de kans dat alle N verjaardagen verschillend zijn. Om de kans te bekomen dat er minstens twee verjaardagen overeenkomen (dus niet verschillend zijn), moeten we dit aftrekken van 1, en we bekomen:

Als we nu P(N) berekenen voor een aantal N zien we:

N	P(N)
10	11,7%
20	41,1%
23	50,7%
30	70,6%
34	79,5%
40	89,1%
50	97,0%

Met 23 personen hebben we dus iets meer dan 50% kans dat twee van die personen op dezelfde dag jarig zijn. We kunnen dit ook zo proberen te begrijpen: als men in een groep met 23 personen de verjaardag van de eerste persoon met de andere vergelijkt, hebben we slechts 22 kansen dat ze overeenkomen, dus lijkt het of dit veel te weinig is om 50% kans op dezelfde verjaardag te bekomen. Maar het gaat niet om dezelfde verjaardag als één specifiek persoon, maar om dezelfde verjaardag tussen twee willekeurige personen. Als men elk van de 233 personen met elk van de 23 anderen vergelijkt, hebben we niet minder dan 253 kansen! Immers, er zijn 23 x 22 / 2 = 253 verschillende paren.

We kunnen deze kans P(N) ook in een grafiek uitzetten, en dan zien we duidelijk dat de kans op dezelfde verjaardag snel stijgt tot 50%:

Verder bespreek ik in het artikel ook nog het duivenhokprincipe, waarvan de verjaardagsparadox eigenlijk een probabilistische variant is. Ik bespreek ook de kans dat een aantal personen in dezelfde maand jarig zijn of de kans dat een aantal personen verjaren met slechts een week verschil. En tot slot pas ik dit wiskundige fait divers toe in de informatica (PC-Active is nu eenmaal een informaticablad, dus alle wiskunde die ik er binnensmokkel moet ik wel kunnen motiveren met een toepassing in de informatica): enerzijds het concept van UUID’s (128 bits getallen die gebruikt worden om bepaalde informatie uniek te identificeren) en anderzijds de verjaardagsaanval op hash-functies.