Blcha v meste

Nasledovná jednoduchá úloha ma dnes napadla pri čítaní učebnice teórie informácie. (Matematickým základom teórie informácie je teória pravdepodobnosti.)

Blšia krajina je tvorená n dedinami rozmiestnenými vo vrcholoch pravidelného n-uholníka a jedným mestom. Keď sa blcha nachádza v dedine, skočí buď do niektorej z dvoch najbližších susedných dedín, alebo do mesta (každú z týchto troch možností si vyberá s pravdepodobnosťou 1/3). Ak je blcha v meste, skočí náhodne do niektorej z dedín (každú si volí s rovnakou pravdepodobnosťou). Predpokladáme, že blcha urobí jeden skok každú minútu a samotný skok trvá zanedbateľný čas. Blcha už takto skáče veľmi dlho. Odhadnite, s akou pravdepodobnosťou sa blcha práve nachádza v meste.

Na obrázku je ilustrovaná blšia krajina s n=6. Túto úlohu vie mechanicky vyriešiť každý, kto absolvoval prednášku z Markovovych reťazcov, ale s malým nápadom sa dá vyriešiť aj bez akejkoľvek vyššej matematiky.

Poznámka 31.7.: Trochu to zadanie upresním. Označme ako p_n pravdepodobnosť, že po n skokoch sa bude blcha nachádzať v meste. Dá sa ukázať, že nezávise na tom, kde blcha svoje skoky začala, konverguje postupnosť p₁, p₂, p₃, ... k pevnému číslu. Pýtame sa práve aké je to číslo.

Archimedov problém

S nasledovným problémom som sa prvýkrát stretol v Gardnerovej zbierke matematických hlavolamov. Túto úlohu však riešil a správne vyriešil už Archimedes. Ja som si ňou lámal hlavu vyše pol hodiny, kým som zistil, aká je triviálna :-)

Uvažujme dva nekonečne dlhé valce, oba s priemerom 1, ktorých osi sa pretínajú pod pravým uhlom. Aký je objem telesa zodpovedajúceho prieniku týchto dvoch valcov?

Hádanky z Wordle

Program Wordle je založený na jednoduchom, no veľmi peknom nápade: Z akéhokoľvek vstupného textu urobí "oblak slov", pričom veľkosť jednotlivých slov je určená ich frekvenciou výskytu v danom texte. Farby, pozíciu a niekoľko ďalších vlastností výsledného oblaku si môžete sami nastaviť. Jednoducho príjemná zábava na daždivé dni. Dnes ma však napadlo, že pomocou Wordle sa dajú vyrobiť aj originálne hádanky.

Nasledujúce oblaky slov zodpovedajú stručným životopisom štyroch významných Rakúšanov. Viete odhaliť, o ktorých ľudí sa jedná?

Keď na obrázky kliknete, tak sa zväčšia. Aj menšie slová môžu znamenať rozhodujúcu nápovedu.

Skladanie kocky

K dispozícii máme neobmedzený počet kvádrov veľkosti 1×1×4, z ktorých chceme zlepiť (plnú) kocku veľkosti n×n×n. Pre ktoré n je to možné? (Pochopiteľne, žiadny kváder nemôžeme rozpíliť na menšie kúsky :-)

Päť miest na sfére

Nasledovné tvrdenie sa mi zdá "intuitívne zrejmé", ale nedarí sa mi ho elegantne dokázať. (Súvisí priamo s jedným problémom na Peťovom blogu). Možno budete vy úspešnejší.

Na jednotkovej sfére S je 5 miest, pričom žiadne tri z nich neležia na spoločnej hlavnej kružnici. Ak spojíme najkratšou cestou každé mesto s každým (samozrejme po povrchu), tak sumárna dĺžka všetkých ciest bude menšia ako 6π.

Poznámka 1: Ľahko sa dá ukázať, že súčet dĺžok všetkých ciest je menší ako 20π/3. Totiž ak si označíme ako d_ij vzdialenosť miest i a j, tak máme:

Nerovnosť plynie z očividnej vlastnosti, že obvod akéhokoľvek trojuholníka na sfére je menší ako 2π.

Poznámka 2: Sériou trikov už viem dokázať dokonca nasledovné zovšeobecnenie pre akýchkoľvek n bodov (nielen 5) a to na akejkoľvek jednotkovej sfére (nielen v trojrozmernom priestore):


kde α je 0 pre párne n a 1 pre nepárne n. Ale stručný dôkaz neviem ani v špeciálnom prípade n=5, takže sa teším na vaše nápady.

Buffonov rez sféry II

Keďže Ruziklan už predchádzajúcu úlohu vyriešil, môžem formulovať zamýšľané zťaženie. Kto príde ako prvý so správnym riešením, ten má u mňa fľašu whisky. (A to je už iné kafe ako pivo, nie?)



Na povrchu jednotkovej sféry S máme tri body A,B,C, pričom vzdialenosť AB označme c, vzdialenosť AC označme b a vzdialenosť BC označme a (samozrejme, vzdialenosti opäť berieme po povrchu sféry). Sféru S náhodne rozpolíme rovinným rezom na dve rovnako veľké hemisféry. V závislosti od vzdialeností a,b,c, aká je pravdepodobnosť, že po vykonaní tohto rezu sa budú všetky tri body nachádzať na spoločnej hemisfére?

Buffonov rez sféry

Dnes som pre Vás vymyslel trochu ťažšiu úlohu, ktorá pripomína problém o Buffonovej ihle. Riešenie je celkom pekné a naviac táto úloha je môj vlastný nápad. Doslova sa čudujem, ako je možné, že som sa s ňou ešte nestretol v žiadnej z tých desiatok kníh z teórie pravdepodobnosti, ktoré používam. Kto príde ako prvý so správnym riešením (aj s odôvodnením; napíšte ho do komentárov, alebo mi pošlite mail), ten má u mňa pivo. Alebo aj tri.


Nech S je jednotková sféra, čím rozumieme povrch trojrozmernej gule s polomerom 1. Na S sú vyznačené dva body A a B, ktorých vzdialenosť je h. (Vzdialenosť počítame po povrchu sféry S, t.j. h je dĺžka sférickej úsečky AB.) Sféru S náhodne rozpolíme rovinným rezom na dve rovnako veľké hemisféry. Aká je pravdepodobnosť, že body A a B sa po vykonaní tohto rezu budú nachádzať na spoločnej hemisfére?

Haruki Murakami: Kafka on the Shore

Je zbytočné, aby som tu podrobne analyzoval Murakamiho bestseller "Kafka on the shore". Totiž, nalejme si čistého vína, akokoľvek dlho by som sa snažil, tak pre Vás nevyprodukujem nič lepšie, než je jednoduchý odkaz na recenziu napísanú Johnom Updikom^†. Čo však môže byť prínosom tohto príspevku je popis mojich subjektívnych myšlienok, ktorých som sa pri čítaní tejto knihy nevedel zbaviť; popis výsledku interakcie Murakamiho emotívnej prózy a mojej cvičenej, často zámerne chladnej racionality.

Knihy plné metafyzických úvah, mystiky a metafor sú založené na tom, že my ľudia sme v zásade veľmi podobní^‡. Žijeme však v dobe zmien dotýkajúcich sa podstaty nášho bytia, v dobe, ktorá celkom určite onedlho spôsobí zmenu nášho zmyslového vnímania a priestoru mentálnych stavov.

Budú vôbec naši vzdialení potomkovia schopní stotožniť sa s našimi emóciami? Budú schopní pochopiť našu iracionalitu, naše "emotívne qualia", čiže čosi, čo sa nedá odmerať, zapísať a objektívne študovať, niečo, čo je natoľko subjektívne, že sa dá len zažiť? Budú súčasné umelecké diela v ľuďoch evokovať aj čosi iné ako množstvo faktov a dedukcií, prípadne myšlienok úplne nekompatibilných s našim archaickým wetwarom?

Ako sa domnievajú niektorí futurológovia, možno žijeme v záverečnom štádiu doby klasickej smrteľnosti. Po explozívnom náraste našich vedomostí sa možno už za niekoľko desiatok rokov bude počítať očakávaná doba ľudského života na storočia; za niekoľko desiatok rokov, čo je z hľadiska mnohotisícročnej doby existencie ľudstva ako nešťastná smrť v okamihu tesne pred otvorením brány do raja. Sú tu však naše archaické emotívne qualia, pocity viazané na náš svet tu a teraz, ktoré sú z hľadiska vývoja ľudstva výnimočné a neopakovateľné. A to aj preto, že je tu každý z nás len krátko.

---

^†Môžem však dodať, že slovná zásoba potrebná na plynulé čítanie je tejto knihy je malá, teda aspoň v porovnaní s väčšinou iných kníh anglicky písanej beletrie. Samozrejme, aj túto knihu Vám rád požičiam; stačí sa zastaviť u mňa v kancelárii.

^‡Takmer každý semester opakujem jeden klasický príklad z teórie pravdepodobnosti, pričom pred určitým krokom sa zakaždým zastavím a spýtam sa študentov na jeden technický detail. Skoro vždy dostanem tú istú odpoveď, ktorá je ... nesprávna. Jedná sa pritom o skutočnú matematickú banalitu. Ľudia sú si skrátka podobní aj opakovaním rovnakých chýb.

Chlapec, dievča a pes

Nasledovná úloha pripomína príklady pre stredné školy. Nebude problém vyriešiť ju úplne mechanicky. Alebo áno?

Chlapec, dievča a pes vychádzajú zo spoločného bodu na rovnej ceste, pričom chlapec pôjde celý čas rýchlosťou 6 kilometrov za hodinu, dievča 4 kilometre za hodinu a pes bude kmitať medzi chlapcom a dievčaťom rýchlosťou 10 kilometrov za hodinu. (T.j. keď pes dobehne chlapca, tak sa okamžite otočí a bude bežať konštantnou rýchlosťou 10 km/hod k dievčaťu, keď dobehne k dievčaťu tak sa okamžite otočí a bude bežať konštantnou rýchlosťou 10 km/hod ku chlapcovi a tak ďalej.) Ako ďaleko od štartu sa bude nachádzať pes po jednej hodine?

Táto úloha je z už viackrát spomínanej knihy Martina Gardnera. Teším sa na Vaše riešenia.

Presviedčacia sila faktu

Matematický aparát teórie pravdepodobnosti obvykle používame na kvantifikáciu "objektívnej neurčitosti" týkajúcej sa výsledkov experimentu. V tomto príspevku však budeme interpretovať pravdepodobnosť tak, ako ju vidia Bayesisti, t.j. ako mieru "subjektívnej dôvery" v pravdivosť hypotéz.

Predstavme si napríklad, že rozhodca hodil mincou. Napriek tomu, že o výsledku tohto hodu je už rozhodnuté, z môjho subjektívneho hľadiska je miera dôvery, že padol znak, rovná 1/2. To platí až do okamihu, keď o výsledku získam nejakú informáciu. Až vtedy sa moja subjektívna miera dôvery zmení a to v závislosti od toho, akú informáciu som získal. Napríklad ak by som sa na vlastné oči presvedčil, že padol znak, tak sa moja miera dôvery zmení na jednotku a ak by mi tento výsledok len niekto oznámil, tak by sa moja subjektívna miera dôvery v to, že padol znak, mohla zmeniť na hodnotu nižšiu ako jedna. V tomto druhom prípade by totiž jediným úplne istým faktom bolo pre mňa to, že mi nejaký človek oznámil, že padol znak, čo je, ako uznáte, nie vždy to isté, ako že znak naozaj padol.

Vo všeobecnosti môžeme teda povedať, že akonáhle sa človek dozvie novú informáciu, nastane zmena jeho osobného pravdepodobnostného modelu sveta.

Pre človeka c označme symbolom Pc jeho pravdepodobnostný model sveta a nech H je nejaká hypotéza. Ako Pc(H) označíme mieru dôvery človeka c v platnosť hypotézy H, čo je číslo medzi 0 a 1. Pochopiteľne, Pc(H)=1 znamená, že c si je istý, že H platí a Pc(H)=0 znamená, že c si je istý, že H neplatí. Slovným spojením "preferencia hypotézy H človekom c pred negáciou hypotézy H", alebo stručnejšie "preferencia hypotézy H" nazveme hodnotu


kde !H je označenie logickej negácie hypotézy H. (Kladieme log(0/1)=-∞ a log(1/0)=+∞.) Všimnite si, že čím je väčšia miera dôvery Pc(H), tým je väčšia aj preferencia (H:!H)c a naopak, avšak preferencia môže na rozdiel od dôvery nadobúdať všetky možné číselné hodnoty, ako kladné, tak aj záporné. Naviac, preferencia hypotézy s pravdepodobnosťou 1/2 (pred jej negáciou) je nulová, čo je plne v súlade s intuitívnou predstavou o tomto pojme.

Dá sa ukázať, že ak človek dodržuje všetky pravidlá racionálneho uvažovania, tak sa jeho preferencia hypotézy H musí po zistení faktu F zmeniť nasledovne:


kde Pc(F|H) (a Pc(F|!H)) je miera očakávania platnosti faktu F za predpokladu, že by hypotéza H bola pravdivá (resp. bola nepravdivá). Pravý člen vo vzťahu vyššie teda určuje o koľko fakt F zmení človeku c preferenciu hypotézy H. Túto hodnotu môžeme teda nazvať "presviedčacia sila" faktu F v prospech hypotézy H.

Všimnime si, že fakt F zvyšuje presvedčenie človeka c o platnosti hypotézy H vtedy, keď je pre neho fakt F očakávateľnejší za predpokladu platnosti hypotézy H, než za predpokladu neplatnosti hypotézy H.

Pozrime sa na niekoľko príkladov:

Človek: Ja. Fakt: Moja manželka mi oznámila, že vonku prší. Hypotéza: Vonku naozaj prší. Presviedčacia sila faktu o danej hypotéze: Hodnota Pc(F|H), t.j. moje očakávanie, že mi manželka oznámi, že prší, ak naozaj prší, nie je nijako vysoká. Ale hodnota Pc(F|!H), t.j. pravdepodobnosť, že mi manželka oznámi, že prší, ak by v skutočnosti nepršalo, je extrémne nízka (zrak má dobrý a zmysel pre humor má normálny). Pomer týchto hodnôt je teda veľké číslo a preto aj presviedčacia sila daného faktu o tom, že prší, je veľmi vysoká.

Človek: Ja. Fakt: Vidím nejaký lietajúci tanier. Hypotéza: Vidím lietajúci tanier, v ktorom sú skutoční mimozemšťania. Presviedčacia sila faktu o danej hypotéze: Ak by som videl lietajúci tanier, v ktorom sú skutoční ufóni, tak je logicky jasné, že by som videl nejaký lietajúci tanier, t.j. Pc(F|H)=1. Avšak ak by aj nebola pravda, že vidím lietajúci tanier, v ktorom sú skutoční mimozemšťania, tak pravdepodobnosť, že vidím nejaký lietajúci tanier, nie je zďaleka 0, t.j. Pc(F|!H)>>0. (Môj pravdepodobnostný model totiž zahŕňa ten fakt, že sa nachádzam v zábavnom parku Gardaland.) Presviedčacia sila daného faktu o hypotéze skutočných mimozemšťanov je teda nenulová, ale pomerne malá a vzhľadom na moju mizivú apriórnu dôveru v UFO ma žiadna hystéria nechytá. (Iná situácia by však bola, ak by som sa práve nachádzal na Chopku).

Človek: Ja. Fakt: Nemenovaný politik odpovedal na otázku, či mu záleží na blahobyte občanov, odpoveďou "áno". Hypotéza: Tomuto politikovi naozaj záleží na blahobyte občanov. Presviedčacia sila faktu o danej hypotéze: Pravdepodobnosť Pc(F|H), že politik povie, že mu záleží na blahobyte občanov, ak mu na ňom naozaj záleží, je 1. Avšak pravdepodobnosť Pc(F|!H), že to povie, ak mu na blahobyte občanov nezáleží, je tiež 1. Keďže log(1/1)=0, presviedčacia sila daného faktu o nesebeckých pohnútkach politika je nulová.