Rencontre-ongelma

Rencontre-ongelma eli yhteensattumisongelma on todennäköisyys sille, että kun joukon ${\displaystyle A}$ alkiot kuvataan joukon ${\displaystyle B}$ alkioiksi ja joukon ${\displaystyle B}$ alkiot sekoitetaan satunnaiseen järjestykseen, niin kuvauksessa kaikki joukon ${\displaystyle A}$ alkiot saavat sekoituksessa jonkun uuden joukon ${\displaystyle B}$ alkion. Todennäköisyyden arvo riippuu alkioiden lukumäärästä, mutta se on asymptoottisesti vakio ${\displaystyle {\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ä ${\displaystyle n\in \mathbb {N} }$. Sovitaan, että tapahtuma ${\displaystyle A_{i}}$ sattuu, jos vieras ${\displaystyle i}$ saa takaisin oman lahjansa. Kysytty todennäköisyys on siis

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

De Morganin lakien mukaan pätee yhtälö

${\displaystyle \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ö

${\displaystyle \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

${\displaystyle \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 ${\displaystyle A_{1},\ldots ,A_{n}}$ kaikkien kombinaatioiden leikkausten todennäköisyydet. Koska lahjojen oletetaan jakautuvan symmetrisin todennäköisyyksin, on

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

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

${\displaystyle \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ä ${\displaystyle k}$ ensimmäistä vierasta saavat takaisin omat lahjansa, on

${\displaystyle \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

${\displaystyle \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 ${\displaystyle n}$ arvoille. Kun ${\displaystyle n}$ lähestyy ääretöntä, suppenee todennäköisyys eksponenttifunktion määritelmän mukaan kohti Neperin luvun käänteislukua ${\displaystyle \mathrm {e} ^{-1}\approx 0{,}367\,879}$. Summalausekkeen luonteesta johtuen suppeneminen on hyvin nopeaa, ja likiarvo ${\displaystyle 0{,}368}$ pätee aina, kun lahjan tuovia vieraita on vähintään kuusi.

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