Monte Carlo a mnohorozmerné simplexy

Uvedomil som si, že podobne ako pre hyperkocky (pozri včerajší príspevok) je možné jednoducho generovať rovnomerne rozdelené náhodné body na s-rozmerných stenách k-rozmerného jednotkového simplexu. (Pod k-rozmerným simplexom myslím množinu takých bodov (x1,...,xk), pre ktoré x1+...+xk=1 a všetky komponenty x1,...,xk sú nezáporné. V článku wikipédie sa to nazýva "standard (k-1)-simplex".) Nasledovné obrázky zobrazujú hrany (s=1) a dvojrozmerné steny (s=2) štvorrozmerného, päťrozmerného a šesťrozmerného jednotkového simplexu.

Monte Carlo a mnohorozmerné kocky

Dnes ma napadol trik, pomocou ktorého sa dajú veľmi jednoducho generovať body s rovnomerným náhodným rozdelením na s-rozmerných stenách k-rozmernej jednotkovej kocky. Na odskúšanie som si vygeneroval náhodné body na hranách (s=1) a dvojrozmerných stenách (s=2) štvorrozmernej, päťrozmernej a šesťrozmernej kocky (tesseract, penteract a hexeract). Výsledkom je celkom pekná vizualizácia, ktorá má podľa mňa navrch voči "drôteným" priemetom hrán, pretože poskytuje určitú informáciu aj o "naklonení stien". Inak celý program v jazyku R má len 10 riadkov :)

Poznámka 31.10.: Na obrázkoch je pochopiteľne len dvojrozmerný priemet daných hyperkociek; konkrétne ortogonálny priemet na náhodne zvolenú rovinu.

Konštantná šírka

V poslednej dobe mám menej času na zábavu s blogom, takže opäť len jednoduchá úloha :-)

Šírkou (ohraničeného) rovinného útvaru v smere vektora v nazvime minimálnu šírku nekonečne dlhého pásu, ktorý daný útvar obsahuje a je rovnobežný s vektorom v. Napríklad pre kosoštvorec na obrázku je s1 šírka v smere v1 a s2 je šírka v smere v2. (Menej formálna definícia je šírka tieňa daného telesa osvetlovaného z nekonečne vzdialeného zdroja v smere vektora v.) Je zrejmé, že kruh má konštantnú šírku vo všetkých možných smeroch. Otázka znie: Existuje ešte nejaký iný konvexný rovinný útvar, ktorý má šírku rovnakú vo všetkých smeroch?

Acknoweldgments: Tento problém mi zadal priateľ a kolega z Augsburgskej univerzity Thomas Klein.

Lúč

Zo štyroch zrkadiel sme zostavili štvorcovú komoru a z rohu (0,0) sme v smere bodu (x,1) vyslali lúč (pozri obrázok). Koľkokrát sa tento lúč odrazí od stien komory kým nenarazí presne do niektorého z rohov?

Poznámka: Uvažujeme idealizovaný prípad, t.j. matematicky presný štvorec, nekonečne tenký lúč a dokonalé odrazy. Napríklad ak x=0,2, tak je počet odrazov 4, ak je x=0,75 tak je počet odrazov 5 a podobne. Úlohou je popísať čo najjednoduchší postup (vzorec, algoritmus), ktorým sa dá z x dospieť k počtu odrazov. Svoje riešenia tejto úlohy (aj iných úloh) môžete napísať do komentárov.

Poznámka 27.10.: Úlohu nám už vyriešila gurama (pozri komentáre).

Sťahovanie vo Flatlande

Vo Flatlande je potrebné premiestniť objekt cez chodbu na obrázku. Nájdite objekt s čo najväčšou plochou, ktorý je touto chodbou možné premiestniť.

Poznámky: Objekt možno ľubovoľne posúvať, ťahať a rotovať, ale samozrejme nie deformovať. Napríklad je takto možné premiestniť červený trojuholník na obrázku s plochou 1 meter štvorcový. Je však možné presunúť aj objekt s väčšou plochou? Dodám ešte, že túto úlohu mám z jednej knihy (zatiaľ neprezradím z ktorej) a podľa formulácie riešenia v tejto knihe sa zdá, že dosiaľ nie je dokázané, že to ich riešenie je naozaj optimálne.

Rotujúca tanečnica

Keďže rotujúca tanečnica je už pár dní veľký hit a väčšina z Vás ju už videla, začnem in medias res.

Čierny tieň na obrázku sa samozrejme netočí ani v smere, ani proti smeru hodinových ručičiek; je to len dvojrozmerný objekt. Finta je v tom, že presne takýto tieň by tanečnica vrhala nech by sa točila v ktoromkoľvek z týchto dvoch smerov. Náš mozog pritom z tieňa automaticky rekonštruuje trojrozmerný objekt a ten sa môže točiť len v jedinom smere; skrátka si musí vybrať jednu z dvoch navzájom sa vylučujúcich alternatív (podobne je to v prípade Neckerovej kocky).

Pre ktorú možnosť sa teda náš mozog rozhodne? To nechajme pre nejaký psychologický blog, ale povedal by som, že tu môže hrať rolu "priming". V pôvodnom článku spomínané vysvetlenie na základe dominancie niektorej z hemisfér sa mi zdá byť nepravdepodobné. Totiž podľa toho vysvetlenia by som mal byť viac umelecky ako matematicky založený (tanečnica sa mi pri prvom pohľade točila v smere hodinových ručičiek). A to by som si už asi bol býval všimol.

Čo je však práve na tejto tanečnici také výnimočné? Moja odpoveď znie: Skoro nič. Ak by sme totiž rotovali akékoľvek teleso v smere hodinových ručičiek, tak jeho tieň bude presne taký istý, ako keby sme rotovali proti smeru hodinových ručičiek zrkadlovo preklopenú verziu toho istého telesa. (Všimnite si, že tanečnica má zodvihnutú ľavú nohu pri rotácii proti smeru hodinových ručičiek a pravú nohu ak ju vidíme rotovať v smere hodinových ručičiek.) Ľahko si to uvedomíme v dvoch rozmeroch napríklad pomocou tohoto obrázku:

A prečo som napísal že na tanečnici nie je skoro nič výnimočné? Pretože si myslím, že rotovať teleso-tanečnicu je obzvlášť účinné na dosiahnutie daného efektu. Sme totiž veľmi dobre prispôsobení práve na vytváranie si trojrozmernej predstavy ľudí; postavy nie sú pre nás len "nejaké" telesá, ale veľmi dôležité telesá a mozog s nimi zrejme narába trochu inak ako s inými objektmi. Je to možno niečo ako známy fakt, že tváre rozpoznávame oveľa spoľahlivejšie než iné, podobne komplexné obrazce.

Poznámka 18.10.: Tipol by som si, že ak by sme ako rotujúci objekt použili postavu, ktorá zdraví zdvihnutou rukou, tak väčšina z nás by mala tendenciu vidieť rotáciu v takom smere, aby náš trojrozmerný mentálny model mal zdvihnutú pravú ruku.

Acknowledgements: Na rotujúcu tanečnicu ma upozornil kolega Ján Somorčík.

Vymyslené hádzanie

Predstavte si, že Vám zadám na domácu úlohu hodiť 120 krát mincou a zapísať si výsledky. Toľkokrát hodiť mincou je však poriadna otrava a každý normálny študent by sa určite rozhodol jednoducho si danú postupnosť vymyslieť. Mám nejakú šancu Váš podvod odhaliť?

Skúste si to. Buď si náhádžte výsledky mincou, alebo si napíšte na papier postupnosť 120 vymyslených výsledkov H/Z (hlava/znak) a snažte sa, aby Vaša postupnosť pôsobila čo najnáhodnejšie.

Vyskytuje sa niekde vo Vašej postupnosti päť (alebo viac) rovnakých výsledkov za sebou? Ak nie, tak vitajte v klube normálnych študentov - výsledky ste si skoro určite vymysleli. Totiž pravdepodobnosť, že v 120 hodoch mincou nebude niekde aspoň 5 rovnakých výsledkov za sebou je menej ako 2 percentá...

Ukazuje sa, že veľa ľudí má predstavu o nezávislých náhodných výsledkoch vychýlenú tak, že podvedome považujú dlhšie série rovnakých výsledkov za menej pravdepodobné ako v skutočnosti sú. Táto naša chybná intuícia sa prejavuje napríklad pri rulete: Ak už dlho nepadla červená farba, tak hráči majú väčšiu tendenciu vsadiť na červenú, pretože už "predsa musí konečne padnúť" :-)

Poznámka. Existuje veľké množstvo podobných testov na "pravosť" generovania náhodných hodnôt. Napríklad: Rozdeľte svoju postupnosť 120 výsledkov na 30 úsekov po štyri výsledky a spočítajte, koľko z týchto štvoríc je typu HHHH, ZZZZ, HZZZ, ZHHH, HHZZ, ZZHH, HHHZ alebo ZZZH. Ak je takýchto štvoríc 10 alebo menej, zrejme ste si danú postupnosť vymysleli. Ak by ste totiž naozaj hádzali mincou, bola by pravdepodobnosť takéhoto výsledku približne len 0,05. To čo sme tu urobili sa v štatistickej terminológii nazýva test hypotézy o pravdepodobnosti p binomického rozdelenia na hladine významnosti 5 percent.

Poznámka 3.2.2008: Práve som zistil, že "chybná intuícia", ktorú spomínam v príspevku, má svoje meno: "Gambler's fallacy".

Pokrývanie šachovnice

Máme "šachovnicu" so 78 poliami zobrazenú na obrázku. Je ju možné úplne pokryť

a) 39 dvojpolíčkovými obdĺžnikmi ?
b) 26 trojpolíčkovými obdĺžnikmi ?
c) 26 trojpolíčkovými L-kami ?
Poznámka 7.11.: časti a) aj b) už máme vyriešené (pozri komentáre). Pre úlohu c) ešte nemáme v komentároch riešenie, ale aspoň ja som už konečne riešenie našiel :-) keď povoľujeme aj zrkadlovo otočené L-ká a samozrejme rotácie.

Green dwarf alien

Pozor, odhalenie! Pravým dôvodom misie ESA na Titan (projekt Cassini-Huygens) je nasledovný odkaz, ktorý telepaticky zakódoval nešťastný mimozemšťan do úvodu knihy "Illustrated History of Furniture" (Frederick Litchfield, 1893): GREEN DWARF ALIEN WANTS HELP. I'M ON TITAN. Nespochybniteľným dôkazom je tento obrázok (pozri zväčšenú verziu):

Kniha Michaela Drosnina "The Bible code" je podľa mňa jeden z vrcholných počinov v oblasti získavania slávy a zarábania na ľudskej senzáciechtivosti a nevzdelanosti. Podobne ako som to urobil ja, môžete si aj Vy vziať prakticky akýkoľvek text (nemusí to byť ani hebrejská biblia ako v Drosninovej knihe) a pomocou počítača v ňom nájdete desiatky podobných tajných odkazov a proroctiev. Pri experimentovaní s mojim programíkom som zistil, že zadané štvorpísmenové slovo sa v matici 50x75 písmen bežného textu dá nájsť takmer isto, päťpísmenové často a šesťpísmenové občas. (Samozrejme, závisí to na písmenách zadaného slova; slová obsahujúce Q sa obvykle nenájdu, ani keď sú krátke.) Inak celé je to možné pekne a pomerne jednoducho podložiť matematicky: aj keby sme generovali základný text úplne náhodne, tak by pravdepodobnosť výskytu zadaného ekvidištančného reťazca písmen bola pomerne vysoká. Možno si niekedy nájdem čas a stručne to pre Vás spíšem.

Blink a šachové algoritmy

Moja dnešná malá špekulácia, inšpirovaná knihou Blink, sa týka tajomstva našej schopnosti rýchleho intuitívneho ohodnotenia objektu či situácie a toho, prečo je často takéto hodnotenie presné, ale v niektorých prípadoch sa nechá oklamať jednoduchými trikmi.



Základom väčšiny šachových programov sú dva úplne odlišné "funkčné moduly". Prvý z nich je modul na vytváranie stromu popisujúceho možné vetvenie hry podľa potenciálnych ťahov. Bez tohoto modulu by program väčšinou nenašiel ani tie najjednoduchšie kombinácie. Druhý z týchto modulov slúži na heuristické ohodnocovanie pozícií a zahŕňa množstvo rôznorodých strategických faktorov odvodených z dlhodobých hráčskych skúseností. Takéto hodnotenie je pritom možné robiť mnohými spôsobmi; jeden z nich je napríklad použiť trénované umelé neurónové siete, ktoré reprezentujú informáciu len implicitne.

Naše myslenie pozostávajúce z nadväznosti vedomých krokov je možné prirovnať k postupnému vytváraniu stromu pozícií. Na druhej strane našim inštinktom a našej intuícii - automatickému, rýchlemu a ťažko zdôvodniteľnému mysleniu bez izolovateľných medzikrokov je analogické heuristické ohodnocovanie koncových pozícií umelou neurónovou sieťou. Tieto moduly našej mysli veľmi úzko spolupracujú, podobne ako je to v šachovom programe: Bez sekvenčného uvažovania by sme síce mohli existovať, ale nášmu správaniu by chýbala plánovitosť a naopak, bez inštinktov a intuície by sme len slepo brázdili priestor všetkých možností a nevedeli by sme sa nijako rozhodnúť; chýbal by nám smer a uspokojivý cieľ.

Poznámka 9.10.: Táto predstava až prekvapivo dobre zodpovedá skutočne pozorovaným prípadom patologického uvažovania z knihy A. Damasia Decartes' error; akoby moje dva metaforické moduly skutočne existovali a bolo by ich možné "vyradiť z činnosti".

Poznámka 11.10.: Práve sa v online vydaní SME v sekcii Veda objavil článok o knihe Blink v českom preklade (Okamih).

Poznámka 14.10.: Vypočujte si podcast knihy Blink (mp3).

Bláznivé percentá

Nedarí sa mi dokázať nasledovné tvrdenie.
Pomôžete mi ? :-)

V krabici sú červené loptičky, modré loptičky, červené kocky a modré kocky, pričom loptičiek a kociek je rovnaký počet. Z krabice si zoberieme 98 percent červených kociek, ale iba 88 percent červených loptičiek. Taktiež si zoberieme 80 percent modrých kociek, ale iba 76 percent modrých loptičiek. Potom istotne budeme mať viac kociek ako loptičiek.

Upozornenie: Riešenie nájdete v komentároch.

Náhodné permutácie

Náhodné permutácie sú mojou obľúbenou témou na ilustráciu základných techník v teórii pravdepodobnosti. Keď som na Wolfram demonstrations objavil programík na grafické znázorňovanie cyklov náhodnej permutácie, rozhodol som sa, že o náhodných permutáciách napíšem krátky príspevok do blogu. Možno táto téma niekoho zaujme; bola by napríklad vhodná na bakalársku (a možno aj diplomovú) prácu pre teoretickejšie orientovaného matematika.

Uvažujme postupnosť (1,2,...,n), ktorú "dokonale" náhodne premiešame, napríklad pomocou jednoduchého Fisherovho-Yatsovho algoritmu. Tým dosiahneme to, že každá z n! možných výsledných permutácií má pravdepodobnosť 1/n!. Uvedomme si, že každá permutácia rozloží množinu čísiel 1,...,n na niekoľko podmnožín zodpovedajúcich "cyklom" (pozri ilustračný obrázok vľavo hore pre n=24).

Napríklad pre n=6 má permutácia (2,1,4,6,5,3) tri cykly: cyklus „...-3-4-6-3-4-6-...“ dĺžky 3 (pretože pôvodná pozícia 3 je v novej permutácii obsadená číslom 4, pôvodná pozícia 4 je obsadená číslom 6 a pôvodná pozícia 6 je obsadená číslom 3), ďalej cyklus „...-1-2-1-2-1-...“ dĺžky 2, a cyklus „...-5-5-5-...“ dĺžky 1. Permutácia na ilustračnom obrázku má 5 cyklov dĺžok 1,1,3,5 a 14.

Z pravdepodobnostného hľadiska je práve zaujímavé študovať charakteristiky počtu cyklov a ich dĺžok v náhodnej permutácií.

Najklasickejší problém z oblasti náhodných permutácií, ktorý sa objavuje na prednáškach z pravdepodobnosti po celom svete, môžeme formulovať napríklad takto: Sekretárka náhodne rozdelí n (rôznych) listov do n (rôznych) obálok s adresami. Aká je pravdepodobnosť, že aspoň jeden list vloží do správnej obálky? V reči náhodných permutácií a cyklov sa pýtame na otázku aká je pravdepodobnosť, že náhodná permutácia n čísiel bude mať aspoň jeden cyklus dĺžky jedna. To je možné vyriešiť jednoduchou aplikáciou princípu zapojenia vypojenia. Na tomto príklade je tiež zaujímavé to, že pre n ide do nekonečna sa výsledná pravdepodobnosť blíži presne k 1-1/e.

Veľa podobných otázok je vyriešených v podrobnom článku Wikipédie pomocou techniky vytvárajúcich funkcií. Niektoré z týchto otázok sa však dajú vyriešiť oveľa elementárnejšie, priamočiarym využitím linearity strednej hodnoty. Takto je napríklad možné ukázať, že stredná hodnota počtu cyklov dĺžky k je presne 1/k (nezávisle na n). To znamená, že v priemere sa vygeneruje jeden cyklus dĺžky 1, "pol" cyklu dĺžky dva, atď. Z toho tiež okamžite plynie, že stredná hodnota počtu všetkých cyklov je n-té harmonické číslo H(n) . To je aj pre veľké n kontraintuitívne nízke číslo; napríklad stredný počet cyklov náhodnej permutácie milión čísiel je približne 14,4. Dá sa preto tušiť, že v náhodnej permutácií by sa mali s "veľkou pravdepodobnosťou" vyskytovať "veľké cykly". Skutočne to tak je; napríklad jednoduchým trikom je možné ukázať, že pravdepodobnosť výskytu cyklu obsahujúceho nadpolovičnú väčšinu čísiel je H(n)-H(n/2). (Pre jednoduchosť berieme n párne.) Hodnota H(n)-H(n/2) konverguje k číslu ln(2), čo je približne 0,693. To znamená, že pre veľké n vznikne s pravdepodobnosťou zhruba 70% v náhodnej permutácii n čísiel cyklus obsahujúci nadpolovičnú väčšinu čísiel.

Wolfram demonstrations

Bohatým zdrojom zábavy a poučenia pre matematikov všetkých kategórií je projekt Wolfram demonstrations. Stačí si nainštalovať Mathematica Player a môžete začať so skúmaním približne 1800 interaktívnych programíkov. (Mathematica Player je zadarmo, avšak na vytvorenie vlastnej demonštrácie potrebujete program Mathematica, ktorý už zadarmo nie je. Je to trochu podobné ako Acrobat Reader a Acrobat.) Väčšina demonštrácií by si zasluhovala podrobnejší komentár a určite niektorím z nich venujem v budúcnosti celý príspevok, prípadne ich použijem na výuke. Ktoré demoštrácie zaujali najviac Vás?