Rencontre-ongelma

Wikipediasta
Siirry navigaatioon Siirry hakuun

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

[muokkaa | muokkaa wikitekstiä]

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