Primitivně rekurzivní funkce

Toto je sedmý díl seriálu o logice, který volně sleduje myšlenky D.Hofstadtera sepsané v jeho knize Gödel, Escher, Bach. Navigace: úvodní článek - předchozí díl - příští díl.

Minule jsme si zběžně představili formální verzi aritmetiky; systém, ve kterém řetězce symbolů, jako třeba SS0=(S0+S0) nebo ∃n:(SSS0+n)=0, odpovídají výrokům z teorie čísel, jako třeba „jedna plus jedna je rovno dvěma“ nebo „tři je menší než nula“. Zajímavá a důležitá otázka je, jaké všechny výroky je možno formulovat pomocí řetězců tohoto systému. Pro (částečnou) odpověď se hodí definovat třídu funkcí, které se nazývají primitivně rekurzivní.

Mluvím-li v tomto článku o funkcích, mám na mysli takové, jejichž argumenty i návratové hodnoty jsou přirozená čísla (včetně nuly). Speciálním příkladem jsou pak predikáty, které mohou vracet pouze dvě hodnoty interpretované jako „pravda“ a „nepravda“ (standardně lze zvolit 1 a 0). Primitivně rekurzivní funkce tvoří podmnožinu všech funkcí a existuje několik ekvivalentních definic, které tuto podmnožinu definují. Intuitivně nejsrozumitelnější se zdá definice pomocí algoritmů, kterými je možné funkce vyčíslit: primitivně rekurzivní funkce jsou všechny takové, které lze spočítat pomocí programu obsahujícího pouze „primitivní operace“ a omezené cykly.

Primitivní operace jsou takové, které mají v daném programovacím jazyku předdefinované symboly nebo klíčová slova. Jaké operace se považují za primitivní je definováno výčtem; v podstatě se jedná o definici programovacího jazyka užitého pro vymezení primitivně rekurzivních funkcí. Jeho přesná podoba není až tak podstatná, protože různé volby mohou snadno vést ke stejné množině primitivně rekurzivních funkcí — stejný program lze zpravidla naprogramovat v různých programovacích jazycích. Pro konkrétnost lze za primitivní považovat sčítání, násobení a porovnávání čísel a přiřazování hodnot do proměnných. Dále musí být k dispozici instrukce, která zamezí vykonání části kódu, není-li splněna určitá podmínka (ve většině programovacích jazyků se taková instrukce nazývá if).

Klíčovou částí definice primitivně rekurzivních funkcí je existence pouze omezených cyklů. Omezený cyklus je část kódu, která se vykonává opakovaně; omezenost znamená, že před započetím cyklu je známý maximální počet opakování a tento počet je konečný. Ve většině programovacích jazyků odpovídá omezeným cyklům instrukce for. V následujícím textu budu využívat syntaxi jazyka Pascal, ve zjednodušené podobě: nesmím používat operátory dělení nebo odčítání (nejsou primitivní operace), proměnné jsou všechny přirozená čísla bez omezení maximální velikosti (a není tak třeba je deklarovat), a hlavně: jediný povolená instrukce navazující cyklus je for. Potenciálně neomezené cykly repeat a while, stejně jako instrukce goto, kterou tyto cykly lze nahradit, jsou zakázány. Absence neomezených cyklů zaručuje, že jakýkoli program napsaný v tomto jazyce skončí — nedostane se do nekonečné smyčky, ani například nebude zkoušet jedno přirozené číslo za druhým, zda nemá určitou vlastnost, bez jistoty, že vůbec nějaké číslo s tou vlastností existuje. Primitivně rekurzivní funkci lze spočíst v konečném čase pro každou možnou hodnotu jejích parametrů. (To ovšem neznamená, že jakákoli funkce, jejíž hodnoty spočítá terminující program, je primitivně rekurzivní.)

Příkladem primitivně rekurzivních funkcí jsou mocniny. Například, funkci x^y můžeme naprogramovat takto:

function mocnina(x,y);
begin

z:=1;
for i:=1 to y do z:=z*y;
mocnina:=z;
end;

Funkce mocnina obsahuje jeden cyklus, který proběhne právě y-krát. Čím větší y, tím déle program poběží, ale vždy skončí po konečném množství operací.

Cyklus může být přerušen, je-li splněna určitá podmínka. Například funkce, která určuje, zda n je prvočíslo (vrací 1 pokud ano, 0 pokud ne):

function prvocislo(n);
begin

z:=1;
for i:=2 to n-1 do
  for j:=2 to i do
    if i*j=n then
      begin z:=0; break; end;
prvocislo:=z;
end;

Funkce prohledává všechny možné dvojice dělitelů čísla n, a jakmile nějakou najde, ukončí další hledání (instrukcí break) a vrátí negativní odpověď. Dvojice vnořených cyklů projde všechny hodnoty pouze pokud je hledání neúspěšné a n je prvočíslem.

Funkce prvocislo je příkladem primitivně rekurzivního predikátu. Jejím parametrem je přirozené číslo a návratová hodnota má interpretaci pravda nebo nepravda. Podstatné tvrzení je, že všechny primitivně rekurzivní predikáty lze vyjádřit jako řetězce formální aritmetiky. Toto tvrzení bude pravděpodobně nejslaběji podloženým tvrzením v celé sérii článků, poněvadž mi není známo, jak se dokazuje. (Hofstadter tento problém elegantně ignoruje.) Na jedné straně se zdá přirozené, že má-li být formální aritmetika co k čemu, musí být schopna nejen vyjádřit, ale i dokázat tvrzení typu „n je prvočíslo“, obecněji pak všechna tvrzení, jejichž pravdivost jsme schopni otestovat pomocí zaručeně terminujícího algoritmu. Na druhé straně jsme minule viděli, že i velmi jednoduchý primitivně rekursivní fakt „n je mocnina dvou“ je vyjádřen velmi nepřímočarým způsobem pomocí prvočíselných dělitelů; jen o trochu složitější predikáty, jako například „n je mocnina šesti“, natož „n je mocnina nějakého přirozeného čísla“, jsou ještě o několik stupňů těžší (můžete se pokusit tyto predikáty formalizovat, ovšem nepočítejte s úspěchem). Každopádně požádám čtenáře, aby přijali vyjádřitelnost primitivně rekurzivních predikátů jako fakt, a pokročím dále.

Zatím jsme viděli příklady funkcí, které byly primitivně rekurzivní. Zajímavá otázka je, zda existují funkce, které nejsou primitivně rekurzivní. Kladnou odpověď dává slavný Cantorův diagonální argument. Cantor původně použil tento argument pro důkaz, že množina reálných čísel je nespočetná, tj. že nelze napsat posloupnost reálných čísel, ve které by bylo každé reálné číslo zastoupeno. Argument ve své původní podobě vypadá následovně: Předpokládejme, že můžeme reálná čísla seřadit do posloupnosti. Potom lze jistě seřadit do posloupnosti reálná čísla z intervalu <0,1) — bude to podposloupnost posloupnosti všech reálných čísel. Sepišme tedy pod sebe desetinné rozvoje těchto čísel tak, jak následují v posloupnosti. Dostaneme tak nekonečnou tabulku, jejíž prvních několik řádků bude vypadat třeba nějak takhle:



Podle předpokladu tabulka obsahuje všechna reálná čísla. Nadefinujeme nyní číslo D tak, že jeho desetinný rozvoj tvoří číslice vzniklé z číslic na diagonále této tabulky (jsou vyznačeny tučně) přičtením 1 ke každé (pokud je na diagonále 9, na odpovídajícím místě rozvoje D je 0). Pro naši ilustrační tabulku vyjde D = 0,39383065... Takto zkonstruované D je jistě reálné číslo ležící v daném intervalu, které se nikde v tabulce nenachází, protože jeho konstrukce zaručuje, že se od čísla na k. řádku liší přinejmenším číslicí na k. pozici desetinného rozvoje. To je ale ve sporu s předpokladem, že v tabulce jsou všechna reálná čísla, a protože argument nezávisí na tom, jak posloupnost reálných čísel konkrétně vypadá, plyne z toho, že reálná čísla nelze všechna seřadit do posloupnosti.

Aplikace diagonálního argumentu pro důkaz existence funkcí, jež nejsou primitivně rekurzivní, probíhá opačným směrem. Zde víme, že primitivně rekurzivní funkce lze uspořádat do posloupnosti. Učiníme to třeba tak, že vezmeme všechny syntakticky správné programy definující nějakou funkci a uspořádáme je nejdříve podle počtu znaků. Uvnitř každé ze skupin programů o stejném počtu znaků (kadžá taková skupina obsahuje pouze konečné množství programů) pak programy uspořádáme abecedně. Nyní můžeme každému programu přiřadit jednoznačně jeho číslo: ve skupině nejkratších programů bude programu na n. místě abecedního pořadí přiřazeno číslo n, ve druhé nejkratší skupině program na n. místě abecedního pořadí dostane číslo n + p, kde p je počet programů v první skupině atd. Každý program definuje nějakou primitivně rekurzivní funkci (různé programy mohou definovat stejnou funkci, ale to nevadí) a funkci definovanou n. programem označíme fn. Následně si vytvoříme tabulku, kde v n. řádku a k. sloupci bude hodnota fn(k). Tabulka bude vypadat nějak takto [1]:



Nadefinujeme teď funkci D(n) takto: D(n) = fn(n) + 1, tj. její hodnoty získáme z čísel ležících na diagonále tabulky. Funkce D je různá od libovolné funkce fn. Jelikož ale víme, že posloupnost funkcí fn obsahuje všechny primitivně rekurzivní funkce, funkce D nemůže být primitivně rekurzivní.

Fakt, že ne všechny funkce jsou primitivně rekurzivní, je možná zajímavý sám o sobě. Je zároveň i překážkou v naší snaze o konstrukci formálního výrazu, který bude přes Gödelovo číslování ekvivalentní lhářovu paradoxu. Připomenu z minula, že chceme, aby výraz o svém vlastním Gödelově čísle tvrdil, že to není Gödelovo číslo teorému; tímto způsobem výraz mluví o své nedokazatelnosti. Tvrzení T(n) = „číslo n není Gödelovým číslem teorému“ je predikát s jedním číselným parametrem. Kdyby T(n) byl primitivně rekurzivní predikát, měli bychom jistotu, že jej lze vyjádřit jako řetězec formální aritmetiky. Kdyby ale T(n) bylo primitivně rekurzivní, existoval by terminující algoritmus, který by umožňoval pro libovolné číslo ověřit, zda je Gödelovým číslem teorému, a tudíž pro libovolný výraz ověřit, zda je teorémem. Kdyby tomu tak bylo, bylo by dokazování matematických vět triviálně mechanickou činností a matematikové by přišli o práci [*]. Realita je ovšem komplikovanější: žádný mechanický postup pro ověření, zda výrok je dokazatelný, nemáme. Je proto odůvodněné se domnívat, že T(n) není primitivně rekurzivní.

Naštěstí se nabízí laciná cesta ven z tohoto problému, přes zavedení Gödelova číslování nejen pro výrazy, ale pro celé jejich sekvence vyjadřující důkazy. Udělat se to dá zcela analogicky číslování teorémů: každému znaku z formální abecedy se přiřadí jednoznačná sekvence číslic a sekvence se slepí k sobě. Navíc potřebujeme akorát číselnou kombinaci pro konec řádku. Uvažme kupříkladu odvození

1. ((S0=S0+0)⇒(0+S0=S0))
   
2. (S0=S0+0)
   
3. (0+S0=S0)
   

Zvolme libovolné Gödelovo číslování, například ( ~ 1, ) ~ 2, S ~ 3, 0 ~ 4, = ~ 5, + ~ 6, ⇒ ~ 7 a konec řádky ~ 8. Odvození můžeme zapsat jako ne zrovna malé číslo 113 453 464 271 463 453 422 813 453 464 281 463 453 428.

Jakmile máme očíslované důkazy i teorémy, můžeme zavést predikátovou funkci P(m,n), která vrací hodnotu pravda právě tehdy, když m je Gödelovým číslem odvození výrazu s Gödelovým číslem n. Tvrzení, že uvedené odvození je důkazem výroku „nula plus jedna je rovno jedné“ stojícího na poslední řádce, je pravdivé právě tehdy když P(113 453 464 271 463 453 422 813 453 464 281 463 453 428, 146 345 342) = pravda. (V tomto konkrétním případě bude ovšem predikát P nepravdivý, protože ač třetí řádek z prvních dvou plyne přes modus ponens a první dva řádky jsou teorémy, chybí jejich odvození. Aby P vracelo hodnotu pravda, je nutné, aby odvození bylo úplné: tj. všechny neodvozené řádky musejí být axiomy.)

Na rozdíl od funkce T(n) je funkce P(m,n) primitivně rekurzivní: zatímco zjistit, zda určitý výraz je teorém znamená povinnost hledat důkaz bez jistoty úspěchu, zjistit, zda předložené odvození je korektní je skutečně mechanická operace: postupujeme odvozením řádek po řádku a pro každý zjišťujeme, zda vyplývá z nějakých výše uvedených řádků pomocí legálního odvozovacího pravidla. Jelikož je řádků i pravidel konečný počet, lze s pomocí pouze konečných cyklů stvořit program, který bude tuto činnost vykonávat.

Primitivní rekurzivita funkce P implikuje, že existuje výraz, jehož interpretace je právě predikát P(m,n). Program ověřující korektnost odvození teorémů pochopitelně zabere víc než jen pár řádek, jeho reformulace do formálního jazyka s využitím Gödelova číslování tak bude představovat obludně dlouhý výraz. I kdybych explicitní podobu tohoto výrazu znal a chtěl ho vypsat explicitně, zabralo by to stovky nebo možná tisíce blogových článků. Protože mě ale na tomto výrazu zajímá pouze to, že existuje, spokojím se se zkratkou P(m,n) [*].

Nyní přichází pro dnešek poslední krok, a to konstrukce výrazu, který má interpretaci „n je Gödelovo číslo teorému“. Řekli jsme si, že ověřování toho, zda je n G.č. teorému není primitivně rekurzivní proces, a tak nemáme automaticky zajištěno, že tento predikát bude možno vyjádřit formálně. Můžeme si ale snadno pomoct primitivně rekurzivním predikátem P: výraz ∃m:P(m,n) má interpretaci „existuje číslo m, které je G.č. korektního odvození výrazu, jehož G.č. je n“; krátce „existuje důkaz pro výraz s G.č. n“, neboli „výraz s G.č. n je teorém“.

Poslední problém, který zbývá na příště, je jak nacpat dovnitř výrazu jeho vlastní Gödelovo číslo.

Poznámky:
1.Přísně vzato tabulka neodpovídá řazení programů podle délky zápisu v našem modifikovaném Pascalu; nejkratší program korektně zapsaný v této syntaxi je

function a(b);
begin

a:=0;
end;

reprezentující konstantní nulovou funkci. Nicméně naše řazení není jediné možné řazená programů a náš jazyk není jediný možný jazyk, lze si tak představit i jiné řazení produkující naši ilustrační tabulku.

Pondělní šifra XXXIV.

Následující obrázek v sobě skrývá zašifrovanou tajenku, kterou může být slovo, výraz nebo věta dávající v češtině dobrý význam (může to být i vlastní jméno nebo cizí slovo, pokud je v češtině dostatečně často používáno). Způsob šifrování není předem specifikován, ale měl by být odhalitelný na základě relativně jednoduchých pozorování. V některých případech může být k rozluštění potřeba znalost Morseovy abecedy nebo Braillova písma.

Garbage in, garbage out?

Přibližně za poslední měsíc se u dvou článků na tomto blogu rozvinula na zdejší poměry nevídaně rozsáhlá diskuse. Oba články se týkaly chyb ve vyhodnocování informací a někteří četnáři nesouhlasili jak s klasifikací určitých vzorců myšlení jako chybných, tak i s mými doporučeními ohledně korektního hodnocení faktů. Objevila se i stížnost, že utíkám před dotazy oponenta. I když jsem měl konkrétní důvody pro přerušení debaty (které jsem v jejím průběhu vysvětlil), má ona stížnost něco do sebe: až doposud jsem psal o tom, jak se postupovat nemá, ale dosud jsem jasně neilustroval, jak se postupovat má. Mohlo by to působit dojem, že se nesportovně snažím krýt před údery soupeře. Co je ale horší, varování před chybnými návyky se snadno stane bezcenným, není-li doprovázeno srozumitelným popisem návyků lepších, kterými ty staré lze nahradit. Mám proto zřejmě jistý dluh, který se pokusím dnes splatit. Čtenářům předložím k posouzení postup pro stanovaní pravděpodobnosti hypotézy, o které se diskutovalo pod druhým z odkazovaných článků: Američané zadržení na Íránských hranicích v roce 2009 a letos odsouzení za špionáž jsou skutečně špioni. Nejprve ale krátká všeobecná „palebná příprava“.

Myslím, že jsem již dal dostatečně najevo, že jako cestu ke zlepšení přesnosti odhadů vnímám především redukci sporné otázky na pokud možno elementární podotázky a kvantifikaci relevantních pravděpodobností. Objevila se ovšem námitka, že cpát nejistá data do matematického vzorečku je nesmysl, podle hesla garbage in, garbage out. Nejdřív je tedy na místě vyjádřit se k této námitce.

Heslo garbage in, garbage out (doslova odpad dovnitř, odpad ven, lépe však nesmysly na vstupu, nesmysly na výstupu) bylo původně míněno jako poukaz na nástrahy počítačových modelů. Stává se, že se na počítači implementovaný matematický model dostane do rukou lidem, kteří mají jen vágní představu o jeho fungování. Tito lidé mají model použít a, jsouce zběžně informováni o tom, jaká data model vyžaduje, tato data vyplní jako vstupní parametry; model pak vypočítá hledanou odpověď. Především v dobách nízké všeobecné počítačové gramotnosti byly počítače obklopeny mysteriózní atmosférou, a mnoho lidí považovalo tvrzení „je to výsledek počítačového modelu“ za mystickou garanci správnosti získané odpovědi. Modely jsou ale často citlivé na přesnost vstupních dat a pro některá data nemusí fungovat vůbec. Nemá-li člověk dobrou představu o fungování toho kterého modelu, je jeho užití sázka do loterie, především pokud jsou vstupní data získaná hrubým odhadem. Výstup má pak kvalitu vstupu. Garbage in, garbage out.

Je na místě obávat se podobného efektu při pravděpodobnostní analýze otázky z reálného světa? Na jedné straně ano. Vyjádříme-li pravděpodobnost zkoumaného tvrzení Z jako funkci dílčích pravděpodobností elementárnějších tvrzení E_i, pak se chyby v odhadech P(E_i) skládají a chyba celkového P(Z) může být veliká. Varování sloganu garbage in, garbage out tak zůstává v platnosti: to, že výsledná pravděpodobnost vylezla ze vzorečku, neznamená, že ji můžeme bůhvíjak důvěřovat, natož že to objektivně správná pravděpodobnost. (Pravděpodobnosti jsou sice subjektivní už z definice, ale pocit objektivity svázaný s prováděním výpočtu se i tak může objevit.)

Na druhé straně, „garbage in, garbage out“ je slogan, který je správné užívat jako varování před přílišnou důvěrou ve výsledky složitých výpočtů, nikoli jako argument odůvodňující nevybíravé odmítání jakéhokoli matematického modelu. A přitom takto nesprávně bývá heslo používáno přinejmenším stejně často jako správně. I když je matematický model nespolehlivý v důsledku nespolehlivosti vstupních dat, neznamená to, že intuitivní odhad výsledku je jakkoli spolehlivější. Jistě, může se stát, že má-li člověk praxi v určité disciplíně, vytvoří si relativně spolehlivou intuici pro komplikované odhady, a tato intuice funguje lépe, než formální výpočet založený na jednodušších odhadech, ve kterých řečený člověk nemá žádnou praxi. (Kanonický příklad jsou šachy: dobrý šachista díky své intuici vybere lepší tah než průměrný šachový program — i když zde to nemá co dělat s přesností vstupních dat — aniž by byl schopen sdělit, proč ten tah vybral. Ještě silněji než v šachách dominuje intuice v gu.) Ale kolikrát se s takovou situací setkáme? Spíše než experta s vytříbenou intuicí potkáme falešného experta, který se domnívá, že má zkušenostmi vytříbenou intuici, ale ve skutečnosti není o nic lepší, než náhodný generátor. Výsledky pokusů s účastí vysoce oceňovaných ochutnávačů vína jsou varující.

Možná nejdůležitější idea statistických analýz je ta, že náhodné chyby mají tendenci se navzájem vyrušit. Subjektivní pravděpodobnosti mohou být ovlivněny spoustou náhodných faktorů, ale odchylky mohou stejně často být směrem nahoru jako směrem dolů. Pravděpodobnost složené hypotézy tak má šanci být mnohem přesnější, je-li odvozena z dílčích pravděpodobností, než je-li odhadnuta přímo. Hlavní důvody, pro které prosazuji detailní analýzu, jsou ale jiné. První z nich je zmenšení systematických chyb. Spousta otázek je takříkajíc „citlivých“, v tom smyslu, že zasahují do světonázorových přesvědčení, se kterými se člověk identifikuje. Politická a náboženská přesvědčení jsou typickými, byť ne jedinými, příslušníky této kategorie. Zpochybnění světonázorového přesvědčení je pociťováno jako osobní útok a urážka, případná změna takového přesvědčení pak jako zrada [1]. Systematické chyby v odhadech pravděpodobností jsou podvědomou obranou proti situaci, kdy fakta svědčí ve prospěch hypotézy jsoucí v konfliktu s přijímaným světonázorem. Výhoda redukce na dílčí podotázky spočívá ve dvou věcech: jednak dílčí podotázky samy o sobě bývají méně citlivé, a jednak na první pohled nemusí být jasné, jakým směrem a jak silně bude ten který dílčí odhad projevovat ve výsledné pravděpodobnosti. Například je snažší nezaujatě odhadovat výši vybraných daní při dané daňové zátěži, než se rovnou snažit rozřešit otázku, zda je stávající daňový systém spravedlivý. Mnoho lidí nosí silné přesvědčení o spravedlivosti či nespravedlivosti stávajících daní, ale málokdo má předem připravený odhad toho, kolik se na daních vybere. Zástupci protivných politických táborů mají mnohem větší šanci se shodnout na metodě, jak odvodit výslednou odpověď (spravedlivost systému) z dílčích dat (životní náklady, úspěšnost výběru daní, ...) a zároveň se shodnout na těchto datech, než přímo na závěrečné otázce. Opravdu zatvrzelý debatér asi bude ochoten vycouvat z dohodnutých pravidel a zpětně upravit dílčí odhady tak, aby mu seděly do předpřipraveného výsledku, takový postup s sebou ovšem nese nezanedbatelné stigma podvádění. Čím striktnější pravidla, tím těžší je jejich obcházení. Dílčí hypotézy navíc mohou hrát roli i v jiných argumentech a člověk si musí dávat pozor na jejich vzájemnou konsistenci.

Druhým důvodem pro kvantifikaci dílčích pravděpodobností je efektivita komunikace. Je jasné, že debata o spravedlivosti daňového systému nemůže skončit deklaracemi názorů soupeřících stran. Musí následovat nějaké zdůvodnění názorů. Zdůvodnění ovšem mohou být slabá i silná, a jen velmi zřídka se diskutující namáhají své důvody kvantifikovat. Ve výsledném dojmu tak lehce může převážit ten, kdo složí velké množství okrajově závažných nebo zcela nepodstatných argumentů nad druhou stranou, která má jeden silný argument. Vyčíslení věrohodnostních poměrů je způsob, jak poměřovat schopnost dílčích faktů ovlivňovat pravděpodobnost sporné hypotézy. Takto kvantifikovaná diskuse je výrazně efektivnější, protože umožňuje oběma stranám zjistit, kde leží nejsilnější obrana protivníka, a ignorovat nepodstatné zástěrky. Opravdu zatvrzelý debatér sice může přiřadit nerealisticky vysoký věrohodnostní poměr irelevantnímu faktu, je to však krok mnohem nápadnější a zranitelnější, než realizace podobné taktiky skrytě, bez uvedení konkrétních čísel.

Teď už ale ke konkrétnímu příkladu. V následujícím textu rozeberu posledně diskutovanou hypotézu, sepíšu informace, které uvažuji, a uvedu pravděpodobnosti a věrohodnostní poměry svázané s jednotlivými informacemi. Doporučuji udělat si vlastní odhad předtím, než rozkliknete moje skryté odhady, abyste jimi nebyli ovlivněni. Na konci můžeme porovnat svá čísla. Je dost dobře možné, že jsem opomněl nějaký důležitý fakt. V takovém případě na něj můžete upozornit. Cílem není ani tak vyrobit neprůstřelný argument potvrzující či vyvracející danou hypotézu, jako spíš ilustrovat postup hledání pravdy v neurčitých datech na konkrétním příkladě. Protože jsem před provedením dílčích odhadů intuitivně usoudil, že zadržení nebyli špioni, jsem pravděpodobně zaujatý v neprospěch hypotézy, že se jednalo o špiony, a pro kompenzaci se budu snažit odhady svědčící ve prospěch špionáže spíše nadhodnocovat a odhady svědčící v její neprospěch spíše podhodnocovat.

Pro pohodlné započítávání faktů se snáze než se samotnými pravděpodobnostmi počítá s šancemi. Šance jsou poměr pravděpodobnosti a jejího doplňku, p/(1-p), a obvykle se zapisuje jako sportovní skóre. Například, je-li pravděpodobnost hypotézy 1/2, jsou její šance 1:1; pravděpodobnosti 90% odpovídají šance 9:1, pravděpodobnosti 30% odpovídají šance 1:2,33 atd. Výhoda šancí spočívá v tom, že při započítávání nové informace I je stačí vynásobit věrohodnostním poměrem P(I|H)/P(I|¬H) (kde H je hypotéza, na jejíž šance se ptáme).

Testovaná hypotéza jest:
Š: Občané USA S.Bauer a J.Fattal, odsouzení 20. srpna v Íránu za nezákonné překročení hranice a špionáž, byli na špionážní misi.

Hypotéza je pro pozdější stručné odkazování označena písmenem Š. Pro ujasnění případných nejasností, pod slovo špion zahrnuji jakékoli osoby pověřené nějakou organizací (ne nutně vládní) získávat informace na cizím území v rozporu s místními zákony. Specielně sem počítám všechny příslušníky ozbrojených sil vyslané na zpravodajskou misi s cílem překročit íránské hranice. Jako špiony neklasifikuji vojáky, kteří překročí hranici nedopatřením. (Uvádím toto upřesnění pod vlivem sporu o totéž pod minulým článkem. Máte-li ovšem pocit, že spor se původně týkal něčeho jiného, je to docela možné. Nechci tímto oživit starou debatu a řešit otázku, kdo měl pravdu, pouze zabránit budoucím nedorozuměním.)

Dostupné informace jsou:

1. Bauer a Fattal byli spolu s S.Shourdovou zadrženi íránskou pohraniční stráží 31.7.2009 v oblasti Ahmed Awa v blízkosti irácko-íránských hranic.
   
2. Zadržení byli obviněni z nedovoleného překročení hranice a špionáže.
   
3. Obvinění tvrdí, že byli v oblasti jako turisté a o přesné poloze hranice nevěděli.
   
4. Shourdová byla propuštěna na kauci půl milionu dolarů ze zdravotních důvodů.
   
5. Shourdová opustila Írán a na trestní řízení se nevrátila, údajně ze zdravotních důvodů.
   
6. Zadržení byli odsouzeni za nezákonné překročení hranice a špionáž na osm let vězení.
   
7. Další dosud nezapočítané informace.
   

Toto jsou všechny informace přímo se týkající případu, které budu používat. (Posouzení jejich důvěryhodnosti bude součástí následné analýzy.) Jistě se dá najít řada dalších informací, věnuje-li tomu člověk víc času. Nechce-li se ale člověk ve věci osobně angažovat, asi nebude chtít strávit celý den hledáním dokladů k pro něho nepodstatné záležitosti.

A priori:
Někde musíme začít. Teoreticky máme začít s apriorní pravděpodobností P₀(Š) v absenci jakékoli další informace. Přinejmenším ale musíme vědět, co vůbec říká hypotéza Š. Ta hovoří pouze o třech občanech USA a jejich špionáži. Jaká tedy je pravděpodobnost, že tři náhodně vzatí občané USA jsou špioni (ve smyslu definovaném výše)? Pozor: Apriorní pravděpodobnost zatím nebere v úvahu fakt, kde byli obvinění zadrženi, ani fakt, že byli ze špionáže obviněni. Tyto skutečnosti započítáme později; pokud je zahrnete do apriorní pravděpodobnosti, započítáte je dvakrát. (Klikněte na „Zobraz“ pro zobrazení mého odhadu.)

Zobraz

Na Wikipedii je seznam tajných služeb USA, u některých z nich je uveden odhad počtu zaměstnanců.cca. Největší jsou CIA, FBI a DIA s cca. 20 000 zaměstnanci každá. Z toho odhaduji, že celkový počet zaměstnanců tajných služeb USA je cca. 100 000. Ne všichni jsou ovšem vysíláni do zahraničí na zpravodajské akce. Můj (nepodložený) odhad podílu počtu špionů na celkovém počtu zaměstnanců je cca. 1/20, což by znamenalo 5 000 špionů v žoldu tajných služeb. Dále ovšem existuje možnost, že obvinění nebyli agenti tajné služby, ale prostí vojáci vyslaní na špionážní misi. Armáda USA má zhruba půl milionu vojáků v aktivní službě. Poměr počtu špionů k ostatním vojákům bude nižší než v tajných službách, řekněme 1/100 (další nepodložený odhad). Dostanu tak 5 000 vojenských špionů. Celkem tedy 10 000 špionů. Zajímá nás ovšem ne to, zda zadržení někdy během svého života byli špioni, ale zda v daný okamžik byli na zpravodajské akci. Řekněme, že průměrný špion tráví špionáží polovinu svého času, tudíž v jeden moment je aktivních pět tisíc špionů. Populace USA je zhruba 300 milionů, z toho v použitelné věkové kategorii bude cca. 200 milionů, hrubý odhad P₀(Š) tak vychází na cca. 1/40 000 a tudíž šance pro Š jsou a priori zhruba 1:40 000.

Možnost, že obvinění špionovali pro jinou zemi, než USA, nebo pro soukromý subjekt, zanedbávám, oprava by zvýšila P₀(Š) směrem nahoru, předpokládám však, že neznatelně. Taktéž ignoruji fakt, že skupina sestávala ze dvou mužů a jedné ženy. V armádě a tajných službách je jiný poměr počtu mužů k počtu žen než mezi obecnou populací, takže by se tento fakt dal využít k přepočtení pravděpodobnosti. Tato oprava by P₀(Š) naopak snižovala.

Informace č.1:
Američané byli zadrženi v příhraniční oblasti. Pro aktualizaci pravděpodobnosti touto informací musíme odhadnout věrohodnostní poměr P(I₁|Š) / P(I₁). Jaká je šance špiona být zadržen na íránsko-kurdistánských hranicích, a jakou šanci má nešpion? Nechť p_šk je procento amerických špionů, kteří jsou aktivní v Kurdistánu, p_ší je podíl těchto špionů, kteří jsou v jednom momentě vysláni s úkolem proniknout na íránské území nebo do příhraniční zóny, pravděpodobnost, že takový špion bude v jednou konkrétním dni (kdy se nachází v nebezpečné oblasti) zadržen, označím p_šz. P(I₁|Š) bude rovna p_škp_šíp_šz. Pro zjištění pravděpodobnobnosti zadržení nešpiona postupujeme analogicky: procento amerických občanů (kromě špionů) pohybujících se v Kurdistánu označme p_nk, procento těchto turistů kteří se dostanou do blízkosti íránských hranic p_ní a procento zadržených nechť je p_nz; P(I₁|¬Š) = p_nkp_níp_nz.

Zobraz

Nejdříve p_šk. Američtí špioni budou především dislokováni do zemí, které jsou pro USA rizikové nebo přímo nepřátelské. Jelikož mezi špiony počítám i vojáky angažované do zpravodajských akcí, přednost mají válečné oblasti. Oblast Blízkého východu je silně problematická, počítám tedy, že může být působištěm čtvrtiny aktivních špionů (zbytek bude pravděpodobně rozložen po Evropě, speciálně v zemích sousedících s Ruskem a v bývalé Jugoslávii, střední Asii (zejména Afghánistán), Koreji, jihovýchodní Asii (kvůli drogám), Střední a Jižní Americe). Z čtvrtiny špionů aktivních na Blízkém východě může být polovina v Iráku a z toho pětina v Kurdistánu. Dostávám p_šk = 1/40. Řekněme, že každý desátý špion v Kurdistánu občas dostane úkol prozkoumat hraniční zónu nebo dokonce proniknout na íránské území a tímto úkolem stráví dvacetinu svého času (15-20 dní v roce); (p_ší = 1/200). (Pro kontrolu, spolu s apriorním odhadem to vychází na 125 aktivních špionů v Kurdistánu a každý den zhruba poloviční šanci, že na hranici je aspoň jeden aktivní špion. Hlavně první číslo se zdá být příliš vysoké. Většina amerických zpravodajů v problematických zemích budou místní obyvatelé, nikoli američtí občané. Je tak možné, že počet špionů silně nadhodnocuji, nicméně odhad měnit nebudu — pocit, že počet nadhodnocuji není o nic spolehlivější než získaný odhad.)

Špioni by nešli masově do akce, kde by byla pravděpodobnost zadržení nepřítelem výrazně vysoká a jistě jsou vycvičeni k minimalizaci tohoto rizika. Na druhou stranu riziko nebude úplně zanedbatelné, dejme tedy p_šz = 1/100 (za každý den). Dohromady P(I₁|Š) = 1/800 000. (Interpretace je, že jeden konkrétní americký špion má statisticky šanci 1/800 000 být zadržen na kurdistánsko-íránské hranici. To pochopitelně není příliš informativní číslo, už proto, že zahrnuje i špiony, kteří se do oblasti vůbec nepodívají. Uvážíme-li ale odhad počtu špionů učiněný v předchozím kroku, vyjde nám každodenní šance 1/160 na zadržení libovolného špiona na íránsko-irácké hranici, což znamená v průměru dva špiony v rukou Íránců za rok (pouze co se týká příhraniční oblasti v Kurdistánu). Nemáme sice dvakrát do roka zprávy o zadržení špionů v oblasti, je ovšem možné, že se o takových věcech veřejně nemluví.

Co se týká nešpionů, omezím se na turisty, kteří pravděpodobně tvroří větší část této skupiny. Počet turistů ze zemí Západu navštívivších Kurdistán v roce 2009 odhaduji na 50 tisíc. (Jeden zdroj tvrdí, že toto číslo je 69 000, druhý mluví o 132 000, ovšem nespecifikuje, že se jedná o západní turisty. V minulé diskusi se objevila se námitka na nespolehlivost prvního zdroje, ovšem bez konkrétního důvodu proč by tento zdroj měl daný údaj falšovat. Každopádně spolehlivější informace nemám, odhad lehce koriguji směrem dolů.) Z toho odhaduji, že Američanů bude 1/3 (zhruba poměr populace USA k celkové populaci Západu). Pokud turista stráví v Kurdistánu v průměru týden, je v jednom okamžiku v Kurdistánu 300 amerických turistů. V poměru s celkovou populací USA máme p_nk = 1/1 000 000. Kolik z těchto turistů zatouží po výletu do příhraničních oblastí? Může být, že polovina turistů přijíždí primárně za přírodou do hor, a z těchto turistů každý stý nedbá opatrnosti a dostane se (v jednom dni) do blízkosti hranic. Hranice v oblasti není značena, takže je snadné ji překročit (zadržení Američanů v roce 2009 vešlo ve známost a vedlo ke zvýšení opatrnosti při výletech do příhraničních oblastí; před tímto incidentem netřeba předpokládat příliš velkou opatrnost). Můj odhad p_ní tak je 1/2 000. Turista překročivší hranici v nevědomosti se nebude snažit skrývat a šance na zadržení je tak vyšší než u špiona. Odhadnu tak p_nz = 1/10. Dohromady, P(I₁|¬Š) vychází na 1:2x10¹⁰.

Hledaný věrohodnostní poměr je roven 25 000. Jedná se tedy o velmi silné svědectví ve prospěch hypotézy Š, dohromady s apriorním odhadem jsou v této fázi její šance zhruba 1:1,6.

Informace č.2:
Zadržení byli obviněni ze špionáže. Relevantní pravděpodobnosti jsou P(I₂|Š) a P(I₂|¬Š), tedy pravděpodobnost, že zadržený špion bude obviněn ze špionáže, respektive že nešpion bude obviněn z téhož.

Zobraz

Samozřejmě závisí na paranoidnosti vyšetřovatelů, nicméně pokud vyšetřovatelé nejsou zcela neschopní, P(I₂|Š) > P(I₂|¬Š). Je zbytečné odhadovat obě pravděpodobnosti zvlášť, protože nás zajímá jejich poměr: nakolik je pravděpodobnější, že vyšetřovatel obviní ze špionáže špiona, než že obviní turistu, za předpokladu, že k zatčení dojde při nelegálním přechodu hranic? Můj odhad tohoto poměru je 2:1. Celkové šance jsou nyní 1,25:1 ve prospěch Š.

Informace č.3:
Zadržení tvrdí, že jsou turisté. Zde se ptáme, nakolik je pravděpodobné, že toto budou tvrdit špioni, tj. P(I₃|Š), a nakolik je pravděpodobné, že to budou tvrdit turisté, P(I₃|¬Š).

Zobraz

Druhá z pravděpodobností, P(I₃|¬Š), je prakticky rovna 1. První z nich, P(I₃|Š), je nižší: špion se samozřejmě může snažit namluvit svým věznitelům, že je turista, má ale i jiné možnosti úniku. Může se třeba přiznat a doufat v polehčující okolnosti, může se pokoušet vykoupit se nabídkou spolupráce, může uvést jinou výmluvu. Odhadem, špion bude tvrdit, že je turista v polovině případů. Šance se vracejí na 1:1,6.

Informace č.4:
S.Shourdová byla propuštěna z vazby na kauci ze zdravotních důvodů. Je pravděpodobnější, že bude propuštěna špionka, nebo že bude propuštěna turistka, a nakolik?

Zobraz

U této informace si nejsem jist, zda vůbec má v případu vypovídající hodnotu. Dávám tedy P(I₄|Š)/P(I₄|¬Š) = 1 a ponechávám šance pro Š beze změny.

Informace č.5:
Shourdová se nevrátila do Íránu k přelíčení. Jak pravděpodobné je, že obviněná Američanka se dobrovolně dostaví k soudu do Íránu, kde jí hrozí dlouholetý trest odnětí svobody, pokud k tomu není nucena?

Zobraz

P(I₅|Š), tj. pravděpodobnost, že se skutečná špionka dobrovolně vydá do rukou nepřítele, je znovu prakticky rovna 1. Pravděpodobnost P(I₅|¬Š), tj. že nevinná Američanka do Íránu za účelem nechat se soudit nepojede, je taktéž vysoká. Podmínky ve věznicích nejsou nikde na světě příjemné, a podmínky v ženské věznici v islámské rozvojové zemi o to méně, a Shourdová měla možnost se s těmito podmínkami seznámit. Pokud je navíc skutečně nevinná, měla taktéž dost důvodů nedůvěřovat justici státu, který ji zadržel. Odhaduji, že ne více než jedna z dvaceti nevinných Američanek by se dobrovolně do Íránu vrátila. Šance se mírně zvedají na 1:1.51.

Informace č.6:
Zbylí zadržení byli odsouzeni na osm let vězení za špionáž. Zde se jedná o analogii informace číslo 2, pouze namísto úsudku vyšetřovatele bereme v úvahu výsledek soudního řízení. Pozor na dvojí započítávání informace: Pokud soud rozhodl na základě stejných faktů, které měl k dispozici vyšetřovatel, výrok soudu by nepředstavoval prakticky žádnou novou informaci. Stručně řečeno, obvinění a odsouzení nejsou nezávislé jevy. Máme zde dvě pravděpodobnosti: P(I₆|Š), tj. pravděpodobnost, že špion obviněný ze špionáže bude i odsouzen, a P(I₆|¬Š), tj. že nevinný člověk obviněný ze špionáže bude odsouzen.

Zobraz

Znovu jde o poměr P(I₆|Š)/P(I₆|¬Š). Pro odsouzení musí být k dispozici silnější důkazy než pro pouhé obvinění a vzetí do vazby, ale to je v tuto chvíli irelevantní, poněvadž to stejným způsobem ovlivňuje pravděpodobnosti v čitateli i jmenovateli. Pakliže soud nemá k dispozici informace, které vyšetřovatel neměl, je věrohodnostní poměr roven jedné. Silně usvědčující informací by bylo přiznání, k tomu však nedošlo. Zda soud měl k dispozici nějaké další informace nevíme, ovšem zpravodajské informace související se špionáží bývají obvykle velmi nespolehlivé. Můj odhad věrohodnostního poměru zde je zde 3:2 (považuji odsouzení za relativně slabou informaci), díky čemuž se šance hypotézy Š dostávají někam k úrovni 1:1.

Informace č.7:
Další dosud neuvážené informace. Zde ponechávám čtenářům plnou volnost úvah, aspoň do té doby, co si zobrazí skrytý text.

Zobraz

Zde samozřejmě můžeme hledat a na sebe vršit libovolné množství faktů. Stránka o případu na Wikipedii nabízí řadu dalších informací. Jako nejpodstatnější hodnotím fakt, že zadržení Američané byli propalestinskými aktivisty údajně činnými v organizaci Palestine Solidarity Movement. Aktivní opozice obviněných vůči politice USA je doložena jednak texty, jejichž byli obvinění autory (lze najít např. zde po kliknutí na jednotlivá jména na vrchu stránky), a dále vyjádřeními dalších lidí (pro konkrétnost uvedu Noama Chomského, jehož kritický postoj k politice USA je známý a kterého tudíž těžko lze podezírat z vědomé mystifikace ve prospěch špionů). Existuje samozřejmě možnost, že protiamerické a protiizraelské články obviněných jsou pozdějším podvrhem určeným k oklamání íránských úřadů, nebo maskováním vytvořeným pro lepší krytí špionážních aktivit. Pravděpodobnost něčeho takového ovšem považuji za relativně nízkou.

Vezměme nejdříve možnost, že až po incidentu byly dodatečně vytvořeny protiizraelské články mající ukazovat na levicový aktivismus zadržených. Speciálně u Bauera by to znamenalo spolupráci etablovaných médií (televize Al-Džazíra, časopisů The Nation a Mother Jones), přičemž tato média by riskovala svou věrohodnost v případě odhalení toho, že publikací antedatovaných článků participovala na pokusu oklamat íránskou justici. Pravděpodobnost, že se k něčemu takovému každé z uvedených médií nechá přesvědčit, aby tak pomohlo lidem, kteří velmi dobře mohou být skutečnými špiony, odhaduji na 1/1 000, dohromady u všech tří zvlášť 1:10⁹.

Pravděpodobnější se zdá druhá možnost, a to, že zadržení byli agenty tajné služby produkující podobné materiály jako součást svého krytí. Tím dostávám automaticky faktor 1/2 (při apriorním odhadu počtu špionů jsem uvažoval, že pouze polovina špionů jsou zaměstnanci tajných služeb a druhá jsou vojáci příležitostně vyslaní na zpravodajskou akci). Dále je třeba uvážit otázku, jak často dostávají špioni podobný druh krytí. Samozřejmě se nabízí slavné případy agentů, kteří si budovali falešný obraz loajality k nepříteli, jako byl třeba Richard Sorge. Většina špionů ale pravděpodobně spoléhá spíš na nenápadnost než na falešnou loajalitu; druhá možnost představuje větší riziko prozrazení. Navíc, zdánlivý propalestinský aktivismus se může hodit někomu, kdo chce sbírat informace mezi propalestinskými aktivisty; již méně je vhodný pro agenta snažícího se proniknout do Íránu, nota bene nelegálním přechodem přes horskou hranici. Dávám 10% jako relativní počet špionů zaštiťujících se falešným ideovým profilem v rámci všech špionů, spolu se zmíněnou polovinou to dává 1/20. Falšený ideový profil nemusí nutně znamenat propalestinský aktivismus vedený z anarchisticko-levicových pozic; špioni se mohou vydávat třeba za konvertity k islámu, neonacisty, maoisty. Těžko měřit počet různých ideových profilů, ale když už jsem zmínil čtyři, dám faktor 1/4. Dohromady P(I₇|Š) = 1/100 (v předchozím odstavci diskutovaná pravděpodobnost, že aktivismus neexistoval a jeho důkazy jsou podvrh, je tak malá, že nehraje roli). Pravděpodobnost P(I₇|¬Š), tedy že náhodný turista v Kurdistánu bude propalestinským aktivistou, odhaduji na 1/10. Dohromady mám věrohodnostní poměr 1/10, a protože předchozí úvahy dovedly šance hypotézy Š na zhruba 1:1, po zohlednění posledních informací mi vychází její šance na 1:10, a tedy P(Š) = 9%.

Začne-li se čtenář vrtat v mých odhadech, téměř jistě nalezne spoustu slabých bodů. Odhady jsou založeny na hrubých zjednodušeních a mnoho z nich je „vaření z vody“. Navíc se dá čekat, že jsem zapomněl na některé relevantní spekty případu nebo se dopustil zbytečných hloupých chyb. Z větší části je to daň za to, že jsem odhadování nevěnoval příliš mnoho času. I tak se ovšem nejedná o úvahu, kterou bych měl hotovou za pět minut, což je nakonec vidět i z rozsahu článku. Musel jsem přemýšlet, co je relevantním faktem a co nikoli, rozhodnout, jaké informace jsou navzájem závislé a jaké nezávislé, vyhledat si některá čísla. Vzniklý konglomerát reprezentuje to, čemu se někdy říká Fermiho výpočet: řádový odhad neznámé veličiny založený na řadě hrubých aproximací snáze odhadnutelných čísel. Doufám tedy, že je jasné, že poselstvím tohoto článku není udaný odhad pravděpodobnosti toho, že v Íránu odsouzení Američané jsou špioni — naopak očekávám, že mnoho částečných pododhadů přehodnotím, dostanu-li od čtenářů rozumnou zpětnou vazbu. Poselstvím je ilustrovat, jak takové odhadování pravděpodobnosti vypadá.

Očekávám, že větší než malá část čtenářů si po přečtení tohoto článku pomyslí: „Vždyť je to propagace pusté spekulace! S takhle nespolehlivými odhady můžu dojít k jakémukoli výsledku! Skutečně platí garbage in, garbage out.“ Souhlasíte-li s tímto názorem, máte z velké části pravdu. Ano, složité situace jsou odhadovány na základě nejistých, spekulativních úvah. Druhým poselstvím tohoto článku je ukázat, jak nejistý úkol je odhadování pravděpodobností, a jak obtížné je postavit úvahu, která je skutečně dobře podložená.

Dojem spekulativnosti a nejistoty pramení především z toho, že jsem výsledný odhad získal z řady dílčích čísel a u každého z nich jsem celkem otevřeně přiznal, že buď není podloženo ničím objektivním, nebo pochází z hrubé aproximace. Je také jasné, jaká všechna fakta jsem vzal v úvahu a jaká fakta jsem ignoroval. Jinak řečeno, hrál jsem s otevřenými kartami. Chce-li kdo nyní můj odhad atakovat, nemusí pracně hledat slabiny mezi řádky, protože má řadu odhalených míst, do kterých se může strefovat. Kdybych se chtěl postavit do snadno bránitelné pozice, mohl bych říct něco ve stylu: „podle mého soudu je velmi nepravděpodobné, že hypotéza Š platí, a mám k tomu argumenty A, B a C“. Měl bych volnost v dodatečné interpretaci toho, co znamená „velmi nepravděpodobné“. Měl bych možnost, kdyby mi oponenti sestřelili A, B a C, vytasit argument D a tvářit se, že jsem s ním stále počítal a pouze jsem o něm nemluvil. Kdyby oponenti vytasili protiargumenty, mohl bych se stále tvářit, že mé argumenty jsou silnější, jelikož by nebyla k dispozici míra specifikující sílu argumentů. Mohl bych se zaštiťovat „zdravým rozumem“ nebo zkušeností, moje pozice by byla snáze obhajitelná a především díky tomu by působila jistějším dojmem.

To ovšem neznamená, že by takový odhad byl spolehlivější.

Člověk pravděpodobně vyhodnocuje spolehlivost výroku podle toho, jak snadnou se jeví možnost na něj zaútočit. To dává výhodu názorům, které jsou neurčité a jejichž odůvodnění jsou skrytá. Pro úspěch politické debaty je velmi nemoudré odkrývat své karty; je-li cílem znemožnit protivníka, je třeba zabývat se slabinami jeho názorů a pokud možno držet ty vlastní ve stínu. Je-li ale cílem hledání pravdy, je vhodné hrát otevřeněji. Diskuse tak může být věcnější, nalezení problematických bodů je výrazně rychlejší a jejich urputná obhajoba je těžší. Odměnou je nakonec názor, který je podložen něčím víc, než jen zatvrzelostí svého nositele. Názor, který skutečně vyplývá z podpůrných argumentů, stojící v kontrastu s názory vytvořenými na základě okamžitého dojmu, k nimž se podpůrné argumenty hledají dodatečně.

Otevřená hra vyžaduje disciplínu od obou stran. Byl bych rád, kdyby komentátoři u tohoto článku dodržovali následující pravidla:

• Pokud nesouhlasím, napíšu konkrétně a jasně s čím nesouhlasím a proč. Nepíšu příliš obecné a vágní námitky.
  
• Nezdá-li se mi některý z odhadů pravděpodobností, uvedu vlastní hodnotu, kterou považuji za správnější.
  
• Jestliže se domnívám, že článek ignoruje důležitý fakt, uvedu i věrohodnostní poměr, kterým tento fakt působí na celkovou pravděpodobnost.
  
• Řadím své námitky od nejpodstatnější k nejméně podstatné.
  

Poznámky:
1. Názorová zaujatost je univerzální lidská konstanta. Předchozí věta lehce přehání užitím slova konstanta; jsou samozřejmě mezi námi choleričtí fanatici i umírnění flegmatici, ale množství těch, kdo o sobě nepravdivě prohlašují, že mají otevřenou mysl a jsou prosti zaujetí, řádově převyšuje množství těch, kteří jsou alespoň schopni své zaujetí ovládnout pro účely civilizované debaty. Jestli neexistuje jediný výrok, který má moc vás urazit, pak jste prosti zaujetí — pochybuji ovšem o tom, že neexistuje.

Vězňovo dilema - výsledky turnaje

Jsou zde výsledky turnaje v opakovaném vězňově dilematu! (Pokud nevíte oč jde, přečtěte si příspěvek, ve kterém byl turnaj avizován, nebo alespoň jeho konec. Pravidla jsou popsána tam.)

Sešlo se celkem jedenáct soupeřících strategií (dvanáctá přišla pozdě a bude tak vyhodnocena pouze neoficiálně). Následuje seznam strategií.

Strategie jsou očíslovány v pořadí, v jakém jsem je obdržel. Jméno autora uvádím prioritně to, o jaké požádal. Nevyjádřil-li autor preference, uvádím jméno, které jaké používá ke komentování na tomto blogu. Jestliže autor dosud nekomentoval, nebo pokud se mi nepodařilo přiřadit mejl k přezdívce komentátora, uvádím jméno uvedené v mejlu. Jeden autor požádal o anonymitu. Omlouvám se, pokud jsem špatně doplnil diakritiku u jmen, která došla bez ní.)

• S1 (zaslal Matúš Šimkovič): Pokud jsem v minulém tahu spolupracoval, nechť p je relativní četnost soupeřových spoluprací po mé spolupráci. Pokud jsem zradil, nechť p je četnost soupeřovy spolupráce po mé zradě. Nelze-li tyto relativní četnosti spočítat, nechť p = 1/2. Nechť dále E_s = 5p - 7 a E_z = 6p - 6. Spolupracuji s pravděpodobností exp E_s / (exp E_s + exp E_z).
  

Pravděpodobně se jednalo o nejzajímavější strategii a za pozornost stojí i autorův doprovodný komentář, k němuž se ještě vrátím po uvedení výsledků.

Pravdupovediac nemám veľké očakávnia čo sa týka úspechu tohoto modelu, hlavne tá markovská sieť je veľmi tupý model, HMM alebo niečo komplexnejšie by dávalo väčší zmysel. Myslím, že skôr bude zaujímavé ako si povedie probabilistický model proti tým deterministickým. Teda vo vzájomných zápasoch. Evolúciu je veľmi ľahké vyhrať pomocou nepotizmu (pozdravný kód na začiatku série a potom spolupracovať so súkmeňovcami).

Další strategie:

• S2 (zaslal čtenář Stan): Zrazuji, pokud soupeř zradil alespoň třikrát, nebo pokud zradil v prvním tahu. Jinak spolupracuji.
  
• S3 (anonymní): V prvním tahu zradím a v druhém spolupracuji. Jindy, pokud v předchozích dvou tazích soupeř hrál stejně, hraji to, co hrál soupeř v předchozích dvou tazích. Pokud soupeř hrál různě, hraji opak toho, co jsem sám hrál v minulém tahu.
  
• S4 (zaslal Adam Pekár): Spolupracuji v prvních třech tazích, zrazuji v posledních dvou. Jindy spolupracuji, právě tehdy když soupeř spolupracoval aspoň v 85% tahů.
  
• S5 (zaslal čtenář Satai): Spolupracuji v prvních třech tazích, zrazuji v posledním. Jindy spolupracuji s pravděpodobností rovnou relativní četnosti spolupráce soupeře.
  
• S6 (zaslal Martin Nuhlíček): V prvním tahu spolupracuji, jindy hraji to, co soupeř v minulém tahu. Po první zradě soupeře ovšem spolupracuji.
  
• S7 (zaslal čtenář Tasselhof): V prvním tahu hraji náhodně. V 2n. a 2n+1. tahu hraji to, co soupeř hrál v n. tahu.
  
• S8 (zaslal Matej Kačaljak): Zradím, pokud je splněna aspoň jedna z podmínek: a) soupeř zradil aspoň ve dvou ze tří předchozích tahů, b) pokud jsem sám v předchozím tahu zradil a předtím spolupracoval, c) pokud jsem nezradil ani jednou v předchozích deseti tazích. Vždy spolupracuji v tazích 20, 40, 60 a 80.
  
• S9 (zaslal Ladislav Dolinka): Mám dvě podstrategie. První je zradit právě tehdy když soupeř zradil v obou předchozích tazích (v prvních dvou tazích spolupracuji), druhá je zradit vždy po první zradě soupeře. Začnu první podstrategií. Po každém desátém tahu zjistím, zda můj zisk za posledních deset tahů leží mezi 16 a 34 body, pokud ano, vyměním podstrategii. Po výměně strategie vynuluji počítače zrad.
  
• S10 (zaslal Milan Mach): Tahy 1 a 2: spolupracuji. Tahy 3-29: hraji to, co soupeř v minulém tahu. Tahy 30-84: zradím, pokud soupeř zradil aspoň osmkrát, jinak hraji to, co soupeř v minulém tahu. Tah 85: zradím. Tahy 86 a 87: zradím, pokud soupeř zradil aspoň osmkrát, jinak spolupracuji. Tahy 88-97: Pokud soupeř zradil v tahu 87 nebo pokud zradil aspoň čtyřikrát, zradím, jinak spolupracuji. Tahy 98-100: zradím.
  
• S11 (zaslal Jan Mrzena): Tah 1: spolupracuji. Tah 2: dělám to, co soupeř v rahu 1. Tah 100: zradím. Jindy: když soupeř v minulém tahu zradil a já jsem spolupracoval v předminulém, nebo když soupeř zradil ve dvou předchozích tazích, zradím, jinak spolupracuji.
  

Po termínu došla klasika:

• S12 (zaslal čtenář benep9am): V prvním tahu spolupracuji, jindy hraji to, co soupeř v minulém tahu.
  

No a nakonec zde byla automaticky nasazená Plně náhodná strategie:

• S0 (automaticky ve hře): Spolupracuj s pravděpodobností 50%.
  

Ligový turnaj

Výsledky zápasů ligového turnaje a konečné pořadí jsou uvedeny v následujících tabulkách:







Vítězem se stala strategie S2, kterou zaslal čtenář Stan. Blahopřeji.

Neoficiální turnaj s účastí pozdě došlé strategie S12 by dopadl takto:





Rozdíly v pořadí (například výrazný posun S11 nahoru v druhé tabulce) jsou dány nejen účastí další strategie, ale i vlivem náhody. Při testování jsem turnaj nechal proběhnout několikrát a pořadí v čele se měnilo pokus od pokusu. (Tento fakt mě činí zranitelným vůči obvinění, že jsem simulaci opakoval tak dlouho, než dopadla tak, jak jsem si přál. Jako důkaz toho, že jsem to nedělal, mohu nabídnout pouze své slovo.)

Na co náhoda naopak vliv neměla, to je postavení strategií na chvostu, kde se usídlila má oblíbená S1 a spolu s ní S8. Tyto strategie dokonce dopadly hůř, než náhodná S0. Důvodem je přílišné zrazování. Tyto strategie sice vyhrávají většinu svých zápasů, ale vyhrávají je s malým celkovým ziskem. Mluví o tom jedna z Axelrodových zásad pro podobné hry: nebýt závistivý. Závistivostí se zde myslí touha mít víc bodů, než každý ze soupeřů ve vzájemné konfrontaci. To vede ke zkáze; mnohem lépe si vedou ti, kdo se spokojí s prohrou za oboustranně výhodnějších podmínek.

Druhé poučení je: nerozhodujte se náhodně. Nejlepší probabilistická strategie S5 je podprůměrná, S1 na své využívání náhodného generátoru doplatila ještě výrazněji. Házení kostkou do optimálního rozhodování nepatří.

Evoluční turnaj

Jak se dařilo strategiím v dlouhodobém přežívání? Výsledky jsou mírně odlišné od jednorázového turnaje. S2 získávala své úspěchy proti S0 a dalším náhodně zrazujícím strategiím. Ty však velmi rychle vyhynuly a zhruba od patnácté generace začíná S2 ztrácet. Evoluční turnaj vyhrála strategie S10, jejímu autoru blahopřeji! Konečné pořadí a graf následují:







(V grafu je S0 černá a ostatní jsou barveny od červené po zelenou, S1 je nejčervenější a S11 nejzelenější.) Strategie vymíraly v tomto pořadí: S1 a S8 (8. generace), S0 (9. generace), S5 (25. generace), S3 (28. generace), S7 (38. generace).

Sto generací byla příliš krátká doba nato, aby došlo ve vývoji k dramatickým zvratům. Možná by stálo za to nechat simulaci běžet déle. To jsem učinil, ovšem již ne pouze s jedenácti strategiemi figurujícími v této soutěži, ale s výrazně větší množinou strategií.

Československo proti zbytku světa

Samozřejmě mě zajímalo, jak by si vedli čtenáři tohoto blogu v konfrontaci s nějakou jinou skupinou. Uspořádal jsem tedy soutěž podle úplně stejných pravidel na blogu LessWrong [*], jehož mezinárodní čtenářská obec je o poznání rozsáhlejší než zde. Soutěže se zúčastnilo 21 strategií (plus Plně náhodná). Výsledky tamního turnaje a popis účastnických strategií najdete pod tímto odkazem. Zde uvedu pouze výsledky turnaje s účastí všech strategií, tj. jedenácti zdejších a jednadvaceti konkurenčních. Naše strategie jsou tentokráte označeny C1-C11, náhodná Z, konkurenční strategie pak vystupují pod písmeny A-U [*].




V ligovém turnaji se našim strategiím vedlo se střídavými úspěchy. Celkově naše strategie získaly v průměru 9297 bodů na zápas, konkurence pak 9702 bodů. Nejlépe dopadla jedenáctka na pěkném třetím místě, nejhůře se naopak dařilo jedničce, která ale stále nechala za sebou strategie označené jako U, Q a L. L byla strategie „vždy zraď“. U byla velmi podobná naší S1 (neboli C1): probabilistická strategie snažící se analyzovat pravděpodobnost, že soupeř zradí, spočítat střední zisk, a nakonec si hodit kostkou. Strategie P, Q a U se taktéž pokoušely o nepotismus: tj. spolupracovat s kopiemi sebe sama a zrazovat ostatní. To samozřejmě bylo málo platné v ligovém turnaji, kde se strategie samy se sebou nepotkaly, ale mělo to pomoct v turnaji evolučním.

V evolučním turnaji se z našich nejlépe dařilo S11. Následuje pořadí po sté generaci.







(Naše strategie jsou v grafu červené.)

I zde bylo sto generací příliš málo k tomu, aby se mohly projevit zvraty, kdy úspěšná strategie vyhubí svou hlavní „potravu“ a jakmile nemá koho vykořisťovat, začne sama vymírat. Proto jsem nechal stejnou simulaci běžet po dobu tisíce generací, a obrázek je mnohem zajímavější:





Na začátku vidíme přibližně stejný obrázek jako na předchozím grafu. Dokonce se na chvíli dostala do čela naše S11, potom se ovšem začíná projevovat změna prostředí, kdy vymírá řada neúspěšných strategií, a dopředu se dostávají strategie I a S4; S11 nakonec vymírá někdy po pětisté generaci. Ve hře zůstávají pouze I, S4 a O. Strategii O se nedařilo zrovna slavně na začátku turnaje, ale v okamžiku, kdy jedinými soupeři jsou I a S4, začíná profitovat. Strategie O totiž zradí již v devadesátém osmém tahu, zatímco I a S4 až v devadesátém devátém. Díky tomu získá O ve vzájemných zápasech s I a S4 o sedm bodů navíc, a tento rozdíl stačí k jejímu úspěchu. Kdyby se nechala simulace běžet o něco déle, zůstala by jedinou přeživší strategií.