Hledání tisícikorun v zásuvkách

Toto je spíš nabobtnalý diskusní příspěvek k předchozímu článku než plnohodnotný článek; do formátu diskuse by to ale bylo moc dlouhé a navíc v rámci článku je snažší psát přehledně vzorce. V debatě o pravděpodobnostech čtenář předložil zajímavý problém:

Máme [osoby] A a B a stůl s deseti zásuvkami. A schová tisícovku [do jedné zásuvky] a B označí [ne nutně stejnou] zásuvku, při shodě vyhraješ tisícovku. [Hra má] sto kol, v každém kole [se] můžeš účastnit, když zaplatíš částku x_i, ale výsledky jednotlivých kol se dozvíš až na úplném konci. Máš zaručeno, že A použije ve všech kolech stejné rozdělení, stejně tak B, ale A může mít jiné rozdělení než B (ale [...] o těchto rozděleních nic nevíš a A i B nejsou navzájem domluveni). Dále máš zaručeno, že všechny volby jsou navzájem i dohromady nezávislé (tedy jak volba A proti volbě B, tak volba A v jednom kole proti volbě A v jiném, stejně tak všechny další).

Otázky jsou:

1. Kolik je tvé x_i [nejvyšší, jež jsi ochoten zaplatit] v jednotlivých kolech? Je stejné pro různá i? Pokud ne, proč?
   
2. Pokud by namísto výplaty za každou shodu A i B byla jedna sázka (s někým uplně jiným, stejně neinformovaným/nedomluveným) taková, že vyhraješ tisícovku pouze v případě, když celkový počet shod v těch kolech bude 9,10 nebo 11, kolik by bylo tvé x pro účast v takové sázce? (FYI, pokud bych předpokládal rovnoměrné rozdělení u A i B, tak by tohle mělo být v cca 38 % případů.)
   

V původním komentáři je ještě třetí otázka, které ale zcela nerozumím a tak ji budu ignorovat. Druhá otázka skýtá závažný technický problém: postup, který zastávám, vede v tomto případě k výpočtu, který nejsem schopen přesně provést; najde-li se mezi čtenáři někdo s nápadem na řešení, budu mu povděčen. Aby čtenáři nebyli ochuzeni o plné řešení analogického problému, paralelně vyřeším „soft verzi“: počet zásuvek je tři namísto deseti, počet opakování je 9 namísto 100, alternativní sázka je na to, že v rámci devíti opakování dojde přesně ke třem shodám. Tato verze je analogická původní ve všech podstatných rysech a vede k výpočtům řešitelným v konečném čase.

Takže, jak na to? K řešení je třeba blíže se podívat na mechanismus hry. Máme dva „krupiéry“ A a B, kteří nezávisle na sobě volí z deseti / tří zásuvek. Bylo řečeno, že krupiéři vybírají zásuvky náhodně s nějakým rozdělením. Tato rozdělení určují relativní četnosti (frekventistické pravděpodobnosti) jednotlivých zásuvek. Rozdělení, jež užívá krupiér A, je charakterizováno deseti čísly a_i (podobně b_i pro krupiéra B). Dohromady budu pro stručnost zápisu mluvit o desetirozměrných vektorech a a b.

Jaké jsou tyto vektory? Úloha jasně říká, že o nich nic nevím, což lze přirozeně interpretovat tak, že žádný z vektorů nemám důvod preferovat. Bez této specifikace bych mohl spekulovat například o psychologii krupiérů, nicméně naprostá nevědomost pro mně znamená naprostou symetrii, což se projeví tím, že každé možnosti přiřadím stejnou pravděpodobnost. Ve skutečnosti samozřejmě o a a b přecijen něco vím: relativní četnosti a_i musejí být kladné a jejich součet musí být roven jedné:



(obdobně pro b_i). Rovnoměrné rozdělení tedy přiřadím jen těm vektorům, které splňují dané podmínky. Rozdělení bude vypadat takto:



(δ je Diracova δ-funkce, (n-1)! je normovací faktor; n je rovno 10, resp. 3). Pochopitelně stejné je to pro b.

Všimněte si, že nepředpokládám automaticky, že krupiéři užívají rovnoměrné rozdělení, nedosazuji tedy natvrdo (v původní verzi) a_i = 1/10. Rovnoměrné rozdělení (či obecně rozdělení s maximální Shannonovou entropií) přiřazuji svým subjektivním pravděpodobnostem, nejsou-li k dispozici informace preferující některé z možností před jinými. Čísla a_i a b_i jsou ovšem pro mne externí objektivně měřitelné parametry, které indexují navzájem se vylučující hypotézy o chování krupiérů. Každé z těchto hypotéz je přiřazena pravděpodobnost p(a,b); vzájemná nezávislost krupiérů implikuje



p(a) a p(b) jsou definované výše.

Samozřejmě, čísla a_i mají blízký vztah k subjektivním pravděpodobnostem: věřím-li, že platí hypotéza a, musím též věřit, že v každé iteraci hry je pravděpodobnost nalezení tisícovky v i-tém šupleti rovna a_i; tedy p(š_i|a) = a_i. Cokoli jiného by bylo nekonsistentní. K získání nepodmíněné pravděpodobnosti nalezení tisícovky v příslušném šupleti musím podmíněnou pravděpodobnost zintegrovat přes všechna a s vahou danou p(a). Tedy



Po dosazení vyjde p(š_i) = 1/n, tedy převrácená hodnota počtu zásuvek.

K řešení první otázky potřebujeme ale zjistit jinou pravděpodobnost: tu, že se oba krupiéři shodnou. Pravděpodobnost shody na i-té zásuvce je a_ib_i, musíme dále posčítat přes všechny zásuvky a zintegrovat přes všechna rozdělení. Tedy



Vyjde 1/n, tj. 1/10 pro původní verzi a 1/3 pro „soft“ verzi. Určit nejvyšší částku, za kterou není nevýhodné koupit právo na účast v popsané hře, je už snadné: 100, respektive 333 Kč.

Mohlo by se zdát, že jdu s kanónem na vrabce: až doposud dostávám totéž, jako kdybych přímo postuloval, že A a B sami používají rovnoměrné rozdělení. Mohl bych si ušetřit pracné integrování přes dvacetirozměrný prostor parametrů a_i, b_i. Při řešení druhé otázky ale postupy přestanou být ekvivalentní a postulováním a_i = b_i = 1/n bych nedostal hledaný výsledek. Zde potřebujeme znát, nakolik je pravděpodobné, že v sérii N her nastane shoda K krát. Pokud pravděpodobnost shody v rámci jednoho opakování hry je s, hledáme číslo



kde s = Σa_i b_i. Tuto věc musíme přeintegrovat znovu přese všechna rozdělení, takže dostaneme



Integruje se, stejně jako ve všech předchozích případech, pouze přes kladné hodnoty a_i a b_i. V původní verzi navíc musíme sečíst tři členy tohoto tvaru, s K = 9, 10, 11.

Bohužel, vyčíslit výše uvedený integrál není snadné ani s použitím počítače. V zásadě by se dalo postupovat otrocky, neboť se jedná o primitivní integrál z polynomu, ovšem jeho velikost rychle narůstá s rostoucími N a n. Proto původní verzi nejsem schopen dopočítat do konce. Má někdo z čtenářů nápad na elegantní řešení, případně rozumnou aproximaci?

V lehké verzi s N = 9, K = 3, n = 3 vyjde hledaná pravděpodobnost rovna zhruba 0,054; rozumná cena za sázku na přesně tři shody tedy nepřesáhne 54 Kč. Pro srovnání, pokud bychom měli jistotu, že oba krupiéři používají rovnoměrné rozdělení, byla by pravděpodobnost výhry rovna 0,273, více než pětkrát vyšší.

A teď slibuji, že si s pravděpodobnostmi dám na nějakou dobu pokoj.