Ero sivun ”Rencontre-ongelma” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
eiköhän se ole valmis |
||
Rivi 1:
'''Rencontre-ongelmalla''' eli '''yhteensattumisongelmalla''' tarkoitetaan [[Todennäköisyys|todennäköisyyttä]], että kun esimerkiksi joukko
== Ongelman ratkaisu ==
Ratkaisu on johdettavissa käyttäen apuna [[Joukko-oppi|joukko-opin]] ja todennäköisyyslaskennan kaavoja.
Olkoon lahjapaketin tuojien lukumäärä <math>n \in \mathbb{N}</math>. Sovitaan, että tapahtuma <math>A_i</math> sattuu, jos henkilö <math>i</math> saa oman lahjansa. Kysytty todennäköisyys on siis▼
▲Olkoon lahjapaketin tuojien lukumäärä <math>n \in \mathbb{N}</math>. Sovitaan, että tapahtuma <math>A_i</math> sattuu, jos
<center><math>\mathbb{P} \left( \bigcap_{i=1}^n A_i^c \right)</math>.</center>
[[De Morganin lait|De Morganin lakien]] mukaan pätee [[yhtälö]]
<center><math>\bigcap_{i=1}^n A_i^c = \left( \bigcup_{i=1}^n A_i \right)^c</math>.</center>
Tämän ja [[Komplementti|komplementin]] todennäköisyyden kaavalla saadaan yhtälö
<center><math>\mathbb{P} \left( \bigcap_{i=1}^n A_i^c \right) = \mathbb{P} \left[ \left( \bigcup_{i=1}^n A_i \right)^c \right]= 1-\mathbb{P} \left( \bigcup_{i=1}^n A_i \right)</math>.</center>
Todennäköisyyslaskennan yleinen yhteenlaskukaava on
<center><math>\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]</math>.</center>
Näin ollen
<center><math>\mathbb{P} \left( \bigcap_{j=1}^k A_{i_j} \right) = \mathbb{P} \left( \bigcap_{j=1}^k A_j \right)</math></center>
kaikilla indeksikombinaatioilla <math>\{ i_1 , \ldots , i_k \} \subset \{ 1, \ldots , n \}</math>. Yhteenlaskukaava
<center><math>\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]</math>.</center>
Todennäköisyys, että <math>k</math> ensimmäistä vierasta saavat takaisin omat lahjansa, on
<center><math>\mathbb{P} \left( \bigcap_{j=1}^k A_j \right) = \frac{1 \cdot (n-k)!}{n!} = \frac{(n-k)!}{n!}</math>.</center>
Kun tämä sijoitetaan yhteenlaskukaavaan, saadaan vastaus
<center><math>\mathbb{P} \left( \bigcap_{i=1}^n A_i^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!}</math>.</center>
Tämän kaavan avulla pystytään kysytty todennäköisyys laskemaan helposti eri lukumäärän <math>n</math> arvoille. Kun <math>n</math> lähestyy ääretöntä, suppenee todennäköisyys [[eksponenttifunktio]]n määritelmän mukaan kohti [[Neperin luku|Neperin luvun]] [[käänteisluku]]a <math>e^{-1} \approx 0.367 \, 879</math>. Summalausekkeen luonteesta johtuen suppeneminen on hyvin nopeaa, ja likiarvo <math>0.368</math> pätee aina, kun lahjan tuovia vieraita on vähintään kuusi.
{| border="1" cellspacing="0" cellpadding="2" align="center"
|- bgcolor="#efefef"
|