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".
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öisyys
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|