A születésnap paradoxon

Utolsó frissités: 2016.október.21

A születésnap paradoxon egy érdekes paradoxon a szó hétköznapi értelmében. Matematikai értelemben nem paradoxon, azért nevezik paradoxonnak, mert ellent mond a „józan észnek”.

Annak a valószínűsége, hogy egy csoportban két ember ugyan azon a napon született, a csoport nagyságának a függvényében A kép forrása: Wikipédia
Annak a valószínűsége, hogy egy csoportban két ember ugyan azon a napon született, a csoport nagyságának a függvényében A kép forrása: Wikipédia

A születésnap paradoxon azt mondja ki, hogy (bizonyos fontos elhanyagolásokkal) igaz, hogy amennyiben egy teremben 23 személy tartózkodik legalább kettő ugyan azon a napon tartja a születésnapját több, mint 50%.  60 személy estén ez a valószínűség már 99% felett van.

Ez az állítás azért megdöbbentő, mert egy év 365 és 1/4 napból áll, és a 24 ennek a számnak kevesebb mint 10%-a, és mégis 50% a valószínűsége, hogy két ember ugyan azon a napon született.

Játszunk egy kicsit a számokkal:

Tettünk néhány egyszerűsítést az egyszerűbb számítás érdekében:

  • Az egy évet tekintsük 365 naposnak (tekintsünk el a szökőévektől)
  • Tekintsünk el a születések számának éven belüli hullámzásától, tételezzük fel, hogy, az év bármely napján ugyan annyi ember születik.
  • Tekintsünk el attól, hogy a vizsgált személyek között ikrek is lehetnek

 

Azt józan ésszel is könnyű belátni, hogy ha az év egyes időszakaiban több ember születik (az eloszlás nem egyenletes), a várt esemény valószínűsége megnő.

Ezt a jelenséget használják ki az úgynevezett „születésnapi támadás” esetén. Ilyenkor a támadó figyeli a megtámadott titkosított adatforgalmat, esetleg valamilyen módszerrel még az adatforgalmat forszírozza is. Megpróbál annyi adatforgalmat összegyűjteni, amely már nagy valószínűséggel tartalmaz azonos tartalmú titkosított blokkokat.

Most elővezethetném a levezetést, hogy egy kulccsal legfeljebb hány blokknyi adatot lehet titkosítani, azonban ezt hagyjuk meg a titkosítási rendszerek tervezőinek.

Szuperhatékony módszerek

Az a tény, hogy ha egy helyiségben 60 személy tartózkodik már 99% a valószínűsége, hogy ketten ugyan azon a napon ünneplik a születésnapjukat a szuperhatékony módszerek demonstrálására alkalmas.

Ha szükségünk van egy olyan csoportra, ahol két ember egy napon ünnepli a születésnapját (tételezzük fel, hogy ezt csak a helyszínen tudjuk ellenőrizni), akkor 166 (365+1) embert kell meghívnunk. Amennyiben megelégszünk a 99%-os valószínűséggel elég csak 60-at.

Ez bizonyos esetekben nagyon komoly megtakarításokat eredményezhet.

Kapcsolódó cikkek