TIN065 Prednáška 11

Prednášky z Vyčísliteľnosti II
Obsah
Prehľad Prvá prednáška Druhá prednáška Tretia prednáška Štvrtá prednáška Piata prednáška Šiesta prednáška Siedma prednáška Ôsma prednáška Deviata prednáška Desiata prednáška Jedenásta prednáška Dvanásta prednáška Zhrnutie na skúšku

Na tejto prednáške sme sa zaoberali náhodnosťou a viacerými pohľadmi na ňu.

Algoritmická náhodnosť

Historická poznámka

Prvý, kto sa zaoberal algoritmickou náhodnosťou bol von Mises na začiatku dvadsiateho storočia. Ten však ešte nemal k dispozícii teóriu algoritmov a preto jeho koncepcia bola vágna a bez rigorózneho podkladu.

Budeme hovoriť tradične o množinách ako o nekonečných postupnostiach núl a jedničiek. Podľa von Misesa sa náhodná postupnosť vyznačuje napríklad tým, že má limitne rovnaký počet núl a jedničiek. Problém je, že to spĺňa aj postupnosť pravidelne sa opakujúcich núl a jedničiek (a mnoho ďalších pravidelných), takže von Mises vymyslel, že nie len pre celú množinu by mal byť rovnaký počet núl a jedničiek, ale aj pre rozumne vybrané časti. Rozumne vybrané časti by v tomto prípade zodpovedali rekurzívnym podmnožinám.

Tri pohľady

V dnešnej dobe existujú tri hlavné pohľady na algoritmickú náhodnosť.

1. pohľad cez teóriu miery (a typickosť)
2. Kolmogorovská zložitosť (nestlačiteľnosť)
3. Frekvenčná stabilita (stochastičnosť)

Rozličnými spôsobmi sa snažíme brať množiny a rozhodnúť o nich, či sú náhodné.

Treba povedať, že náhodnosť je výrazne relatívny pojem. Stále ide len o náhodnosť voči daným prostriedkom. Ak príjmeme transcendentný koncept boha, tak prňho nie je nič náhodné. Čím menej ale vieme, týmviac vecí sa nám môže javiť náhodných - chaotických. My ako prostriedky použijeme ČRF (teda algoritmy) a budeme sa snažiť detekovať nenáhodnosť. Všetko ostatné pre nás bude chaos. Ako príklad silnejších prostriedkov môžeme uviesť teóriu množín, ako príklad slabších uvedieme algoritmy s obmedzenými prostriedkami (resource bounded), napríklad pracujúce v polynomiálnom čase alebo v logaritmickom priestore. Tieto prostriedky dokážu viac alebo menej detekovať náhodnosť. Náhodnosť zistiteľná polynomiálnymi prostriedkami je tiež obľúbeným predmetom skúmania.

Pohľad cez teóriu miery

Vieme, že môžeme stotožniť nula-jedničkové postupnosti s reálnymi číslami medzi nulou a jedničkou (vynecháme problémové dyadické čísla). Ak v nula-jedničkovej postupnosti poznáme prvý bit, vieme povedať, v ktorej polovici intervalu $ (0, 1) $ táto postupnosť leží. Ak poznáme (len) druhý bit, tak vieme opäť v ktorých častiach intervalu môže postupnosť ležať a tieto časti majú spolu mieru $ \frac{1}{2} $. "Asi nemusí byť človek génius", aby zistil, že ak poznáme n bitov z postupnosti, tak vieme nájsť množinu miery $ 2^{-n} $, v ktorej postupnosť leží. A ak poznáme nejakú nekonečnú zákonitosť o tej postupnosti (teda poznáme nekonečne veľa bitov), tak máme množinu miery nula, v ktorej tá postupnosť leží.

Odbočka k miere pre amatérov

Je niekoľko druhov miery a nás bude zaujímať Lebesgueova. Aj pri tej je viac spôsobov ako ju zaviesť. Základom sú racionálne intervaly, pridáme k ním ich konečné zjednotenia a potom z výsledných množín budeme vyrábať konečné aj nekonečné prieniky a zjednotenia (a stále dostaneme viac množín) a týmto vybudujeme $ \Sigma $algebru merateľných množín. A dôležitý výsledok je, že množina $ M $ má mieru $ 0 $ práve vtedy ak pre každé $ \epsilon $ existuje otvorená množina $ G $ taká, že $ M \subseteq G $ a miera $ G=\mu(G) $ je menšia ako $ \epsilon $ (označíme dôsledok hviezdičkou). V štandardnom modeli existujú nemerateľné množiny, ale v niektorých divokých modeloch sú všetky množiny merateľné.

Zákonité množiny pre nás budú teda tie, ktoré ležia v efektívne zadaných množinách miery nula a náhodnými budú tie ostatné, ktoré zostanú po vyhodení pekne zadaných množín.

Programov (a teda aj ČRF) je iba spočetne mnoho. Tým vyhodíme spočetne mnoho množín miery nula. Celkovo sme vyhodili iba množinu miery nula a zostala nám množina miery 1 náhodných (random) množín/postupností. Skoro všetky množiny sú teda náhodné.

Výsledok * (charakteristika množín miery nula s časti o miere) sa dá efektivizovať: Množina $ M $ má $ \Sigma_1^0 $ mieru nula (peknú mieru nula, zvládnuteľnú mieru nula, rekurzívne spočetne mieru nula) ak existuje algoritmus, ktorý každému $ n $ priradí program $ P_n $ taký, že $ P_n $ efektívne generuje (rekurzívne spočetnú) množinu racionálnych intervalov s mierou $ 2^{-n} $ takých, že $ M $ je ich podmnožina.

Dôsledok: Pre spočetne mnoho programov máme spočetne mnoho množín $ \Sigma^0_1 $miery nula, v miere 1 sú množiny algoritmicky náhodné.

Postupnosť je 1-náhodná ($ \Sigma^0_1 $náhodná, Martin Löfovsky náhodná), ak nemá $ \Sigma^0_1 $mieru nula.

Varovanie: Každá množina, ktorá obsahuje len jednu postupnosť má mieru nula, ale nemusí mať $ \Sigma^0_1 $mieru nula. Každá rekurzívna má $ \Sigma^0_1 $mieru nula.

Martingály

Predstavme si jednoduchú hazardnú hru. Vsadíme nejaké peniaze a s pravdepodobnosťou $ \frac{1}{2} $ sa zdvojnásobia a s pravdepodobnosťou $ \frac{1}{2} $ o ne prídeme. Zistíme, že ak spočítame priemernú výhru, nevyhrali sme nič.

Martingál (anglicky martingale) je zobrazenie F z $ 2^{<\omega} $ do $ \mathbb{Q}^+ $ také, že platí $ F(\sigma)=\frac{F(\sigma 0)+F(\sigma 1)}{2} $, kde $ \sigma 0 $ je predĺženie reťazca $ \sigma $ o nulu. Definícia viac menej hovorí, že v ďalšom pokuse budeme mať priemerne (očakávaná hodnota) rovnaké množstvo peňazí, ako sme mali v tomto pokuse.

Martingál je názov francúzskej stratégie pri hazardných hrách, ktorá spočíva v zdvojnásobovaní vkladu pri každom ďalšom pokuse.

V našom prípade sú martingály iba nejaké stratégie. Intuitívne pozorovanie je, že proti úplne náhodnej postupnosti sa nedá zbohatnúť.

Definícia: Martingál F uspeje na postupnosti A, ak $ \limsup_n F(A\upharpoonright n) = +\infty $, teda ak nekonečne veľa krát prekročí ľubovoľnú hranicu.

Pre náhodnú postupnosť je táto limita menšia ako nekonečno a zbohatúť sa nedá.

Pomocou martingálov sa dá vybudovať celá Lebesgueova miera a Ville ukázal, že trieda nulajedničkových postupností A má mieru nula práve vtedy, ak existuje martingál, ktorý uspeje na všetkých prvkoch v nej.

Platí: $ \Sigma^0_1 $náhodnosť zodpovedá práve tomu, keď vezmeme triedu všetkých rekurzívne spočetných martingálov.

Ak $ \Delta $ je trieda martingálov, tak $ A $ je $ \Delta $náhodné práve vtedy (def.), keď žiadny martingál $ F\in \Delta $ neuspeje na $ A $. Algoritmicky náhodné postupnosti sú tie, na ktorých sa algoritmickou stratégiou nedá zbohatnúť.

Podľa našej definície nám stačí zvoliť triedu martingálov a podľa toho máme rôzne "stupne" náhodnosti. Za $ \Delta $ môžeme brať všetky rekurzívne, alebo všetky rekurzívne spočetné, alebo zistiteľné v polytime a podľa toho, akú triedu martingálov vezmeme, podľa toho postupnosti klasifikujeme ako náhodné.

Kolmogorovská zložitosť

Kolmogorovská zložitosť predstavuje iný prístup k náhodnosti.Ako prvý sa týmto prístupom zaoberal Solomonoff, ale jeho práca zapadla. Neskôr to nezávisle objavili Chaitin a Kolmogorov. Ideou je, že náhodná postupnosť sa nedá zapísať menším počtom bitov, ako je dlhá ona sama. Ak budeme mať postupnosť samých núl dĺžky $ n $, ktorá zrejme náhodná nie je, tak ju popíšeme v logaritmickom priestore (konštantne veľa priestoru na zápis, že ide o nuly a ich počet v logaritmickom priestore). A tým sme skrátili jej popis. Naopak náhodnú postupnosť takto neskátime ("ak tam nie je zákonitosť, tak neostáva nič iné, ako" postupnosť opísať celú). Nemožnosť zapísať postupnosť kratším spôsobom je opäť relatívna k použitým prostriedkom (polytime, rekurzívne, $ \emptyset^{\prime}\mbox{rekurzívne} $.

Najkratší popis postupnosti $ \sigma $ je $ K_{f}(\sigma)=\min\{|\alpha|:f(\alpha)=\sigma\} $, kde $ |\alpha| $ označuje dĺžku popisu $ \alpha $ a $ f $ je popisovacia metóda (kódovanie).

Za popisovaciu metódu si môžeme vziať univerzálny turingov stroj U. Potom ak $ f $ je ČRF, tak $ K_U(\sigma)=K_f(\sigma)+\mbox{konštanta} $. Kódovanie turingovým strojom teda nie je horšie ako kódovanie nejakou ČRF.

Tato část je neúplná a potřebuje rozšířit. Prečo to je tak?

Radi by sme zadefinovali $ A $ ako náhodnú práve keď $ K(A\upharpoonright n)\geq n + c $. To nám bohužaľ nebude fungovať. Ak $ \alpha $ bude kódom $ \sigma $, tak budeme potrebovať $ |\alpha|+\log|\alpha|+c $ bitov (ten logaritmus naznačuje, že tam máme uloženú dĺžku $ \alpha $)

"A problem with Kolmogorov complexity is that we are not always able to determine where one string stops and another begins. A solution to this is to use prefix-free languages." (Lance Fortnow: Kolmogorov Complexity) - takže asi kvôli tomu potrebujeme uložiť dĺžku kódu.

Aby sme sa vyhli problémom, zavedieme "prefix-free Kolmogorovskú zložitosť". V tomto prípade platí, že ak $ \alpha $ je kódom nejakej postupnosti, tak žiaden prefix $ \alpha $ už kódom nie je.

Takže: $ K^P(\sigma)=\min\{|\alpha|:\alpha \mbox{ je prefix-free kódom }\sigma\} $

Tiež platí, že existuje prefix-free univerzálny turingov stroj.

A nakoniec veta: $ A $ je 1-náhodná ($ \Sigma^0_1 $náhodná) práve vtedy, keď je nestlačiteľná pre prefix-free Kolmogorovskú zložitosť (teda $ \forall n (K^P(A\upharpoonright n)\geq n \pm c) $, kde $ c $ je konštanta).

Toto je silný výsledok a ukazuje robustnosť pojmu náhodnosti. Z dvoch pohľadov je náhodnosť rovnaká.

Zvyšok sa nestihol.

Nejaká literatúra

• Calibrating Randomness v Bulletin of Symbolic Logic.
• Five Lectures On Algorithmic Randomness
• Kolmogorov complexity