728 x 90

O losowości nie tylko w informatyce. Część 2

O losowości nie tylko w informatyce. Część 2

Spójrzmy na historyczny rozwój pojęcia losowości w matematyce, a – jak się nie za długo okaże – również w informatyce. W 1933 roku Kołmogorow ogłosił przyjmowaną po dziś dzień praktycznie bez zmian aksjomatykę prawdopodobieństwa. Jednak już wcześniej Markow używał procesów stochastycznych, zwanych łańcuchami, do analizy statystycznej tekstu. Wcześniej też Gosset stosował słynny rozkład t-Studenta do badania jakości piwa metodami statystycznymi. Pora więc była najwyższa uporządkować ten zakątek matematyki, traktowany wcześniej jako dział fizyki i obiekt zainteresowań hazardzistów. (I chyba nie aż tak wiele się zmieniło od tamtych czasów).

Pierwsze próby wyrażenia w ogólności czym jest prawdopodobieństwo podjął von Mises. Zadał on fundamentalne pytanie: co to znaczy, że ciąg obserwacji jest losowy i jak właściwie wyznaczać prawdopodobieństwo zdarzenia na podstawie częstości jego wystąpienia w takim ciągu? Pytanie okazało się inspirujące, bliskie statystyce, ale praktyczna realizacja idei von Misesa wydawała się nieosiągalna. Wygrał Kołmogorow, natomiast za odpowiedź na pytanie von Misesa przyjęło się uznawać prawa wielkich liczb.

Jednak model Kołmogorowa w przypadku każdego pomiaru prawdopodobieństwa należy dopiero ad hoc zbudować przez wnikliwe przemyślenie sprawy. Unifikuje on cały szereg konkretnych sytuacji, ale jest daleki od intuicji. Zgodnie z anegdotą, sam Erdös (postać na tyle ważna, że matematycy są zainteresowani grafem współautorstwa z tym panem) nie mógł uwierzyć w formalne rozwiązanie głośnego problemu trzech bramek (Monty Hall problem). Dopiero symulacja komputerowa go przekonała, a pełni ukojenia matematycznego zaznał ładnych parę lat później. Podobną furorę robi problem dwóch kopert, paradoks Bertranda i zadanie Banacha o zapałkach (dawniej: o palaczu, ale należy czynić zadość kampanii społecznej z tym okrutnym nałogiem). Co ważniejsze, sam Kołmogorow wierzył w fizyczność prawdopodobieństwa, a nie jakieś dobieranie modeli na łapu-capu.

Problemy fizyki statystycznej, a w szczególności pojęcie entropii występujące w termodynamice, doprowadziły matematyków – w tym i Kołmogorowa – do stworzenia teorii ergodycznej, możliwej do ścisłego sformułowania dzięki formalnemu pojęciu prawdopodobieństwa. Upraszczając historię, teoria ergodyczna dostarcza ścisłego języka i narzędzi teorii chaosu. Sama zaś entropia pojawia się u Shannona jako miara informacji. Powstaje teoria informacji. Jak wcześniej wspomniane zostało, niedobór informacji prowadzi do poważnych kłopotów z przewidywaniem zachowania się układu fizycznego (gaz i demon Laplace’a). Można zaryzykować niedokładne stwierdzenie, że teoria ergodyczna doprecyzowuje a jednocześnie poszerza pojęcie losowości.

Łatwo można jednak zbłądzić. Szereg systemów kryptograficznych opartych na chaosie okazało się nieodpornych na łamanie. Maszyny operują na skończonych rozwinięciach, podczas gdy przekształcenia chaotyczne są chaotyczne jedynie z punktu widzenia działania na ciągach nieskończonych, a nie ich skończonych przybliżeniach. Z drugiej strony, historia odkrycia motyla Lorenza zachęca do użycia chaosu matematycznego celem symulowania procesu losowego; wrażliwość na niewielką zmianę danych początkowych czyni funkcję chaotyczną podobną do funkcji hashującej.

Okazuje się, że to jeszcze nie koniec historii rozwoju pojęcia losowości. Zapoczątkowana przez Turinga, von Neumanna i in. rewolucja komputerowa wiąże się nierozerwalnie z pojęciem obliczenia, algorytmu. Komputer przetwarza informację. Informację można mierzyć entropią. Bum! Kołmogorow w swych poszukiwaniach wprowadził pojęcie złożoności algorytmicznej ciągu. Jeśli ciąg jest niekompresowalny, ma maksymalną możliwą złożoność, to należy go uznać za losowy. Oto stara koncepcja von Misesa, naiwnego zdefiniowania losowości pojedynczego ciągu, powraca do łask w postaci losowości algorytmicznej, nazywanej współcześnie losowością w sensie Martina-Löfa, na cześć studenta Kołmogorowa. (Odnotujmy tu, że Martin-Löf zajmował się również podstawami logicznymi funkcyjnych języków programowania. Dla osoby z ulicy jeszcze ciekawsze zainteresowania mają jego dwaj bracia: ubezpieczenia i technologie kosmiczne).

Niestety pojęcie losowości algorytmicznej jest dość abstrakcyjne. Nie dziwi więc zwycięstwo definicji prawdopodobieństwa Kołmogorowa nad próbami von Misesa. Jak przetestować, czy dany ciąg jest losowy? Tu napotykamy na ścianę i dziwy charakterystyczne dla logicznych podstaw informatyki (ucieleśnionych kursem teorii rekursji); trudno coś wskazać palcem, wszystko zdaje się istnieć potencjalnie, lecz nie namacalnie. Na otarcie łez odnotujmy, że każdy ciąg losowy w sensie Martina-Löfa jest ciągiem normalnym w sensie Borela. Normalność ciągu oznacza z grubsza, że wszystkie znaki i utworzone z nich słowa pojawiają się w ciągu odpowiednio często, w sposób równomierny. Naiwnie prosty ciąg Champernowne’a 0123456789 00 01 02… 99 000 001 …999… nad alfabetem złożonym z cyfr 0, 1,…, 9, okazuje się być normalnym, ale nie jest ciągiem losowym w sensie Martina-Löfa. Niestety nawet przyzwoita – by się zdawało – normalność nie jest pojęciem wystarczająco namacalnym. Na ogół sprawdzenie, czy ciąg jest normalny stanowi poważny problem. Czy ciąg cyfr rozwinięcia liczby pi w układzie szesnastkowym jest normalny? Pomimo zadziwiającego wzoru Baileya-Borweina-Plouffego na pojedyncze cyfry szesnastkowego rozwinięcia pi, nadal tego nie wiadomo (lipiec 2017). Z drugiej strony ciąg rzutów monetą jest normalny z prawdopodobieństwem 1. Czy to normalne?

Praktykujący informatyk nasze rozwikłanie zagadki losowości potraktować może wzruszeniem ramion. Powstrzymajmy się jeszcze chwilę od ciskania kamieni. Zwątpienie w ludzki rozum nami targa, lecz nie traćmy nadziei. Istnieje pojęcie losowości znacznie słabsze od tych, które zaprezentowano wyżej. Pomimo pewnych słabości ma ono szereg zalet. Pojęcie to jest namacalne, dziecięco proste i użyteczne. Losowość polega na tym, że wszystko może się zdarzyć, nawet najbardziej fikuśna kombinacja. Przynajmniej niektórzy tak myślą o losowości. W algorytmicznej teorii złożoności ciągi o takowej charakterystyce określamy mianem dyzjunktywnych. (Nazwę wymyślili teoretycy, którym rzecz się skojarzyła z dyzjunkcyjną postacią normalną wyrażenia. Ale były i konkurencyjne wobec terminu ,,disjunctive sequence” pomysły: rich sequence, saturated sequence). Ściśle rzecz biorąc, nieskończony ciąg nad alfabetem A jest dyzjunktywny, gdy zawiera w sobie (jako podciągi) wszelkie możliwe słowa skończone nad A. Okazuje się, że wtedy każde słowo pojawia się tak naprawdę nieskończenie wiele razy. (Widzisz to szanowny Czytelniku?) Jeżeli losować litery za pomocą wielościennej kostki, to powstały ciąg będzie dyzjunktywny z prawdopodobieństwem 1. I to nawet gdyby kostka była niesprawiedliwa. Nawet gdyby nam ktoś podmieniał co chwila kostkę na inną. (Ta bezczelna procedura nosi specjalną nazwę: niejednorodny proces Bernoulliego). W oczywisty sposób ciąg Champernowne’a jest dyzjunktywny.

Namacalność – jest, prostota – jest, a użyteczność? Okazuje się, że skuteczność algorytmu iteracji losowej do generowania fraktali zasadza się nie tyle na losowości, ile na dyzjunktywności. Algorytm iteracji losowej stanowi m.in. podstawę implementacji dekompresji fraktalnej, interpolacji fraktalnej oraz metody CGR porównywania kodów DNA. Być może inne algorytmy probabilistyczne można podobnie zderandomizować?

Cóż jeszcze? Ciągi dyzjunktywne mają związek z ciągami de Bruijna (optymalne upakowanie słów, w przypadku gdy chcemy wygenerować skończony fragment ciągu dyzjunktywnego), a poprzez to z rejestrami przesuwnymi (używanymi do generowania ciągów pseudolosowych) i kwadratami łacińskimi (magicznymi). Sprawa chyba jest dość poważna, bo w artykule Wikipedii ,,De Bruijn sequence” ktoś nawet wrzucił kod do generowania cykli de Bruijna w Pythonie.

Magicznie powróciliśmy do pseudolosowości, na czym zakończyć wypada tę przydługą podróż. Chciałoby się złośliwie podsumować: Which witch is such a wit? Za brak spisu literatury przepraszam, ale startując z Wikipedii łatwo podjąć interesujący trop z użyciem wyszukiwarki w roli psiego nosa.

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

Inne artykuły

Zapraszamy na WMiI UMK

Studia na Wydziale Matematyki i Informatyki

Nasze szkolenia

iOS11 Design Patterns: szkolenie w Warszawie, 22-24.09.2017


Python – i Ty możesz programować: szkolenie dla nauczycieli, 13-14 września 2017 w Toruniu


Od zera do Apple kodera – szkolenie dla początkujących, 8-10 września 2017 w Warszawie


Xamarin – programowanie wieloplatformowe, 9-10 września 2017 w Toruniu

Ostatnie artykuły

Zapraszamy na UMK