Rencontre-ongelma

Rencontre-ongelma eli yhteensattumisongelma on todennäköisyys sille, että kun joukon $A$ alkiot kuvataan joukon $B$ alkioiksi ja joukon $B$ alkiot sekoitetaan satunnaiseen järjestykseen, niin kuvauksessa kaikki joukon $A$ alkiot saavat sekoituksessa jonkun uuden joukon $B$ alkion. Todennäköisyyden arvo riippuu alkioiden lukumäärästä, mutta se on asymptoottisesti vakio ${\tfrac {1}{\mathrm {e} }}=0{,}368$.

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ä $n\in \mathbb {N}$. Sovitaan, että tapahtuma $A_{i}$ sattuu, jos vieras $i$ saa takaisin oman lahjansa. Kysytty todennäköisyys on siis

$\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}^{\mathrm {c} }\right)$.

De Morganin lakien mukaan pätee yhtälö

$\bigcap _{i=1}^{n}A_{i}^{\mathrm {c} }=\left(\bigcup _{i=1}^{n}A_{i}\right)^{\mathrm {c} }$.

Tämän ja komplementin todennäköisyyden kaavalla saadaan yhtälö

$\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}^{\mathrm {c} }\right)=\mathbb {P} \left[\left(\bigcup _{i=1}^{n}A_{i}\right)^{\mathrm {c} }\right]=1-\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)$.

Todennäköisyyslaskennan yleinen yhteenlaskukaava on

$\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left[(-1)^{k-1}\sum _{i_{1}<\ldots <i_{k}}\mathbb {P} \left(\bigcap _{j=1}^{k}A_{i_{j}}\right)\right]$.

Näin ollen riittää laskea tapahtumien $A_{1},\ldots ,A_{n}$ kaikkien kombinaatioiden leikkausten todennäköisyydet. Koska lahjojen oletetaan jakautuvan symmetrisin todennäköisyyksin, on

$\mathbb {P} \left(\bigcap _{j=1}^{k}A_{i_{j}}\right)=\mathbb {P} \left(\bigcap _{j=1}^{k}A_{j}\right)$

kaikilla indeksikombinaatioilla $\{i_{1},\ldots ,i_{k}\}\subset \{1,\ldots ,n\}$. Yhteenlaskukaava supistuu tällöin binomikertoimen avulla merkittynä muotoon

$\mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left[(-1)^{k-1}{n \choose k}\mathbb {P} \left(\bigcap _{j=1}^{k}A_{j}\right)\right]$.

Todennäköisyys, että $k$ ensimmäistä vierasta saavat takaisin omat lahjansa, on

$\mathbb {P} \left(\bigcap _{j=1}^{k}A_{j}\right)={\frac {1\cdot (n-k)!}{n!}}={\frac {(n-k)!}{n!}}$.

Kun tämä sijoitetaan yhteenlaskukaavaan, saadaan vastaus

$\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}^{\mathrm {c} }\right)=1-\sum _{k=1}^{n}\left((-1)^{k-1}{n \choose k}{\frac {(n-k)!}{n!}}\right)=\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}$.

Tämän kaavan avulla pystytään kysytty todennäköisyys laskemaan helposti eri lukumäärän $n$ arvoille. Kun $n$ lähestyy ääretöntä, suppenee todennäköisyys eksponenttifunktion määritelmän mukaan kohti Neperin luvun käänteislukua $\mathrm {e} ^{-1}\approx 0{,}367\,879$. Summalausekkeen luonteesta johtuen suppeneminen on hyvin nopeaa, ja likiarvo $0{,}368$ pätee aina, kun lahjan tuovia vieraita on vähintään kuusi.

$n$	todennäköisyys
$2$	${\frac {1}{2}}=0{,}5$
$3$	${\frac {1}{3}}\approx 0{,}333$
$4$	${\frac {3}{8}}=0{,}375$
$5$	${\frac {11}{30}}\approx 0{,}367$
$6$	${\frac {53}{144}}\approx 0{,}368$
$7$	${\frac {103}{280}}\approx 0{,}367\,857$
$8$	${\frac {2\,119}{5\,760}}\approx 0{,}367\,882$
$9$	${\frac {16\,687}{45\,360}}\approx 0{,}367\,879$