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 $\frac{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[(-1{)}^{k-1}\sum _{i_1<\dots <i_k}\mathbb{P}\left(\bigcap _{j=1}^k{A}_{i_j}\right)]$.

Näin ollen riittää laskea tapahtumien $A_1,\dots ,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,\dots ,i_k\}\subset \{1,\dots ,n\}$. Yhteenlaskukaava supistuu tällöin binomikertoimen avulla merkittynä muotoon

$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{k=1}^n[(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})\mathbb{P}\left(\bigcap _{j=1}^k{A}_j\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((-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})\frac{(n-k)!}{n!})=\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,367879$. 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,367857$
$8$	$\frac{2119}{5760}\approx 0,367882$
$9$	$\frac{16687}{45360}\approx 0,367879$