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 ratkaisuMuokkaa

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