Rachunek Prawdopodobieństwa i Statystyka (UW) Wykład 8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Motywacja

Zanim zdefiniujemy pojęcie łańcucha Markowa przyjrzyjmy się przykładom sytuacji, które można za ich pomocą opisywać i pytań, na które pozwalają one odpowiadać.

Przykład 8.1 (Student walczy) Student raz w tygodni bierze udział w zajęciach z rachunku prawdopodobieństwa. Na każde zajęcia przychodzi przygotowany bądź nie. Jeśli w danym tygodniu jest przygotowany, to w następnym jest przygotowany z prawdopodobieństwem 0.7. Jeśli natomiast w danym tygodniu nie jest przygotowany, to w następnym jest przygotowany z prawdopodobieństwem 0.2. Interesują nas odpowiedzi na pytania w rodzaju:

  1. Jeśli student jest w tym tygodniu nieprzygotowany, to ile tygodni musimy średnio czekać aż będzie przygotowany?
  2. Na dłuższą metę, jak często student jest przygotowany?


Przykład 8.2 (Turniej trzyosobowy) Trzech graczy: A, B i C gra turniej systemem "przegrywający odpada". Turniej zaczyna się od pojedynku A z B, a w każdej kolejnej grze gra zawodnik, który w poprzedniej nie grał ze zwycięzcą. Dla każdej pary zawodników znamy ich prawdopodobieństwa wygrania bezpośredniego pojedynku.

  1. Jak długo będziemy średnio czekać na drugi pojedynek A z B?
  2. Jeśli rozgrywany turniej będzie się składał z bardzo wielu gier, to średnio jaką część wszystkich gier rozegranych będą grać między sobą gracze A i B? Jak wiele gier (spośród wszystkich gier) wygra średnio gracz A?


Przykład 8.3 (Hazardzista) Hazardzista zaczyna grać z kapitałem początkowym 1000 zł. W każdej rundzie rozgrywki z prawdopodobieństwem 0.5 wygrywa 10 zł i z prawdopodobieństwem 0.5 przegrywa 10zł. Celem hazardzisty jest zdobycie kwoty 5000zł, ale zakończy grę także jeśli wcześniej zbankrutuje.

  1. Jakie jest prawdopodobieństwo, że uda mu się zdobyć 5000zł?
  2. Jak długo musi średnio grać, aby zdobyć tę kwotę lub zbankrutować?
  3. Co jeśli hazardzista nie przestaje grać, chyba że zbankrutuje? Jakie jest prawdopodobieństwo tego, że się to stanie? (ignorujemy w tym miejscu, to że wcześniej umrze/zachoruje/zaśnie/inne)


Definicja łańcucha Markowa

Zauważmy, że we wszystkich powyższych przykładach mamy do czynienia z obiektem/systemem/układem, który zawsze znajduje się w jednym z pewnej liczby stanów (student jest w stanie "przygotowany", bądź w stanie "nieprzygotowany", hazardzista w stanie "0zł", "1zł", itd.). Ponadto stan, w którym znajdzie się za chwilę jest wybierany losowo, ale prawdopodobieństwa znalezienia się w poszczególnych stanach zależą tylko od aktualnego stanu.

Formalnie taką sytuację możemy modelować następująco: Definicja (łańcuch Markowa) Łańcuchem Markowa o zbiorze stanów nazywamy ciąg zmiennych losowych taki, że dla każdego i ciągu stanów .

W tej definicji zmienna opisuje stan, w którym znajduje się łańcuch Markowa w chwili . Intuicyjnie, warunek z definicji łańcucha Markowa mówi, że zmienna zależy tylko od zmiennej . Co ważne, nie znaczy to, że jest niezależna od . Znaczy to jedynie tyle, że "cała zależność od jest zawarta w zależności od ".

Uwaga 8.4 Ze względu na definicję zmiennej losowej (przypomnijmy: zmienne losowe mają wartości rzeczywiste), w powyższej definicji zakładamy, że stany łańcucha Markowa są liczbami rzeczywistymi. W praktyce takie ograniczenie jest dość niewygodne, np. w przykładzie z trzyosobowym turniejem naturalne byłoby przyjęcie . Zawsze można jednak przypisać takim ogólniejszym stanom etykiety będące liczbami rzeczywistymi, czy nawet naturalnymi, i w ten sposób uzyskać łańcuch Markowa zgodny z definicją.

Liczby występujące w definicji łańcucha Markowa to tzw. prawdopodobieństwa przejścia w jednym kroku. Jeśli w danej chwili łańcuch jest w stanie , to z prawdopodobieństwem znajdzie się w następnej chwili w stanie . Liczby te wygodnie jest ułożyć w macierz: Definicja (macierz przejścia) Macierzą przejścia (w jednym kroku) łańcucha Markowa nazywamy macierz .

Uwaga W dalszej części wykładu będziemy symbolem oznaczać zarówno macierz przejścia łańcucha, jak i sam łańcuch.

Z oczywistych względów zachodzi następujący fakt. Fakt 8.5 Wiersze macierzy przejścia łańcucha Markowa sumują się do 1.

Uwaga 8.6 Może się zdarzyć, że zbiór nie będzie skończony (może nawet nie być przeliczalny, ale takie sytuacje nie będą nas interesować). W związku z tym zdefiniowany powyżej obiekt może czasem nie być (skończoną) macierzą. Jak jednak łatwo zauważyć podstawowe operacje macierzowe takie jak mnożenie macierzy przez wektor, czy przez inną macierz, mają sens także dla takich "nieskończonych macierzy". W ogólnym przypadku mogą pojawić się problemy związane ze zbieżnością, ale w naszym przypadku problemy takie nie wystąpią ze względu na Fakt 8.5. W związku z tym, w dalszym ciągu wykładu będziemy ignorowali tę kwestię i mówili po prostu o macierzy przejścia.

Przykład 8.1 (Student walczy, c.d.) W przykładzie ze studentem mamy dwa stany: 1 - student jest przygotowany, oraz 2 - student nie jest przygotowany. Macierz przejścia wygląda w tym przypadku tak:

Przypuśćmy, że znamy rozkład zmiennej , tzn. prawdopodobieństwa tego, że w chwili znajdujemy się w poszczególnych stanach. Jak wygląda rozkład zmiennej ? I ogólniej, jak wygląda rozkład zmiennej dla  ? Okazuje się, że można go łatwo obliczyć korzystając z macierzy . Fakt 8.7 Niech będzie rozkładem reprezentowanym za pomocą wierszowego wektora prawdopodobieństw poszczególnych stanów, t.j.\ . Wtedy i ogólniej . Dowód Ze wzoru na prawdopodobieństwo całkowite mamy: , a to jest definicja mnożenia macierzy przez wektor (z lewej strony!). Ogólniejsza wersja wynika z prostszej przez indukcję.

Powyższy fakt pokazuje siłę macierzowej reprezentacji łańcuchów Markowa. Istnieją bowiem algorytmy pozwalające bardzo szybko obliczyć nawet dla dużych (oparte, na przykład, na rozkładzie Jordana macierzy). Dzięki temu możemy w relatywnie prosty sposób obliczać rozkład znając rozkład .

W dalszej części wykładu elementy macierzy będziemy oznaczać . W szczególności .


Prawdopodobieństwa dotarcia

Zastanowimy się teraz jak można odpowiadać na pytania w rodzaju "Jeśli łańcuch Markowa jest w stanie , to jakie jest prawdopodobieństwo tego, że kiedykolwiek dotrze do stanu ?". Będziemy to prawdopodobieństwo oznaczać . Symbol będziemy interpretować jako prawdopodobieństwo tego, że wrócimy do stanu po wykonaniu co najmniej jednego kroku. Innym naturalnym pomysłem byłoby przyjęcie , ale wybrana przez nas konwencja jest wygodniejsza w praktyce (choć prowadzi do nieco bardziej skomplikowanych wzorów).

Twierdzenie 8.8 Niech będzie łańcuchem Markowa o zbiorze stanów i niech . Wtedy .

Dowód Przyjmijmy, że i niech będzie zdarzeniem odpowiadającym dotarciu kiedykolwiek do stanu , formalnie . Interesuje nas obliczenie P(A). Ze wzoru na prawdopodobieństwo całkowite mamy . Łatwo zauważyć, że dla (zachęcamy czytelnika do uzasadnienia tego formalnie) oraz , skąd dostajemy tezę.


Klasyfikacja stanów

Przypomnijmy, że symbolem oznaczamy prawdopodobieństwo przejścia ze stanu do stanu w krokach, a symbolem prawdopodobieństwo dotarcia (kiedykolwiek) z do . Niech ponadto będzie prawdopodobieństwem dotarcia z do po raz pierwszy po krokach. Oczywiście zachodzi .

Definicja (stan powracający/chwilowy) Stan jest powracający, jeśli , czyli jeśli wracamy do niego z prawdopodobieństwem . Stan jest chwilowy, jeśli nie jest powracający.

Przykład 8.9 Łatwo zauważyć oba stany studenta i wszystkie trzy stany turnieju trzyosobowego są powracające. W przykładzie z hazardzistą bankructwo i osiągniecie celu są stanami powracającymi, natomiast wszystkie pozostałe stany są chwilowe.

Twierdzenie 8.10 Stan jest powracający wtedy i tylko wtedy, gdy .

Uwaga 8.11 Tezę powyższego twierdzenia można interpretować następująco: stan jest powracający wtedy i tylko wtedy, gdy średnia liczba powrotów do jest nieskończona. Jest to interpretacja bardzo przydatna, ale niestety nie do końca poprawna - liczba powrotów może być nieskończona, a zatem nie jest zmienną losową w sensie naszej definicji.

Dowód Aby uniknąć problemu, o którym wspomnieliśmy w uwadze 8.11, przyjmijmy, że oraz niech będzie liczbą powrotów do w pierwszych krokach (ograniczając się do pierwszych kroków unikamy nieskończonych wartości). Wtedy z liniowości wartości oczekiwanej , a zatem jest granicą .

Jeśli jest stanem powracającym, to , a zatem istnieje takie, że , tzn.\ z prawdopodobieństwem wrócimy do stanu w nie więcej niż krokach. Mamy wtedy , a także i ogólnie . Dla dostajemy . Biorąc odpowiednio małe i odpowiednio duże (a zatem także odpowiednio duże ) widzimy, że może przyjmować dowolnie duże wartości, a co za tym idzie .

Aby pokazać implikację w drugą stronę, przyjmijmy, że jest chwilowy. Wtedy . Dla dowolnego zachodzi , a zatem , co kończy dowód.

Definicja (stany osiągalne) Stan jest osiągalny ze stanu jeśli istnieje takie , że . Zbiór stanów osiągalnych ze stanu oznaczamy .

Definicja (stany komunikujące się) Stany komunikują się jeśli oraz .

Uwaga 8.12 Te definicje mają naturalną interpretację grafową. Jeśli zbudujemy graf, w którym wierzchołkami są stany łańcucha, a krawędź skierowana istnieje, gdy , to:

  1. jest osiągalny z jeśli istnieje skierowana ścieżka z do ,
  2. i komunikują się, jeśli są w tej samej silnie spójnej składowej.


Fakt 8.13 Jeśli stan jest powracający, to każdy stan osiągalny z też jest powracający i zachodzi . Dowód (szkic) Ponieważ jest osiągalny z to dla pewnego zachodzi . Z drugiej strony, ponieważ jest powracający, to z prawdopodobieństwem wrócimy do po -tym kroku. Stąd . Niech i niech i będą liczbą odwiedzin odpowiednio i w pierwszych krokach. Wtedy wiemy z twierdzenia 8.10, że , ale ponieważ (bo za każdym razem gdy odwiedzamy mamy szansę na odwiedzenie po krokach), to dostajemy też , co w połączeniu z twierdzeniem 8.10 oznacza, że jest powracający. Druga część tezy jest oczywista. (Zachęcamy czytelnika do uzupełnienia powyższej argumentacji.)

Z powyższych rozważań wynika następujący wniosek, bardzo przydatny w szybkiej klasyfikacji stanów łańcucha Markowa. Wniosek 8.14 Niech będzie grafem odpowiadającym skończonemu łańcuchowi Markowa , jak w uwadze 8.12 i niech będzie DAG-iem silnie spójnych składowych . Wtedy:

  1. każda silnie spójna składowa (zwana często klasą) składa się albo z samym stanów powracających (tzw. klasy powracające), albo z samych stanów chwilowych (tzw. klasy chwilowe),
  2. ujścia (czyli wierzchołki, z których nie wychodzą żadne krawędzie) odpowiadają klasom powracającym, a pozostałe wierzchołki klasom chwilowym.


Wniosek 8.15 W skończonym łańcuchu Markowa dla każdego stanu istnieje stan powracający osiągalny z . W szczególności każdy skończony łańcuch Markowa zawiera stan powracający.

Definicja (łańcuch nieredukowalny) Łańcuch nazywamy nieredukowalnym (w starszej literaturze nieprzywiedlny), jeśli składa się z jednej klasy powracającej.

Uwaga 8.16 Z wniosku 8.15 wynika, że w przypadku łańcuchów skończonych nie ma potrzeby żądać, by jedyna klasa łańcucha była powracająca - ona musi być powracająca bo zawiera stan powracający. Nie jest to jednak prawdą w przypadku łańcuchów nieskończonych.


Średnie czasy dotarcia

Jesteśmy już gotowi odpowiedzieć na pytania postaci "Średnio po ilu krokach łańcuch Markowa dotrze do stanu ?". Ograniczymy się przy tym do następującej sytuacji: Niech będzie skończonym łańcuchem Markowa o dokładnie jednej klasie powracającej i niech będzie jednym z jej elementów. Wtedy dla każdego stanu zachodzi (dlaczego?). Interesuje nas obliczenie dla każdego stanu średniej liczby kroków potrzebnej na dotarcie do . W szczególności przez oznaczamy średnią liczbę kroków potrzebnych, aby wrócić do .

Twierdzenie 8.17 Niech będzie jak powyżej. Wtedy dla każdego zachodzi: .

Uwaga 8.18 Jeśli w łańcuchu istnieje więcej niż jeden stan powracający, a interesuje nas dojście do któregokolwiek z nich, to możemy skleić wszystkie stany powracające w jeden (zachęcamy czytelnika do uzupełnienia szczegółów). Takie sklejenie można wykonać nawet jeśli istnieje więcej niż jedna klasa powracająca. W takim przypadku można też próbować obliczać średni czas dojścia do stanu chwilowego pod warunkiem, że do niego w ogóle dojdziemy. Ta sytuacja jest bardziej skomplikowana i nie będziemy się nią tu zajmować.

Dowód Dowód przebiega analogicznie do dowodu twierdzenia 8.8. Załóżmy, że i niech , czyli jest liczbą kroków, po której po raz pierwszy docieramy do stanu . Interesuje nas obliczenie . Ze wzoru na całkowitą wartość oczekiwaną mamy . Łatwo zauważyć, że dla (zachęcamy czytelnika do uzasadnienia tego formalnie) oraz , skąd dostajemy tezę.


Rozkład stacjonarny i długookresowe zachowanie łańcucha Markowa

Postaramy się teraz opisać długookresowe zachowanie łańcucha Markowa. Dzięki temu będziemy odpowiadać na pytania w rodzaju:

  1. Na dłuższą metę, jak często student jest przygotowany? (patrz przykład 8.1)
  2. Jeśli rozgrywamy bardzo dużo gier, to jak często grają ze sobą gracze A i B? (patrz przykład 8.2)


Żeby to zrobić, musimy najpierw wprowadzić kilka definicji.

Definicja (okresowość) Stan jest okresowy, jeśli istnieje liczba całkowita (zwana okresem ) taka, że jeśli dla pewnego , to . Stan, który nie jest okresowy nazywamy nieokresowym. Łańcuch Markowa nie zawierający stanów okresowych nazywamy łańcuchem nieokresowym Przykład 8.19 Rozważmy łańcuch Markowa o stanach i przejściach jeśli oraz wpp. Wtedy wszystkie stany mają okres .

Fakt 8.20 Jeśli jest okresowy z okresem to każdy stan komunikujący się z też jest okresowy z okresem . Dowód Ponieważ i się komunikują, to mamy oraz dla pewnych . Gdyby nie spełniał tezy, to istniałoby niepodzielne przez i takie, że . Ale wtedy moglibyśmy przejść z do zarówno w krokach jak i krokach, co nie jest możliwe, bo co najmniej jedna z tych liczb nie jest podzielna przez .

Możemy już sformułować najważniejszy wynik tego rozdziału: Twierdzenie 8.21 (ergodyczne) Dla skończonego nieredukowalnego i nieokresowego łańcucha Markowa o zbiorze stanów istnieje wektor takie, że:

  1. oraz dla wszystkich ,
  2. ,
  3. dla każdego zachodzi .


Pojawiający się w powyższym twierdzeniu wektor nazywa się z reguły rozkładem stacjonarnym, co można łatwo zrozumieć patrząc na pierwsze dwa punkty tezy twierdzenia ergodycznego. Pierwszy z punktów mówi, że jest rozkładem prawdopodobieństwa na zbiorze stanów . Drugi punkt mówi, że jest on stacjonarny w następującym sensie: Jeśli ma rozkład , to także ma rozkład .

Najważniejszy jest oczywiście punkt trzeci, który mówi, że niezależnie od tego w jakim stanie łańcuch startuje, po odpowiednio długim czasie zbiegnie do rozkładu . Innymi słowy, niezależnie od rozkładu , dla odpowiednio dużych , zmienna będzie miała rozkład dowolnie bliski .

Przykład 8.22 Widać, że twierdzenie ergodyczne jest dokładnie tym czego potrzebujemy, aby móc odpowiadać na pytania, które zadaliśmy na początku tego rozdziału, np. "Na dłuższą metę, jak często student jest przygotowany?". Przypomnijmy, że student znajduje się w jednym z dwóch stanów: 1 - przygotowany, 2 - nieprzygotowany. Macierz przejścia między tymi stanami wygląda następująco: Odpowiedzią na pytanie, o to jak często student jest na dłuższą metę przygotowany jest liczba z twierdzenia ergodycznego. Jak ją znaleźć? Oczywiście za pomocą twierdzenia ergodycznego, a konkretnie dwóch pierwszych punktów tezy tego twierdzenia. Mamy mianowicie: , czyli , (tak naprawdę wystarczy jedno z tych równań, dlaczego?) oraz . Łatwo dostajemy , .

Uwaga 8.23 Łatwo zauważyć, że założenia twierdzenia ergodycznego są do pewnego stopnia konieczne:

  1. Jeśli nasz łańcuch jest okresowy, na przykład jest cyklem, i wystartujemy z jednego z punktów tego cyklu, to w dowolnym kroku będziemy w jednym punkcie cyklu, w szczególności nie może być mowy o zbieżności do jakiegokolwiek stabilnego rozkładu.
  2. Założenie, że łańcuch jest nieredukowalny można nieco osłabić. Wystarczy, że zawiera dokładnie jedną powracającą klasę stanów. Twierdzenie zachodzi w takiej sytuacji w zasadzie bez zmian, a wszystkie stany chwilowe mają w rozkładzie stacjonarnym prawdopodobieństwo zerowe.

Jeśli jednak nasz łańcuch zawiera więcej niż jedną powracającą klasę stanów to twierdzenie nie zachodzi. W zależności od tego, gdzie wystartujemy, uzyskamy inny rozkład stacjonarny. W szczególności, jeśli wystartujemy w którejś z klas powracających, to nigdy z niej nie wyjdziemy.

  1. Twierdzenie w postaci podanej wyżej nie zachodzi dla łańcuchów nieskończonych. Przykładem nieskończonego nieredukowalnego i nieokresowego łańcucha, który nie ma rozkładu stacjonarnego jest błądzenie losowe po prostej (dowód wykracza poza zakres tego wykładu). Aby teza twierdzenia zachodziła należy dodatkowo zażądać, aby wszystkie powracające stany łańcucha były niezerowe, tzn. aby dla każdego stanu powracającego zachodziło .

Ostatnie twierdzenie tego wykładu pokazuje interesujące zastosowanie rozkładu stacjonarnego. Twierdzenie 8.24 Przy założeniach jak w twierdzeniu ergodycznym dla każdego stanu zachodzi . Formalny dowód pominiemy, ale intuicyjnie twierdzenie to powinno być jasne: Skoro na dłuższą metę jest frakcją kroków, w których łańcuch jest w stanie , to średni odstęp między wystąpieniami stanu wynosi . Przykład 8.25 Możemy z tego twierdzenia wywnioskować, że jeśli student jest w danym tygodniu przygotowany, to musimy czekać średnio tygodnie, aż znów będzie przygotowany. Akurat w tym przypadku ten sam wynik można w bardzo prosty sposób uzyskać wprost z definicji, ale jeśli łańcuch jest bardziej skomplikowany twierdzenie ergodyczne jest często najprostszą metodą.

Zastosowanie łańcuchów Markowa

Łańcuchy Markowa mają mnóstwo bardzo różnorodnych zastosowań. Wspomnimy w tym miejscu o zaledwie kilku z nich:

  1. Losowanie obiektów: Aby wygenerować losowy obiekt zgodnie z pewnym rozkładem konstruujemy łańcuch Markowa dla którego rozkład ten jest rozkładem stacjonarnym, po czym wykonujemy odpowiednio długie symulacje tego łańcucha. To podejście nazywa się metodą Monte Carlo z wykorzystaniem łańcuchów Markowa (ang. Markov Chain Monte Carlo).
  2. Modelowanie: Za pomocą łańcuchów Markowa można skutecznie modelować wiele naturalnych procesów i struktur. Na przykład modelując w ten sposób język naturalny można zbudować algorytm kompresji tekstu. Alternatywnie, modeli takich można użyć do generowania losowych tekstów. Modele Markowa pojawiają się też bardzo często w biologii obliczeniowej.
  3. PageRank: Imponującym zastosowaniem łańcuchów Markowa jest stworzony przez firmę Google algorytm szeregowania stron PageRank. Algorytm ten bazuje na łańcuchu Markowa, który jest modelem procesu poruszania się użytkownika po zbiorze wszystkich (znanych systemowi) stron WWW.