Pochodzenie Łańcuchów Markowa

Obserwując przyrodę, zauważamy piękną dychotomię: żadne dwie rzeczy nie są identyczne, lecz wszystkie zdają się zgodne z jakimś nadrzędnym wzorem. Platon uważał, że prawdziwa forma Wszechświata jest przed nami ukryta; obserwując przyrodę, poznamy tę formę jedynie w przybliżeniu. Jakby istniały sekretne projekty. Dostęp do czystych form daje tylko abstrakcyjne rozumowanie filozofii i matematyki. Weźmy np. okrąg. Platon definiował go jako zbiór punktów równoodległych od jednego punktu, środka. W przyrodzie nie znajdziemy jednak okręgu doskonałego ani doskonałej prostej. Chociaż Platon wysnuł przypuszczenie, że po niezliczonej liczbie lat wszechświat osiągnie stan idealny. Wróci do swojej formy doskonałej. Platońska idea abstrakcyjnych, czystych form była popularna przez wieki. Dopiero w XVI stuleciu ludzie zaczęli godzić się z nieuporządkowanymi wariantami rzeczywistości i za pomocą matematyki wydobywali z niej ukryte wzory. Bernouilli dopracował koncepcję wartości oczekiwanych. Interesowało go, jak dokładnie oszacować prawdopodobieństwo jakiegoś zdarzenia na podstawie tego, ile razy zdarzenie powtarza się w niezależnych próbach. Podał prosty przykład: przypuśćmy, że gdy nie patrzycie, ktoś wkłada do urny 3000 białych kamyków i 2000 czarnych. Aby ustalić stosunek ilości kamyków białych i czarnych, losujecie po jednym, ze zwracaniem, i notujecie, ile razy wyciągacie biały kamyk, a ile razy czarny. Wykazał, że wartość oczekiwana wyników białych i czarnych w miarę zwiększania się liczby prób zbliża się do stosunku rzeczywistego. Zasadę tę nazwano słabym prawem wielkich liczb. Zakończył wnioskiem: jeśli obserwacje zdarzeń będą kontynuowane w nieskończoność, to okaże się, że wszystkim na świecie rządzą precyzyjne stosunki i zmiany podlegające stałym prawom. Koncepcję szybko rozwinięto, gdy zauważono, że wyniki dążą do oczekiwanej średniej, a prawdopodobieństwo, że wynik od tej średniej odbiegnie, przybiera znajomy kształt, lub inaczej - rozkład. Świetny przykład stanowi tzw. deska Francisa Galtona. Każde odbicie jest pojedynczym, niezależnym zdarzeniem, takim jak rzut monetą. Po 10 odbiciach, czyli zdarzeniach, kulka wpada do zbiornika, gdzie widzimy stosunek skrętów w prawo do skrętów w lewo, czy orłów do reszek. Cała krzywa, znana jako rozkład dwumianowy, wydawała się kształtem idealnym. Pojawiała się zawsze, gdy rozpatrywano wyniki dużej liczby prób losowych. Przeciętny przebieg tych zdarzeń wydaje się określony z góry. Zasadę nazwano centralnym twierdzeniem granicznym. Niektórzy widzieli w tym groźny koncept filozoficzny. Paweł Niekrasow, z wykształcenia teolog, później zajął się matematyką i propagował religijną doktrynę wolnej woli. Nie pochwalał koncepcji ustalonego z góry przebiegu prób statystycznych. Sformułował słynną tezę, że niezależność to warunek konieczny dla prawa wielkich liczb. Niezależność cechuje tylko łatwe przykłady z kulkami i kostkami, gdzie wynik poprzedniego zdarzenia nie zmienia prawdopodobieństwa zdarzeń bieżących ani przyszłych. Każdy jednak potwierdzi, że większość rzeczy w świecie fizycznym zależy od wcześniejszych wyników: np. szansa wybuchu pożaru, słonecznego dnia, a nawet przewidywana długość życia. A gdy prawdopodobieństwo zdarzenia jest warunkowe względem poprzednich zdarzeń, to powiemy, że są to zdarzenia zależne. Lub zależne zmienne. To stwierdzenie irytowało innego rosyjskiego matematyka, Andrieja Markowa. Publicznie wyrażał niechęć wobec Niekrasowa. Napisał nawet w liście: „Ta okoliczność skłania mnie do wyjaśnienia, w serii artykułów, że prawo wielkich liczb może uwzględniać zmienne zależne”. Używa konstrukcji, o której, jak mówi, Niekrasowowi nawet się nie śniło. Markow rozciąga wnioski Bernouilliego na zmienne zależne, stosując genialny pomysł. Wyobraźcie sobie rzut monetą, który nie jest niezależny. Zależy od poprzedniego wyniku. Ma krótkotrwałą pamięć jednego zdarzenia. Wyraźmy to poprzez hipotetyczną maszynę, która zawiera dwa kubki; nazwijmy je stanami. W jednym stanie jest po tyle samo kulek jasnych i ciemnych. W drugim stanie ciemnych jest więcej niż jasnych. Jeden kubek nazwijmy stanem 0: to sytuacja po wylosowaniu ciemnej kulki. Drugi stan nazwiemy 1; to gdy wypadła kulka jasna. Maszynę uruchamiamy, wyciągając kulkę z dowolnego stanu. Potem, zależnie od tego zdarzenia, przechodzimy do stanu 0 lub 1. Na podstawie wyniku otwieramy 0, jeśli kulka była ciemna, albo 1, jeżeli jasna. Dzięki tej dwustanowej maszynie określimy 4 możliwe przejścia. Jeśli jesteśmy w stanie 0 i wypadnie ciemna kulka, to losujemy jeszcze raz. Po kulce jasnej przechodzimy do stanu 1, który może się zapętlić lub skierować nas znów do 0, gdy kulka będzie ciemna. Prawdopodobieństwo wyboru kulki ewidentnie nie jest niezależne; zależy od poprzedniego wyniku. Ale Markow udowodnił, że póki każdy stan w maszynie jest osiągalny, to, maszyna, w miarę losowań, dąży do równowagi. Nie ma znaczenia, skąd zaczniecie. To, ile razy odwiedzicie każdy stan, i tak będzie odzwierciedlać określony stosunek, prawdopodobieństwo. Ten prosty przykład obala tezę Niekrasowa, jakoby tylko zdarzenia niezależne mogły dawać przewidywalne rozkłady. Koncepcja modelowania ciągów zdarzeń losowych za pomocą stanów i przejść między nimi zyskała nazwę łańcucha Markowa. Jedno z pierwszych i najsłynniejszych zastosowań łańcucha Markowa przedstawił Claude Shannon.