Rencontre-ongelma

Rencontre-ongelma eli yhteensattumisongelma on todennäköisyys sille, että kun joukon  alkiot kuvataan joukon  alkioiksi ja joukon  alkiot sekoitetaan satunnaiseen järjestykseen, niin kuvauksessa kaikki joukon  alkiot saavat sekoituksessa jonkun uuden joukon  alkion. Todennäköisyyden arvo riippuu alkioiden lukumäärästä, mutta se on asymptoottisesti vakio .

Käytännön esimerkkinä tästä ovat pikkujoulun lahjapaketit, missä juhlavieraat tuovat lahjasäkkiin lahjapaketin ja ne jaetaan takaisin lahjan tuoneiden kesken umpimähkään. Penconte-ongelmassa päätellään todennäköisyys sille, että "kukaan ei saa omaa lahjaansa takaisin".

Ongelman ratkaisu 

Ratkaisu on johdettavissa käyttäen apuna joukko-opin ja todennäköisyyslaskennan kaavoja.

Olkoon lahjapaketin tuojien lukumäärä . Sovitaan, että tapahtuma  sattuu, jos vieras  saa takaisin oman lahjansa. Kysytty todennäköisyys on siis
.
De Morganin lakien mukaan pätee yhtälö
.
Tämän ja komplementin todennäköisyyden kaavalla saadaan yhtälö
.
Todennäköisyyslaskennan yleinen yhteenlaskukaava on
.
Näin ollen riittää laskea tapahtumien  kaikkien kombinaatioiden leikkausten todennäköisyydet. Koska lahjojen oletetaan jakautuvan symmetrisin todennäköisyyksin, on

kaikilla indeksikombinaatioilla . Yhteenlaskukaava supistuu tällöin binomikertoimen avulla merkittynä muotoon
.
Todennäköisyys, että  ensimmäistä vierasta saavat takaisin omat lahjansa, on
.
Kun tämä sijoitetaan yhteenlaskukaavaan, saadaan vastaus
.

Tämän kaavan avulla pystytään kysytty todennäköisyys laskemaan helposti eri lukumäärän  arvoille. Kun  lähestyy ääretöntä, suppenee todennäköisyys eksponenttifunktion määritelmän mukaan kohti Neperin luvun käänteislukua . Summalausekkeen luonteesta johtuen suppeneminen on hyvin nopeaa, ja likiarvo  pätee aina, kun lahjan tuovia vieraita on vähintään kuusi.

Todennäköisyyslaskennan ongelmat