Denník N

Matematika – pravdepodobnosť v losovaní

V texte si ukážeme výpočet pravdepodobnosti výskytu javu pri losovaní. Text vznikol z vianočnej iniciatívy v práci losovať kolegu, ktorému venujeme vianočný darček.

Úvod 1- definícia problému

V práci pred Vianocami vznikla iniciatíva, ktorú sme nazvali „Secret Santa“. Ide o to, aby kolega venoval inému kolegovi nejaký malý darček. Aby však každý z tímu dostal darček, rozhodli sme sa, že budeme losovať mená a tak sa rozhodne, kto komu dá darček. Na spoločnom mítingu neskôr niekto povedal, že kolega X si vytiahol samého seba. Samozrejme, lístok dal naspäť a ťahal znovu.

Ja som sa však zamyslel nad týmto prípadom a vyslovil som otázku:
Aká je pravdepodobnosť, že v tíme o N ľuďoch si nikto nevytiahne svoje meno? Aby som bol konkrétny, tu je presný postup. Máme nádobu s lísktami, na lístku je jedno meno a každý lístok má iné meno. Ľudia, ktorých meno je v nádobe, losujú = vyberajú každý jeden lístok z nádoby. Každý človek vylosuje lístok s menom, ale nepozrie sa naň. Keď budú všetky lístky vyzbierané, každý si pozrie svoj lístok. Aká je pravdepodobnosť, že na lístku nikto neuvidí svoje meno?

Úvod 2- definícia podobného problému

Začal som túto otázku riešiť a mal som odpoveď pripravenú, ale predtým som otázku predostrel kolegom. Jeden kolega vyslovil úvahu a povedal, že je to tá istá pravdepodobnosť ako odpoveď na nasledujúcu otázku.
Ak sa ľudia navzájom spoja s tými, koho vylosovali, musí vzniknúť práve jeden kruh- aká je pravdepodobnosť?

Ako vysvetlím nižšie, nie je to ten istý problém ako predchádzajúci.

Riešenie

Zavedenie pojmov

Predtým, než si vysvetlíme, v čom sú tieto 2 problémy iné, zadefinujme si pojmy. Príklady budeme demonštrovať na tíme o populácii N = 4 ľuďoch s menami {A, B, C, D}. Problémy nazveme P1 a P2.

Grafom G budeme nazývať graf reprezentujúci losovanie. Ľudia, ktorí losujú, budú predstavovať uzly (vrcholy) grafu a prepojenia s tými, koho vylosovali, bude znázornené orientovanou hranou grafu.

Začneme druhým problémom, P2. Tento možno prepísať do otázky:

Aká je pravdepodobnosť, že v tíme o N ľuďoch títo vytvoria tzv. Hamiltonovský graf? Znovu, konkrétne ide o pravdepodobnosť, že losovanie bude predstavnené takým grafom, kde existuje len jedna kružnica.

Uvediem príklady takých Hamiltonovských grafov:

Obr1: Príklad Hamiltonovského grafu
Obr 2: Príklad Hamiltonovského grafu

Inými slovami, problém možno preložiť na pravdepodonosť, kedy najkratšia dĺžka kružnice (uzatvorenej cesty) v grafe P2: c_min(G) = N.

Nasledovné príklady nevyhovujú P2, pretože netvoria Hamiltonovskú kružnicu, t.j. c_min(G) != N.

Obr 3: Príklad nehamiltonovského grafu N=4, s minimálnou dĺžkou kružnice c_min(G)= 2.
Obr. 4: Príklad nehamiltonovského grafu N=4 s minimálnou dĺžkou kružnice c_min(G) = 1.

V prípade P1 požadujeme, aby človek nevylosoval seba. V teórii grafov teda hovoríme o prípade P1: c_min(G) > 1. Pre prípad 1 teda budú vyhovovať obrázky 1 až 3. Možno teda vysloviť predpoklad, že

P (P1) >= P (P2)

t.j. pravdepodobnosť vytvorenia grafu P (c_min(G) > 1) >= P (c_min(G) = N)

Riešenie príkladu č.2

V tomto príklade môžme vychádzať z tejto úvahy. Na to, aby sme pravdepodobnosť vyčíslili, musí prvý človek X vylosovať iné meno Y, môže ho prečítať (tým sme pravdepodobnosť nezmenili) a zároveň tento ďalší Y musí vylosovať hocikoho okrem X, ďalší tak isto atď.
Prvý človek teda má šancu (N – 1) / N na vylosovanie kohokoľvek, len nie seba.
Druhý človek už vyberá z N-1 ľudí a má šancu (N – 2) / (N – 1) na vylosovanie kohokoľvek, len nie prvého. Seba už vylosovať nemôže, keďže pri spomenutom postupe už bolo jeho meno vytiahnuté. Potom:

P (P2) = (N – 1)/N * (N – 2)/(N-1) * (N – 3)/(N-2) * … * 2/3 * 1/2 = 1 / N

Riešenie príkladu č.1

Tento príklad je trošku zložitejší, nakoľko podmienka nám dovoľuje vytvárať aj iné štruktúry (graf) ako jednu kružnicu. Na tento príklad sa môžeme pozrieť z iného pohľadu. Predstavme si množinu možných (vhodných aj nevhodných) výsledkov losovania.

To si možno modelovať takto. Menám presne v tomto poradí {A, B, C, D} priradíme ďalšiu N-ticu prvkov. Táto N-tica je jeden z množiny permutácií prvkov {A, B, C, D}:
{ {A, B, C, D}, {A, B, D, C} , {A, C, B, D} , {A, C, D, B}, {B, A, C, D} … {….} }

A B C D
A B C D
A B D C
A C B D
A C D B
B A C D

tak nám v konečnom dôsledku vzniknúť N! možností výsledkov losovania. Počet cudzích mien pod vlastným menom, je pre každé meno rovnaký, t.j. vylosovaním jednej z N! permutácií má každý teoretickú šancu (N-1)/N, že tam nebude jeho meno. Potom

P (P1) = (N – 1)/N * (N- 1)/N * (N-1)/N … = [(N-1)/N]^N

Táto pravdepodobnosť je len teoretická. V praxi sa totiž pri nízkom N vyskytuje, že sa samotné možnosti vylučujú, t.j. ide o podmienenú pravdepodobnosť. Napríklad, pri N = 2 vyzerá tabuľka nasledovne:

A B
A B
B A

Prvý prípad {A, B} nevyhovuje A, ale ani B a oba (A, B) zdieľajú to isté nevyhovujúce (prvé) pole. Podľa vypočítanej teoretickej pravdepodobnosti je však prvok A prispieva čiastkou 1/2 a rovnako nezávisle prvok B pomerom 1/2, čo robí P(P2, N=2) = 1/4. Je zrejmé, že s narastajúcim počtom N sa budeme teoretickou pravdepodobnosťou približovať k reálnej, nakoľko sa budú polia prekrývať menej.

Možno uviesť, že [(N-1)/N]^N je dolná hranica pravdepodobnosti (lebo, ako som spomínal, v realite je tých vyhovujúcich vzoriek viac, keďže niektoré nevyhovujúce sa prekrývajú medzi viacerými ľuďmi).

Teoretickú pravdepodobnosť teda možno vypočítať ako:

P (P1) = lim (N →∞) [(N-1)/N]^N = lim (N →∞) [1-1/N]^N = 1/e = 36.77%

V praxi som aj vytvoril model v pythone, ktorý počítal pravdepodobnosť pre N = 1 .. 10. Tento model vygeneroval všetky permutácie pre každé N a vypočítal k nim, či vyhovujú alebo nevyhovujú podmienke. Z pomeru vyhovujúcich nakoniec vypočítal (nameral) reálnu pravdepodobnosť.

Jeho výsledky prinášam v nasledovnom grafe:

Obr 5: Závislosť nameranej (odsimulovanej) pravdepodobnosti od veľkosti populácie a vypočítaná dolná hranica teoretickej pravdepodobnosti

Záver

Predchádzajúci príklad ma samého prekvapil oscilujúcou reálnou pravdepodobnosťou so zvyšujúcou sa populáciou (vidno na obr. 5 pri N=2 .. 5). V texte som vypočítal dolnú hranicu pravdepodobnosti. Bolo by vhodné pozrieť sa aj na hornú hranicu pravdepodobnosti, t.j. vypočítať, koľko vzoriek bolo vyradených z viacerých „zdrojov“ súčiniteľa.

Mnohí kolegovia vraveli, že ide o Birthday paradox, ten je však v niečom odlišný. Birthday paradox totiž predpokladá, že viacerí ľudia v populácii môžu mať tú istú „hodnotu“, v našom prípade by to bol rovnaký papierik s menom. To je vylúčené už zadaním.

Teraz najčítanejšie