sobota 26. listopadu 2011

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 xi, 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é xi [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 ai (podobně bi 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 ai musejí být kladné a jejich součet musí být roven jedné:



(obdobně pro bi). 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) ai = 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 ai a bi 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 ai 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 ai; tedy p(ši|a) = ai. 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 aibi, 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ů ai, bi. Při řešení druhé otázky ale postupy přestanou být ekvivalentní a postulováním ai = bi = 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 = Σai bi. 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 ai a bi. 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.

4 komentáře:

  1. Dekuji za rozsahlou odpoved.

    K te treti otazce - cely ten priklad byl z me strany motivovan vnimanym rozporem mezi apriornimi pravdepodobnostmi a jejich skladanim, ale kdyz jsem to dopsal, tak me doslo, jake je reseni (ze prvky pravdepodobnostniho prostoru budou nejen konfigurace zasuvek, ale take primo ony distribuce na A, B; jako to je spocitane v tomto clanku), proto jsem k ni pripsal, ze jde o chytak (tedy ze naznacovany rozpor neexistuje).

    Kazdopadne jeste me zaujala jedna vec - v techto prikladech se implicitne predpoklada, ze pokud takto ziskany odhad pravdepodobnosti je p, pak je racionalni ucastnit se takovych sazek za x = vyhra * p, a je to vzdy peclive formulovane tak, ze protihrac nema informacni vyhodu. Co kdyby ji ale mohl mit? Tedy hra vypada takto: Mejme nejaky nahodny jev s deseti moznymi stavy, s pevnym, ale neznamym rozdelenim. Pak je tu osoba C, ktera nabizi sazku na to, ze 'padne jednicka' (pokud padne konkretni stav, hrac vyhraje tisicovku). Osoba C nemuze ovlivnit nahodny jev, ani jeho distribuci, ale nevylucujeme, ze muze mit lepsi znalost te distribuce. Jake bude prijatelne x, poplatek pro vstup do hry, v tomto pripade? Pokud jine nez 100, je to proto, ze v ty 'implicitni pravdepodobnosti' vlastne zas tak moc neverime, nebo proto, ze samotny fakt, ze se s nami chce nekdo vsadit na konkretni hodnotu, bereme jako vstupni informaci, ktera ty pravdepodnostosti ovlivni?

    OdpovědětSmazat
  2. Zapomel jsem dodat, ze ty mozne stavy jsou samozrejme v kazdem ohledu (tedy krom toho, ze osoba C chce na jeden z nich proti nam vsadit) symetricke, jako v predchozich prikladech.

    OdpovědětSmazat
  3. "Mejme nejaky nahodny jev s deseti moznymi stavy, s pevnym, ale neznamym rozdelenim. Pak je tu osoba C, ktera nabizi sazku na to, ze 'padne jednicka' (pokud padne konkretni stav, hrac vyhraje tisicovku). Osoba C nemuze ovlivnit nahodny jev, ani jeho distribuci, ale nevylucujeme, ze muze mit lepsi znalost te distribuce. Jake bude prijatelne x, poplatek pro vstup do hry, v tomto pripade? Pokud jine nez 100, je to proto, ze v ty 'implicitni pravdepodobnosti' vlastne zas tak moc neverime, nebo proto, ze samotny fakt, ze se s nami chce nekdo vsadit na konkretni hodnotu, bereme jako vstupni informaci, ktera ty pravdepodnostosti ovlivni?"

    Zajímavá otázka. Prakticky, kolik budu ochoten vsadit bude záviset na spekulaci o psychologii a motivech osoby C (chce mě obrat? chce hrát fér hru? umí počítat? zná teorii pravděpodobnosti? má averzi k riziku?). Zajímavé by bylo analyzovat celou situaci s nějakými "rozumnými" (čti dostatečně konkrétními a ne zcela absurdními) předpoklady, jako že oba hráči (já i C) jsou "dokonale racionální" a chtějí vyhrát; mám pocit, že pak by mohla být relevantní Aumannova věta o souhlasu, která říká, že pokud mají dva dokonalí bayesovští agenti stejné apriorní pravděpodobnosti a vědí navzájem o svých aposteriorních pravděpodobnostech nějaké zvolené hypotézy (a vědí, že vědí atd., common knowledge), pak se tyto pravděpodobnosti musí rovnat (nezávisle na tom, že každý z agentů učinil jiná pozorování).

    Musel bych si ale rozmyslet, jak přesně by se dal příklad formulovat, aby na to seděl.

    OdpovědětSmazat
  4. Samozřejmě, to, že se někdo chce vsadit na konkrétní hodnotu, je vstupní informace, která narušuje symetrii a pravděpodobnost ovlivní. Těžká otázka je, jak konkrétně.

    (Abych neignoroval explicitní dotaz.)

    OdpovědětSmazat