Łańcuch Markowa - Markov chain

Diagram przedstawiający dwustanowy proces Markowa ze stanami oznaczonymi E i A. Każda liczba reprezentuje prawdopodobieństwo przejścia procesu Markowa z jednego stanu do drugiego, w kierunku wskazanym przez strzałkę. Na przykład, jeśli proces Markowa jest w stanie A, to prawdopodobieństwo, że przejdzie do stanu E wynosi 0,4, podczas gdy prawdopodobieństwo pozostania w stanie A wynosi 0,6.

Markov chain lub proces Markowa jest stochastycznym modelem opisującym sekwencję możliwych zdarzeń, w których prawdopodobieństwo każdego zdarzenia zależy jedynie od stanu osiągniętego w poprzednim przypadku. Przeliczalnie nieskończony sekwencji, w których stan porusza się łańcuch w nieciągłych przedziałach czasu, daje dyskretnych łańcuch Markowa (DTMC). Ciągły w czasie procesu nazywa się ciągłe stacjonarne Markowa łańcuch (CTMC). Jego nazwa pochodzi od rosyjskiego matematyka Andrieja Markowa .

Łańcuchy Markowa mają wiele zastosowań jako modele statystyczne procesów rzeczywistych, takich jak badanie systemów tempomatu w pojazdach silnikowych , kolejek lub linii klientów przybywających na lotnisko, kursów walut i dynamiki populacji zwierząt.

Procesy Markowa są podstawą ogólnych stochastycznych metod symulacji znanych jako łańcuch Markowa Monte Carlo , które są wykorzystywane do symulacji próbkowania ze złożonych rozkładów prawdopodobieństwa i znalazły zastosowanie w statystyce bayesowskiej , termodynamice , mechanice statystycznej , fizyce , chemii , ekonomii , finansach , sygnale przetwarzanie , teoria informacji i przetwarzanie mowy .

Przymiotniki Markovian i Markov są używane do opisania czegoś, co jest związane z procesem Markowa.

Wstęp

rosyjski matematyk Andrey Markov

Definicja

Proces Markowa jest procesem stochastycznym, który spełnia właściwość Markowa (czasami określaną jako „brak pamięci ”). Mówiąc prościej, jest to proces, dla którego można przewidzieć przyszłe wyniki wyłącznie na podstawie jego obecnego stanu i – co najważniejsze – takie prognozy są tak samo dobre, jak te, które można poczynić znając pełną historię procesu. Innymi słowy, w zależności od obecnego stanu systemu, jego stany przyszłe i przeszłe są niezależne .

Łańcuch Markowa to rodzaj procesu Markowa, który ma dyskretną przestrzeń stanów lub dyskretny zestaw indeksów (często reprezentujących czas), ale dokładna definicja łańcucha Markowa jest różna. Na przykład powszechne jest definiowanie łańcucha Markowa jako procesu Markowa w dyskretnym lub ciągłym czasie z policzalną przestrzenią stanów (a więc niezależnie od natury czasu), ale często definiuje się również łańcuch Markowa jako mający dyskretny czas w przeliczalnej lub ciągłej przestrzeni stanów (a więc niezależnie od przestrzeni stanów).

Rodzaje łańcuchów Markowa

Należy określić przestrzeń stanów i indeks parametrów czasowych systemu . Poniższa tabela przedstawia przegląd różnych instancji procesów Markowa dla różnych poziomów ogólności przestrzeni stanów oraz dla czasu dyskretnego i czasu ciągłego:

Policzalna przestrzeń stanu Ciągła lub ogólna przestrzeń stanów
Czas dyskretny (czas dyskretny) łańcuch Markowa na policzalnej lub skończonej przestrzeni stanów Łańcuch Markowa na mierzalnej przestrzeni stanów (na przykład łańcuch Harrisa )
Ciągły czas Proces Markowa w czasie ciągłym lub proces skoku Markowa Dowolny ciągły proces stochastyczny z własnością Markowa (na przykład proces Wienera )

Należy zauważyć, że w literaturze nie ma ostatecznej zgody na użycie niektórych terminów oznaczających szczególne przypadki procesów Markowa. Zwykle termin „łańcuch Markowa” jest zarezerwowany dla procesu z dyskretnym zestawem czasów, to znaczy dyskretnego łańcucha Markowa (DTMC) , ale kilku autorów używa terminu „proces Markowa” w odniesieniu do ciągłego czasu Łańcuch Markowa (CTMC) bez wyraźnej wzmianki. Ponadto istnieją inne rozszerzenia procesów Markowa, które są określane jako takie, ale niekoniecznie należą do żadnej z tych czterech kategorii (patrz model Markowa ). Co więcej, indeks czasu niekoniecznie musi być wyceniany w sposób rzeczywisty; podobnie jak w przypadku przestrzeni stanów, można sobie wyobrazić procesy, które przechodzą przez zbiory indeksów z innymi konstrukcjami matematycznymi. Zauważ, że łańcuch Markowa w ogólnej przestrzeni stanów w czasie ciągłym jest tak ogólny, że nie ma wyznaczonego członu.

Podczas gdy parametr czasu jest zwykle dyskretny, przestrzeń stanów łańcucha Markowa nie ma żadnych ogólnie przyjętych ograniczeń: termin może odnosić się do procesu w dowolnej przestrzeni stanów. Jednak wiele zastosowań łańcuchów Markowa wykorzystuje skończone lub przeliczalnie nieskończone przestrzenie stanów, które mają prostszą analizę statystyczną. Poza parametrami indeksu czasu i przestrzeni stanów istnieje wiele innych odmian, rozszerzeń i uogólnień (zobacz Wariacje ). Dla uproszczenia większość tego artykułu koncentruje się na przypadku dyskretnej przestrzeni stanów w czasie dyskretnym, chyba że zaznaczono inaczej.

Przejścia

Zmiany stanu układu nazywane są przejściami. Prawdopodobieństwa związane z różnymi zmianami stanu nazywane są prawdopodobieństwami przejścia. Proces charakteryzuje się przestrzenią stanów, macierzą przejścia opisującą prawdopodobieństwa poszczególnych przejść oraz stanem początkowym (lub początkowym rozkładem) w przestrzeni stanów. Umownie zakładamy, że wszystkie możliwe stany i przejścia zostały uwzględnione w definicji procesu, więc zawsze istnieje następny stan, a proces się nie kończy.

Proces losowy w czasie dyskretnym obejmuje system, który znajduje się w określonym stanie na każdym etapie, przy czym stan zmienia się losowo między etapami. Kroki są często uważane za momenty w czasie, ale równie dobrze mogą odnosić się do odległości fizycznej lub innego dyskretnego pomiaru. Formalnie kroki są liczbami całkowitymi lub liczbami naturalnymi , a proces losowy to ich odwzorowanie na stany. Własność Markowa mówi, że rozkład prawdopodobieństwa warunkowego dla systemu w kolejnym kroku (a właściwie na wszystkich przyszłych krokach) zależy tylko od aktualnego stanu systemu, a nie dodatkowo od stanu systemu na poprzednich krokach.

Ponieważ system zmienia się losowo, generalnie nie można z całą pewnością przewidzieć stanu łańcucha Markowa w danym punkcie w przyszłości. Jednak statystyczne właściwości przyszłości systemu można przewidzieć. W wielu zastosowaniach to właśnie te właściwości statystyczne są ważne.

Historia

Markow studiował procesy Markowa na początku XX wieku, publikując swoją pierwszą pracę na ten temat w 1906 roku. Procesy Markowa w czasie ciągłym odkryto na długo przed pracą Andreya Markowa na początku XX wieku w postaci procesu Poissona . Markow był zainteresowany badaniem rozszerzenia niezależnych ciągów losowych, motywowany sporem z Pawłem Niekrasowem, który twierdził, że niezależność jest niezbędna do utrzymania słabego prawa wielkich liczb . W swoim pierwszym artykule o łańcuchach Markowa, opublikowanym w 1906 roku, Markow wykazał, że w pewnych warunkach średnie wyniki łańcucha Markowa zbiegają się do ustalonego wektora wartości, co dowodzi słabego prawa wielkich liczb bez założenia o niezależności, które było powszechnie uważane za wymóg, aby takie matematyczne prawa były spełnione. Markow później użył łańcuchów Markowa do badania rozmieszczenia samogłosek w Eugeniuszu Onieginie , napisanym przez Aleksandra Puszkina i udowodnił centralne twierdzenie graniczne dla takich łańcuchów.

W 1912 Henri Poincaré badał łańcuchy Markowa na skończonych grupach w celu zbadania tasowania kart. Inne wczesne zastosowania łańcuchów Markowa obejmują model dyfuzji, wprowadzony przez Paula i Tatianę Ehrenfest w 1907 roku, oraz proces rozgałęziania, wprowadzony przez Francisa Galtona i Henry'ego Williama Watsona w 1873 roku, poprzedzający pracę Markowa. Po pracach Galtona i Watsona później ujawniono, że ich proces rozgałęziania został niezależnie odkryty i zbadany około trzy dekady wcześniej przez Irénée-Jules Bienaymé . Od 1928 Maurice Fréchet zainteresował się łańcuchami Markowa, co ostatecznie doprowadziło do opublikowania w 1938 r. szczegółowego opracowania na temat łańcuchów Markowa.

Andriej Kołmogorow rozwinął w artykule z 1931 roku dużą część wczesnej teorii ciągłych procesów Markowa. Kołmogorowa częściowo zainspirowała praca Louisa Bacheliera z 1900 roku na temat wahań na giełdzie, a także praca Norberta Wienera na temat modelu ruchu Browna Einsteina. Wprowadził i przestudiował określony zestaw procesów Markowa, znanych jako procesy dyfuzji, gdzie wyprowadził zestaw równań różniczkowych opisujących te procesy. Niezależnie od pracy Kołmogorowa, Sydney Chapman wyprowadził w artykule z 1928 r. równanie, obecnie nazywane równaniem Chapmana-Kolmogorowa , w sposób mniej rygorystyczny matematycznie niż Kołmogorowa, badając ruchy Browna. Równania różniczkowe są teraz nazywane równaniami Kołmogorowa lub równaniami Kołmogorowa-Chapmana. Inni matematycy, którzy znacząco przyczynili się do powstania procesów Markowa, to William Feller , począwszy od lat 30. XX wieku, a następnie Eugene Dynkin , począwszy od lat 50. XX wieku.

Przykłady

Losowe spacery oparte na liczbach całkowitych i problem ruiny hazardzisty to przykłady procesów Markowa. Niektóre odmiany tych procesów były badane setki lat wcześniej w kontekście zmiennych niezależnych. Dwoma ważnymi przykładami procesów Markowa są proces Wienera , znany również jako proces ruchów Browna , oraz proces Poissona , które są uważane za najważniejsze i centralne procesy stochastyczne w teorii procesów stochastycznych. Te dwa procesy są procesami Markowa w czasie ciągłym, podczas gdy losowe spacery po liczbach całkowitych i problem ruiny hazardzisty są przykładami procesów Markowa w czasie dyskretnym.

Słynny łańcuch Markowa to tak zwany „spacer pijaka”, błądzenie losowe po osi liczbowej , w którym na każdym kroku pozycja może zmieniać się o +1 lub -1 z równym prawdopodobieństwem. Z dowolnej pozycji możliwe są dwa przejścia, do następnej lub poprzedniej liczby całkowitej. Prawdopodobieństwo przejścia zależy tylko od aktualnej pozycji, a nie od sposobu, w jaki pozycja została osiągnięta. Na przykład prawdopodobieństwa przejścia od 5 do 4 i od 5 do 6 są równe 0,5, a wszystkie inne prawdopodobieństwa przejścia od 5 są równe 0. Prawdopodobieństwa te są niezależne od tego, czy system był wcześniej w 4 czy 6.

Innym przykładem są nawyki żywieniowe stworzenia, które je tylko winogrona, ser lub sałatę i którego nawyki żywieniowe są zgodne z następującymi zasadami:

Markov-ser-sałata-winogrona.svg
  • Zjada dokładnie raz dziennie.
  • Jeśli dziś zjadł ser, jutro z równym prawdopodobieństwem zje sałatę lub winogrona.
  • Jeśli dziś jadł winogrona, jutro będzie jadł winogrona z prawdopodobieństwem 1/10, ser z prawdopodobieństwem 4/10 i sałatę z prawdopodobieństwem 5/10.
  • Jeśli dziś jadł sałatę, jutro będzie jadł winogrona z prawdopodobieństwem 4/10 lub ser z prawdopodobieństwem 6/10. Jutro już nie zje sałaty.

Nawyki żywieniowe tego stworzenia można modelować za pomocą łańcuszka Markowa, ponieważ jego wybór na jutro zależy wyłącznie od tego, co zjadł dzisiaj, a nie od tego, co jadł wczoraj lub kiedykolwiek w przeszłości. Jedną statystyczną właściwością, którą można obliczyć, jest oczekiwany procent, w długim okresie, dni, w których stworzenie będzie jadło winogrona.

Seria niezależnych zdarzeń (na przykład seria rzutów monetą) spełnia formalną definicję łańcucha Markowa. Jednak teoria ta jest zwykle stosowana tylko wtedy, gdy rozkład prawdopodobieństwa następnego kroku zależy nietrywialnie od aktualnego stanu.

Przykład niemarkowski

Załóżmy, że w torebce znajduje się pięć ćwierćdolarówek (każda warta 25 ), pięć dziesięciocentówek (każda warta 10 ) i pięć pięciocentówek (każda warta 5 ¢) i jedna po drugiej monety są losowo dobierane z sakiewki i są na stole. Jeśli oznacza całkowitą wartość monet ustawiony na stole po n rysuje, z , to sekwencja jest nie proces Markowa.

Aby zobaczyć, dlaczego tak się dzieje, załóżmy, że w pierwszych sześciu losowaniach wylosowano wszystkie pięć pięciocentówek i jedną czwartą. Tak więc . Jeśli znamy nie tylko , ale także wcześniejsze wartości, możemy określić, które monety zostały wylosowane, i wiemy, że następna moneta nie będzie pięciocentówką; więc możemy to wyznaczyć z prawdopodobieństwem 1. Ale jeśli nie znamy wcześniejszych wartości, to tylko na podstawie wartości możemy się domyślić, że wylosowaliśmy cztery dziesięciocentówki i dwie pięciocentówki, w takim przypadku z pewnością można by wylosować kolejną pięciocentówkę Następny. Tak więc na nasze domysły ma wpływ nasza wiedza o wartościach sprzed .

Możliwe jest jednak modelowanie tego scenariusza jako procesu Markowa. Zamiast definiować do reprezentowania całkowitą wartość monet na stole, możemy zdefiniować do reprezentowania liczbę różnych rodzajów monet na stole. Na przykład można zdefiniować stan, w którym po 6 losowaniach jeden po drugim na stole znajduje się jedna czwarta, zero dziesięciocentówek i pięć pięciocentówek. Ten nowy model byłby reprezentowany przez 216 możliwych stanów (tj. stany 6x6x6, ponieważ każdy z trzech rodzajów monet może mieć na stole od 0 do 5 monet pod koniec 6 losowań). Załóżmy, że pierwsze losowanie skutkuje stanem . Prawdopodobieństwo osiągnięcia teraz zależy od ; na przykład państwo nie jest możliwe. Po drugim losowaniu trzecie losowanie zależy od tego, jakie monety zostały do ​​tej pory wylosowane, ale już nie tylko od monet, które zostały wylosowane dla pierwszego stanu (ponieważ do scenariusza dodano już probabilistycznie ważne informacje). W ten sposób prawdopodobieństwo stanu zależy wyłącznie od wyniku stanu.

Formalna definicja

Dyskretny łańcuch Markowa

Łańcuch Markowa o czasie dyskretnym to ciąg zmiennych losowych X 1 , X 2 , X 3 , ... o własności Markowa , a mianowicie, że prawdopodobieństwo przejścia do następnego stanu zależy tylko od stanu obecnego, a nie od poprzedniego stwierdza:

jeśli oba prawdopodobieństwa warunkowe są dobrze zdefiniowane, to znaczy, jeśli

Możliwe wartości X i tworzą policzalny zbiór S zwany przestrzenią stanów łańcucha.

Wariacje

  • Jednorodne w czasie łańcuchy Markowa to procesy, w których
    dla wszystkich n . Prawdopodobieństwo przejścia jest niezależne od n .
  • Stacjonarne łańcuchy Markowa to procesy, w których
    dla wszystkich n i k . Zgodnie z regułą Bayesa można udowodnić, że każdy łańcuch stacjonarny jest jednorodny w czasie.
    Warunkiem koniecznym i wystarczającym, aby jednorodny w czasie łańcuch Markowa był stacjonarny, jest to, że rozkład jest stacjonarnym rozkładem łańcucha Markowa.
  • Łańcuch Markowa z pamięcią (lub łańcuch Markowa porządku m ), gdzie m jest skończone, jest procesem satysfakcjonującym
    Innymi słowy, przyszły stan zależy od przeszłych m stanów. Możliwe jest skonstruowanie łańcucha, z którego ma „klasyczną” własność Markowa, przyjmując jako przestrzeń stanów uporządkowane m -krotki wartości X , tj . .

Ciągły łańcuch Markowa

Stała czasu łańcuch Markowa ( X , T ) T  ≥ 0 jest określony przez stan ograniczonej lub policzalnych przestrzeni S , A szybkość przejścia macierz Q o wymiarach równych szerokości przestrzeni stanu i wstępnego rozkładu prawdopodobieństwa określonej w przestrzeni stanu. Dla i  ≠  j , elementy q ij są nieujemne i opisują szybkość przejścia procesu ze stanu i do stanu j . Elementy q ii są dobrane tak, że każdy wiersz macierzy szybkości przejścia sumuje się do zera, podczas gdy sumy wierszy macierzy prawdopodobieństwa przejścia w (dyskretnym) łańcuchu Markowa są równe jeden.

Istnieją trzy równoważne definicje procesu.

Nieskończona definicja

Ciągły łańcuch Markowa charakteryzuje się szybkościami przejść, pochodnymi względem czasu prawdopodobieństw przejścia między stanami i oraz j.

Niech będzie zmienną losową opisującą stan procesu w czasie t i załóżmy, że proces jest w stanie i w czasie t . Wtedy wiedza , jest niezależna od poprzednich wartości , a jako h → 0 dla wszystkich j i dla wszystkich t ,

,

gdzie jest delta Kroneckera , używając notacji little-o . Mogą być postrzegane jako pomiar jak szybko przejście od I do j dzieje.

Skok łańcucha/definicja czasu utrzymywania

Zdefiniuj dyskretny łańcuch Markowa Y n do opisania n- tego skoku procesu i zmienne S 1 , S 2 , S 3 , ... do opisania czasów utrzymywania w każdym ze stanów, w których S i podąża za rozkładem wykładniczym z szybkością parametr − q Y i Y i .

Definicja prawdopodobieństwa przejścia

Dla dowolnej wartości n = 0, 1, 2, 3, ... i czasów indeksowanych do tej wartości n : t 0 , t 1 , t 2 , ... oraz wszystkich stanów zarejestrowanych w tych czasach i 0 , i 1 , ja 2 , ja 3 , ... zawiera to

gdzie p ij jest rozwiązaniem równania postępującego ( równanie różniczkowe pierwszego rzędu )

z warunkiem początkowym P(0) jest macierzą jednostkową .

Skończona przestrzeń stanów

Jeżeli przestrzeń stan jest ograniczony rozkład prawdopodobieństwa przejścia może być przedstawiony za pomocą matrycy o nazwie macierz transformacji, z ( i , j ), H elementem z P równym

Ponieważ każdy wiersz sumy P do jednego i wszystkie elementy są nieujemne, P jest prawą macierzą stochastyczną .

Dystrybucja stacjonarna względem wektorów własnych i uproszczeń

Rozkład stacjonarny π jest wektorem (wierszowym), którego wpisy są nieujemne i sumują się do 1, nie zmienia się w wyniku działania na nim macierzy przejścia P , a więc jest określony wzorem

Porównując tę ​​definicję z definicją wektora własnego , widzimy, że te dwa pojęcia są ze sobą powiązane i że

jest znormalizowaną ( ) wielokrotnością lewego wektora własnego e macierzy przejścia P o wartości własnej równej 1. Jeśli istnieje więcej niż jeden wektor własny, to ważona suma odpowiadających stanów stacjonarnych również jest stanem stacjonarnym. Ale w przypadku łańcucha Markowa zwykle bardziej interesuje nas stan stacjonarny, czyli granica ciągu rozkładów dla pewnego rozkładu początkowego.

Wartości rozkładu stacjonarnego są związane z przestrzenią stanów P, a jej wektory własne mają zachowane względne proporcje. Ponieważ składowe π są dodatnie, a ograniczenie, że ich suma jest jednością, można napisać od nowa, ponieważ widzimy, że iloczyn skalarny π z wektorem, którego wszystkie składowe wynoszą 1, jest jednością i że π leży na simpleksie .

Jednorodny w czasie łańcuch Markowa ze skończoną przestrzenią stanów

Jeżeli łańcuch Markowa jest jednorodny w czasie, to macierz przejścia P jest taka sama po każdym kroku, więc prawdopodobieństwo przejścia k- kroku można obliczyć jako k-tą potęgę macierzy przejścia P k .

Jeżeli łańcuch Markowa jest nieredukowalny i aperiodyczny, to istnieje jednoznaczny rozkład stacjonarny π . Dodatkowo w tym przypadku P k zbiega się do macierzy pierwszego rzędu, w której każdy wiersz jest rozkładem stacjonarnym π :

gdzie 1 jest wektorem kolumnowym ze wszystkimi wpisami równymi 1. Mówi o tym twierdzenie Perrona-Frobeniusa . Jeśli w jakikolwiek sposób zostanie znaleziony, stacjonarny rozkład danego łańcucha Markowa można łatwo określić dla dowolnego początkowego rozkładu, co zostanie wyjaśnione poniżej.

W przypadku niektórych macierzy stochastycznych P granica nie istnieje, podczas gdy rozkład stacjonarny istnieje, jak pokazano w tym przykładzie:

(Ten przykład ilustruje okresowy łańcuch Markowa).

Ponieważ istnieje wiele różnych specjalnych przypadków do rozważenia, proces znajdowania tego limitu, jeśli istnieje, może być długotrwałym zadaniem. Istnieje jednak wiele technik, które mogą pomóc w znalezieniu tego limitu. Niech P będzie macierzą n × n i zdefiniuj

To zawsze prawda

Odjęcie Q od obu stron i faktoring, a następnie daje

gdzie I n jest macierzą jednostkową o rozmiarze n , a 0 n , n jest macierzą zerową o rozmiarze n × n . Mnożenie przez siebie macierzy stochastycznych zawsze daje inną macierz stochastyczną, więc Q musi być macierzą stochastyczną (patrz definicja powyżej). Czasami wystarczy użyć powyższego równania macierzowego i faktu, że Q jest macierzą stochastyczną do rozwiązania dla Q . Uwzględniając fakt, że suma każdego wiersza w P wynosi 1, istnieje n+1 równań do wyznaczenia n niewiadomych, więc obliczeniowo łatwiej jest, jeśli z jednej strony wybierze się jeden wiersz w Q i zastąpi każdy z jego elementów jednym , a z drugiej podstawia odpowiedni element (ten z tej samej kolumny) w wektorze 0 , a następnie mnoży ten ostatni wektor w lewo przez odwrotność transformowanej poprzedniej macierzy, aby znaleźć Q .

Oto jedna metoda, aby to zrobić: najpierw zdefiniuj funkcję f ( A ), która zwraca macierz A z jej skrajną prawą kolumną zamienioną na wszystkie jedynki. Jeśli [ f ( PI n )] −1 istnieje wtedy

Wyjaśnij: Pierwotne równanie macierzowe jest równoważne układowi n×n równań liniowych w n×n zmiennych. I jest n więcej równań liniowych z faktu, że Q jest prawą macierzą stochastyczną, której każdy wiersz sumuje się do 1. Więc potrzebuje n×n niezależnych równań liniowych (n×n+n) do rozwiązania dla n× n zmiennych. W tym przykładzie n równań z „Q pomnożone przez skrajną prawą kolumnę (P-In)” zostało zastąpione przez n stochastyczne.

Jedną rzeczą jest fakt, że jeżeli p ma elementu P ı , I na jego głównej przekątnej jest równe 1, a i p wiersza lub kolumny inaczej wypełnione przez 0, a następnie, że wierszu lub kolumnie pozostanie niezmienione u wszystkich kolejnych uprawnienia P k . Stąd i- ty wiersz lub kolumna Q będzie miał jedynkę i zera w tych samych pozycjach, co w P .

Prędkość konwergencji do rozkładu stacjonarnego

Jak wspomniano wcześniej, z równania (jeśli istnieje) rozkład stacjonarny (lub ustalony) π jest lewym wektorem własnym macierzy stochastycznej wierszy P . Następnie zakładając, że P jest diagonalizowalny lub równoważnie, że P ma n liniowo niezależnych wektorów własnych, prędkość zbieżności jest opracowywana w następujący sposób. (W przypadku nie diagonalizable, to znaczy uszkodzone matryce , może rozpocząć się z Jordan postaci normalnej, z P i dokonać nieco większy udział zestaw argumentów w podobny sposób.

Niech U będzie macierzą wektorów własnych (każdy znormalizowany do normy L2 równej 1), gdzie każda kolumna jest lewym wektorem własnym P i niech Σ będzie macierzą diagonalną lewych wartości własnych P , czyli Σ = diag( λ 1 , λ 2 , λ 3 ,..., λ n ). Następnie przez dekompozycję własną

Niech wartości własne zostaną wyliczone w taki sposób, że:

Ponieważ P jest rzędową macierzą stochastyczną, jej największa lewa wartość własna wynosi 1. Jeśli istnieje jednoznaczny rozkład stacjonarny, to największa wartość własna i odpowiadający jej wektor własny również są unikatowe (ponieważ nie ma innego π, który rozwiązuje powyższe równanie rozkładu stacjonarnego). Niech u i będzie i -tą kolumną macierzy U , czyli u i jest lewym wektorem własnym P odpowiadającym λ i . Niech x będzie również wektorem o długości n wierszy, który reprezentuje prawidłowy rozkład prawdopodobieństwa; ponieważ wektory własne u i span możemy pisać

Jeśli pomnożymy x przez P od prawej strony i będziemy kontynuować tę operację z wynikami, w końcu otrzymamy rozkład stacjonarny π . Innymi słowy, π = u ixPP ... P = xP k jako k → ∞. To znaczy

Ponieważ π = u 1 , π ( k ) zbliża się do π jako k → ∞ z prędkością rzędu λ 2 / λ 1 wykładniczo. Wynika to z tego, że λ 2 / λ 1 jest wyrazem dominującym. Im mniejszy stosunek, tym szybsza konwergencja. Szum losowy w rozkładzie stanu π może również przyspieszyć tę zbieżność do rozkładu stacjonarnego.

Ogólna przestrzeń stanu

Łańcuchy Harrisa

Wiele wyników dla łańcuchów Markowa ze skończoną przestrzenią stanów można uogólnić na łańcuchy o niepoliczalnej przestrzeni stanów poprzez łańcuchy Harrisa .

Zastosowanie łańcuchów Markowa w metodach Monte Carlo łańcuchów Markowa obejmuje przypadki, w których proces przebiega w ciągłej przestrzeni stanów.

Lokalnie oddziałujące łańcuchy Markowa

Rozważenie zbioru łańcuchów Markowa, których ewolucja uwzględnia stan innych łańcuchów Markowa, wiąże się z pojęciem lokalnie oddziałujących łańcuchów Markowa . Odpowiada to sytuacji, gdy przestrzeń stanów ma postać iloczynu (kartezjańskiego). Zobacz oddziałujący system cząstek i stochastyczne automaty komórkowe (probabilistyczne automaty komórkowe). Zobacz na przykład interakcja procesów Markowa lub

Nieruchomości

Dwa stany komunikują się ze sobą, jeśli oba są osiągalne przez sekwencję przejść o dodatnim prawdopodobieństwie. Jest to relacja równoważności, która daje zbiór komunikujących się klas. Klasa jest zamknięta, jeśli prawdopodobieństwo opuszczenia klasy wynosi zero. Łańcuch Markowa jest nieredukowalny, jeśli istnieje jedna klasa komunikująca się, przestrzeń stanów.

Stan i ma okres , jeżeli jest największy wspólny dzielnik liczby przejść przez który i może być osiągnięte, począwszy od I . To jest:

Mówi się, że stan i jest przejściowy, jeśli począwszy od i istnieje niezerowe prawdopodobieństwo, że łańcuch nigdy nie powróci do i . W przeciwnym razie nawraca. Dla stanu powtarzalnego i średni czas trafienia definiuje się jako:

Stan i jest dodatni, rekurencyjny, jeśli jest skończony, aw przeciwnym razie null rekurencyjny. Okresowość, przemijanie, rekurencja oraz dodatnia i zerowa rekurencja są właściwościami klasy — to znaczy, jeśli jeden stan ma tę właściwość, to wszystkie stany w jego komunikującej się klasie mają tę właściwość.

Stan i nazywamy absorbującym, jeśli nie ma przejść wychodzących ze stanu.

Ergodyczność

Mówi się, że stan i jest ergodyczny, jeśli jest aperiodyczny i dodatni, nawracający. Innymi słowy, stan i jest ergodyczny, jeśli jest powtarzalny, ma okres 1 i ma skończony średni czas nawrotu. Jeśli wszystkie stany w nieredukowalnym łańcuchu Markowa są ergodyczne, to mówi się, że łańcuch jest ergodyczny.

Można wykazać, że skończony nieredukowalny łańcuch Markowa jest ergodyczny, jeśli ma stan aperiodyczny. Bardziej ogólnie, łańcuch Markowa jest ergodyczny, jeśli istnieje liczba N taka, że ​​dowolny stan można osiągnąć z dowolnego innego stanu w dowolnej liczbie kroków mniejszej lub równej liczbie N . W przypadku w pełni połączonej macierzy przejść, gdzie wszystkie przejścia mają niezerowe prawdopodobieństwo, warunek ten jest spełniony przy  N  = 1.

Łańcuch Markowa z więcej niż jednym stanem i tylko jednym wychodzącym przejściem na stan jest albo nieredukowalny, albo nie aperiodyczny, a zatem nie może być ergodyczny.

reprezentacje markowskie

W niektórych przypadkach, pozornie niemarkowskie procesy mogą nadal mieć reprezentacje markowskie, konstruowane przez rozszerzenie pojęcia stanów „aktualnych” i „przyszłych”. Na przykład niech X będzie procesem niemarkowskim. Następnie zdefiniuj proces Y , taki, że każdy stan Y reprezentuje przedział czasowy stanów X . Matematycznie przybiera to postać:

Jeśli Y ma własność Markowa, to jest reprezentacją Markowa X .

Przykładem procesu niemarkowskiego z reprezentacją Markowską jest autoregresywny szereg czasowy rzędu większego niż jeden.

Czasy uderzeń

Czas trafienia to czas, począwszy od danego zestawu stanów, aż łańcuch dotrze do danego stanu lub zestawu stanów. Rozkład takiego okresu czasu ma rozkład typu fazowego. Najprostszym takim rozkładem jest rozkład pojedynczego przejścia o rozkładzie wykładniczym.

Oczekiwane czasy trafień

Dla podzbioru stanów A  ⊆  S , wektor k A czasów trafień (gdzie element reprezentuje wartość oczekiwaną , począwszy od stanu i , w którym łańcuch wchodzi w jeden ze stanów zbioru A ) jest minimalnym nieujemnym rozwiązaniem

Odwrócenie czasu

Dla CTMC X t , proces odwróconej w czasie określa się . Zgodnie z lematem Kelly'ego proces ten ma taki sam rozkład stacjonarny jak proces do przodu.

Mówi się, że łańcuch jest odwracalny, jeśli proces odwrócony jest taki sam jak proces przekazywania. Kryterium Kołmogorowa mówi, że koniecznym i wystarczającym warunkiem odwracalności procesu jest to, że iloczyn szybkości przejść wokół zamkniętej pętli musi być taki sam w obu kierunkach.

Wbudowany łańcuch Markowa

Jeden ze sposobów znajdowania stacjonarną rozkład prawdopodobieństwa , gatunku , z na ergodycznej ciągłym czas łańcucha Markowa, Q , jest pierwszym ustaleniu jego osadzonym łańcucha Markowa (EMC) . Ściśle mówiąc, EMC jest zwykłym łańcuchem Markowa w czasie dyskretnym, czasami określanym jako proces skoku . Każdy element jednostopniowej macierzy prawdopodobieństwa przejścia EMC, S , jest oznaczony przez s ij i reprezentuje warunkowe prawdopodobieństwo przejścia ze stanu i do stanu j . Te warunkowe prawdopodobieństwa można znaleźć przez:

Z tego S można zapisać jako

gdzie I jest macierzą jednostkową, a diag( Q ) jest macierzą diagonalną utworzoną przez wybranie głównej przekątnej z macierzy Q i ustawienie wszystkich pozostałych elementów na zero.

Aby znaleźć stacjonarny wektor rozkładu prawdopodobieństwa, musimy następnie znaleźć taki, że

przy czym wektor rzędzie, tak, że wszystkie składniki są większe niż 0, a = 1. W tym π mogą być znalezione

( S może być okresowe, nawet jeśli Q nie występuje. Po znalezieniu π należy je znormalizować do wektora jednostkowego .)

Innym procesem w czasie dyskretnym, który można wyprowadzić z łańcucha Markowa w czasie ciągłym, jest -szkielet — łańcuch Markowa (w czasie dyskretnym) utworzony przez obserwowanie X ( t ) w odstępach co δ jednostek czasu. Zmienne losowe X (0),  X (δ),  X (2δ), ... podają sekwencję stanów odwiedzanych przez -szkielet.

Specjalne rodzaje łańcuchów Markowa

Model Markowa

Modele Markowa służą do modelowania systemów zmieniających się. Istnieją 4 główne typy modeli, które uogólniają łańcuchy Markowa w zależności od tego, czy każdy stan sekwencyjny jest obserwowalny, czy nie, oraz czy system ma być korygowany na podstawie dokonanych obserwacji:

Stan systemu jest w pełni obserwowalny Stan systemu jest częściowo obserwowalny
System jest autonomiczny Łańcuch Markowa Ukryty model Markowa
System jest kontrolowany Proces decyzyjny Markowa Częściowo obserwowalny proces decyzyjny Markowa

Schemat Bernoulliego

Schemat Bernoulliego jest szczególnym przypadkiem łańcucha Markowa gdzie macierz prawdopodobieństwo przejścia ma identyczne rzędach, co oznacza, że następny stan jest nawet niezależna od aktualnego stanu (oprócz tego, że niezależnie od ostatnich Zjednoczonych). Schemat Bernoulliego z tylko dwoma możliwymi stanami jest znany jako proces Bernoulliego .

Należy jednak zauważyć, że według twierdzenia Ornsteina o izomorfizmie każdy aperiodyczny i nieredukowalny łańcuch Markowa jest izomorficzny ze schematem Bernoulliego; można zatem równie dobrze twierdzić, że łańcuchy Markowa są „szczególnym przypadkiem” schematów Bernoulliego. Izomorfizm na ogół wymaga skomplikowanego przekodowania. Twierdzenie o izomorfizmie jest nawet nieco silniejsze: stwierdza, że każdy stacjonarny proces stochastyczny jest izomorficzny ze schematem Bernoulliego; łańcuch Markowa to tylko jeden z takich przykładów.

Podprzesunięcie typu skończonego

Gdy matryca Markowa otrzymuje matrycy przylegania z ograniczonym wykres uzyskany przesuwane do haseł topologiczna łańcuchów Markowa lub subshift skończonej typu . Macierz Markowa, która jest zgodna z macierzą sąsiedztwa, może wówczas zapewnić miarę przesunięcia podrzędnego. Wiele chaotycznych układów dynamicznych jest izomorficznych z topologicznymi łańcuchami Markowa; Przykłady obejmują Dyfeomorfizm o zamkniętych kolektorów , w systemie Prouhet-Thue-Morse , w systemie Chacon , systemy sofic , systemy wolne od kontekstu i systemy blokowe kodowanie .

Aplikacje

Badania wykazały zastosowanie i przydatność łańcuchów Markowa w wielu dziedzinach, takich jak fizyka, chemia, biologia, medycyna, muzyka, teoria gier i sport.

Fizyka

Systemy Markowa pojawiają się szeroko w termodynamice i mechanice statystycznej , ilekroć prawdopodobieństwa są używane do reprezentowania nieznanych lub niemodelowanych szczegółów systemu, jeśli można założyć, że dynamika jest niezmienna w czasie i że nie trzeba brać pod uwagę odpowiedniej historii, która nie została już uwzględniona w opisie stanu. Na przykład stan termodynamiczny działa z rozkładem prawdopodobieństwa, który jest trudny lub kosztowny do uzyskania. Dlatego metoda Markowa Łańcucha Monte Carlo może być użyta do losowego losowania próbek z czarnej skrzynki w celu przybliżenia rozkładu prawdopodobieństwa atrybutów w zakresie obiektów.

Ścieżki, w całkowym sformułowaniu ścieżkowym mechaniki kwantowej, są łańcuchami Markowa.

Łańcuchy Markowa są wykorzystywane w symulacjach sieciowej QCD .

Chemia

Kinetyka Michaelisa-Mentena . Enzym (E) wiąże substrat (S) i wytwarza produkt (P). Każda reakcja jest przejściem stanu w łańcuchu Markowa.

Sieć reakcji to układ chemiczny obejmujący wiele reakcji i rodzajów substancji chemicznych. Najprostsze modele stochastyczne takich sieci traktują system jako ciągły łańcuch Markowa, przy czym stanem jest liczba cząsteczek każdego gatunku i reakcjami modelowanymi jako możliwe przejścia łańcucha. Łańcuchy Markowa i procesy Markowa w czasie ciągłym są przydatne w chemii, gdy układy fizyczne ściśle zbliżają się do właściwości Markowa. Na przykład wyobraźmy sobie dużą liczbę n cząsteczek w roztworze w stanie A, z których każda może przejść reakcję chemiczną do stanu B z pewną średnią szybkością. Być może cząsteczka jest enzymem, a stany odnoszą się do tego, jak jest pofałdowana. Stan każdego pojedynczego enzymu następuje po łańcuchu Markowa, a ponieważ cząsteczki są zasadniczo niezależne od siebie, liczba cząsteczek w stanie A lub B w danym momencie jest n razy większa niż prawdopodobieństwo, że dana cząsteczka będzie w tym stanie.

Klasyczny model aktywności enzymu, kinetyka Michaelisa-Mentena , można postrzegać jako łańcuch Markowa, w którym na każdym etapie reakcja przebiega w pewnym kierunku. Chociaż Michaelis-Menten jest dość prosty, o wiele bardziej skomplikowane sieci reakcji można również modelować za pomocą łańcuchów Markowa.

Algorytm oparty na łańcuchu Markowa został również wykorzystany do skoncentrowania opartego na fragmentach wzrostu chemikaliów in silico w kierunku pożądanej klasy związków, takich jak leki lub produkty naturalne. Gdy cząsteczka rośnie, fragment jest wybierany z powstającej cząsteczki jako stan „bieżący”. Nie jest świadomy swojej przeszłości (to znaczy nie jest świadomy tego, co jest już z nią związane). Następnie przechodzi do następnego stanu, gdy jest do niego dołączony fragment. Prawdopodobieństwa przejścia są szkolone na bazach danych autentycznych klas związków.

Również wzrost (i skład) kopolimerów można modelować za pomocą łańcuchów Markowa. Na podstawie współczynników reaktywności monomerów tworzących rosnący łańcuch polimerowy można obliczyć skład łańcucha (na przykład, czy monomery mają tendencję do dodawania naprzemiennie lub w długich seriach tego samego monomeru). Ze względu na efekty steryczne, efekty Markowa drugiego rzędu mogą również odgrywać rolę we wzroście niektórych łańcuchów polimerowych.

Podobnie, zasugerowano, że krystalizację i wzrost niektórych epitaksjalnych materiałów tlenków supersieci można dokładnie opisać za pomocą łańcuchów Markowa.

Biologia

Łańcuchy Markowa są wykorzystywane w różnych dziedzinach biologii. Godne uwagi przykłady obejmują:

Testowanie

Kilku teoretyków zaproponowało ideę testu statystycznego łańcucha Markowa (MCST), metody łączenia łańcuchów Markowa w „ koc Markowa ”, układania tych łańcuchów w kilka warstw rekurencyjnych („waferowanie”) i wytwarzania bardziej wydajnych zestawów testowych – próbki — jako zamiennik dla wyczerpujących testów. MCST mają również zastosowanie w sieciach opartych na stanie czasowym; Artykuł Chilukuri et al. zatytułowany „Sieci uzasadniające niepewność czasową dla łączenia dowodów z aplikacjami do wykrywania i śledzenia obiektów” (ScienceDirect) zawiera tło i studium przypadku dotyczące stosowania MCST w szerszym zakresie aplikacji.

Zmienność promieniowania słonecznego

Oceny zmienności natężenia promieniowania słonecznego są przydatne w zastosowaniach związanych z energią słoneczną . Zmienność irradiancji słonecznej w dowolnym miejscu w czasie jest głównie konsekwencją deterministycznej zmienności trajektorii ruchu słońca przez kopułę nieba oraz zmienności zachmurzenia. Zmienność dostępnego promieniowania słonecznego na powierzchni Ziemi została wymodelowana za pomocą łańcuchów Markowa, w tym również modelowanie dwóch stanów przejrzystości i zachmurzenia jako dwustanowego łańcucha Markowa.

Rozpoznawanie mowy

Ukryte modele Markowa są podstawą większości nowoczesnych systemów automatycznego rozpoznawania mowy .

Teoria informacji

Łańcuchy Markowa są używane podczas przetwarzania informacji. Słynny artykuł Claude'a Shannona z 1948 r . Matematyczna teoria komunikacji , który w jednym kroku stworzył dziedzinę teorii informacji , rozpoczyna się wprowadzeniem pojęcia entropii poprzez modelowanie języka angielskiego Markowa. Takie wyidealizowane modele mogą uchwycić wiele statystycznych prawidłowości systemów. Nawet bez doskonałego opisu pełnej struktury systemu, takie modele sygnałów mogą umożliwić bardzo efektywną kompresję danych dzięki technikom kodowania entropijnego , takim jak kodowanie arytmetyczne . Pozwalają również na efektywną estymację stanu i rozpoznawanie wzorców . Łańcuchy Markowa odgrywają również ważną rolę w uczeniu się przez wzmacnianie .

Łańcuchy Markowa są również podstawą ukrytych modeli Markowa, które są ważnym narzędziem w tak różnorodnych dziedzinach, jak sieci telefoniczne (wykorzystujące algorytm Viterbiego do korekcji błędów), rozpoznawanie mowy i bioinformatyka (m.in. w wykrywaniu przegrupowań).

W lzma algorytm kompresji bezstratnej łączy łańcuchów Markowa z kompresją Lempel-Ziv osiągnąć bardzo wysoki stopień ściśnięcia.

Teoria kolejkowania

Łańcuchy Markowa są podstawą do analitycznego traktowania kolejek ( teoria kolejek ). Agner Krarup Erlang zainicjował ten temat w 1917 roku. To sprawia, że ​​mają kluczowe znaczenie dla optymalizacji wydajności sieci telekomunikacyjnych, w których wiadomości często muszą konkurować o ograniczone zasoby (takie jak przepustowość).

Wiele modeli kolejkowania wykorzystuje łańcuchy Markowa w czasie ciągłym. Na przykład kolejka M/M/1 to CTMC na nieujemnych liczbach całkowitych, w których przejścia w górę od i do i  + 1 występują z szybkością λ zgodnie z procesem Poissona i opisują przybycie zadań, podczas gdy przejścia od i do i  – 1 (dla i  > 1) występują z szybkością μ (czasy obsługi zadań są rozłożone wykładniczo) i opisują wykonane usługi (wyjścia) z kolejki.

Aplikacje internetowe

Diagram stanu reprezentujący algorytm PageRank z prawdopodobieństwem przejścia M lub .

PageRank od strony sieci Web jako używane przez Google jest definiowana za pomocą łańcucha Markowa. Jest to prawdopodobieństwo znalezienia się na stronie w rozkładzie stacjonarnym w następującym łańcuchu Markowa na wszystkich (znanych) stronach internetowych. Jeśli jest to liczba znanych stron internetowych, a strona zawiera linki do niej, to prawdopodobieństwo przejścia dotyczy wszystkich stron, do których prowadzą linki, i wszystkich stron, do których nie są linki. Przyjmuje się, że parametr wynosi około 0,15.

Modele Markowa zostały również wykorzystane do analizy zachowań użytkowników w nawigacji internetowej. Przejście użytkownika przez łącze internetowe na określonej stronie internetowej może być modelowane za pomocą modeli Markowa pierwszego lub drugiego rzędu i może być wykorzystywane do przewidywania przyszłej nawigacji i personalizacji strony internetowej dla indywidualnego użytkownika.

Statystyka

Metody łańcucha Markowa stały się również bardzo ważne dla generowania sekwencji liczb losowych, aby dokładnie odzwierciedlić bardzo skomplikowane pożądane rozkłady prawdopodobieństwa, za pomocą procesu zwanego Monte Carlo łańcucha Markowa (MCMC). W ostatnich latach zrewolucjonizowało to praktyczność metod wnioskowania bayesowskiego , umożliwiając symulowanie szerokiego zakresu rozkładów a posteriori i znajdowanie ich parametrów numerycznie.

Ekonomia i finanse

Łańcuchy Markowa są wykorzystywane w finansach i ekonomii do modelowania wielu różnych zjawisk, w tym dystrybucji dochodów, dystrybucji wielkości firm, cen aktywów i krachów rynkowych. DG Champernowne zbudował model łańcucha Markowa dystrybucji dochodów w 1953 roku. Herbert A. Simon i współautor Charles Bonini wykorzystali model łańcucha Markowa do wyprowadzenia stacjonarnego rozkładu Yule'a rozmiarów firm. Louis Bachelier jako pierwszy zaobserwował, że ceny akcji podążają w sposób przypadkowy. Błądzenie losowe było później postrzegane jako dowód na korzyść hipotezy rynku efektywnego, a modele błądzenia losowego były popularne w literaturze z lat 60. XX wieku. Modele cykli koniunkturalnych polegające na zmianie reżimu zostały spopularyzowane przez Jamesa D. Hamiltona (1989), który wykorzystał łańcuch Markowa do modelowania zmian pomiędzy okresami wysokiego i niskiego wzrostu PKB (lub alternatywnie, ekspansji gospodarczej i recesji). Nowszym przykładem jest model multifraktalny z przełączaniem Markowa autorstwa Laurenta E. Calveta i Adlai J. Fishera, który opiera się na wygodzie wcześniejszych modeli przełączania reżimów. Wykorzystuje dowolnie duży łańcuch Markowa, aby sterować poziomem zmienności zwrotów z aktywów.

Dynamiczna makroekonomia intensywnie wykorzystuje łańcuchy Markowa. Przykładem jest użycie łańcuchów Markowa do egzogenicznego modelowania cen akcji (akcji) w warunkach równowagi ogólnej .

Agencje ratingowe sporządzają roczne tabele prawdopodobieństw przejścia dla obligacji o różnych ratingach kredytowych.

Nauki społeczne

Łańcuchy Markowa są zwykle używane do opisywania argumentów zależnych od ścieżki , gdzie obecne konfiguracje strukturalne warunkują przyszłe wyniki. Przykładem jest przeformułowanie pomysłu, pierwotnie z powodu Karl Marx „s Das Kapital , wiążąc rozwoju gospodarczego do powstania kapitalizmu . W obecnych badaniach powszechnie stosuje się łańcuch Markowa do modelowania, w jaki sposób kraj osiągnie określony poziom rozwoju gospodarczego, konfigurację czynników strukturalnych, takich jak wielkość klasy średniej , stosunek liczby mieszkań w mieście do wsi, wskaźnik od politycznej mobilizacji, itd., będzie generować większe prawdopodobieństwo przechodzenia od autorytarnego do systemu demokratycznego .

Gry

Łańcuchy Markowa można wykorzystać do modelowania wielu gier losowych. Na przykład gry dla dzieci Snakes and Ladders i „ Hi Ho! Cherry-O ” są dokładnie reprezentowane przez łańcuchy Markowa. W każdej turze gracz zaczyna w określonym stanie (na danym kwadracie) i stamtąd ma stałe szanse na przejście do pewnych innych stanów (kwadratów).

Muzyka

Łańcuchy Markowa są wykorzystywane w algorytmicznej kompozycji muzycznej , szczególnie w oprogramowaniu takim jak Csound , Max i SuperCollider . W łańcuchu pierwszego rzędu stany systemu stają się wartościami nuty lub wysokości dźwięku, a wektor prawdopodobieństwa dla każdej nuty jest konstruowany, uzupełniając macierz prawdopodobieństwa przejścia (patrz poniżej). Algorytm jest skonstruowany w celu wygenerowania wyjściowych wartości nut na podstawie wag macierzy przejścia, które mogą być wartościami nut MIDI , częstotliwością ( Hz ) lub dowolną inną pożądaną metryką.

Macierz pierwszego rzędu
Notatka A C E
A 0,1 0,6 0,3
C 0,25 0,05 0,7
E 0,7 0,3 0
Macierz drugiego rzędu
Uwagi A D g
AA 0,18 0,6 0,22
OGŁOSZENIE 0,5 0,5 0
AG 0,15 0,75 0,1
DD 0 0 1
DA 0,25 0 0,75
DG 0,9 0,1 0
GG 0,4 0,4 0,2
GA 0,5 0,25 0,25
GD 1 0 0

Łańcuch Markowa drugiego rzędu można wprowadzić, biorąc pod uwagę bieżący stan, a także stan poprzedni, jak wskazano w drugiej tabeli. Łańcuchy wyższego rzędu n -tego mają tendencję do „grupowania” ze sobą poszczególnych nut, podczas gdy czasami „odrywają się” na inne wzory i sekwencje. Te łańcuchy wyższego rzędu mają tendencję do generowania wyników z poczuciem struktury frazowej , a nie „bezcelowej wędrówki” wytwarzanej przez system pierwszego rzędu.

Łańcuchy Markowa mogą być używane strukturalnie, jak w Analogique A i B Xenakisa. Łańcuchy Markowa są również używane w systemach, które wykorzystują model Markowa do interaktywnego reagowania na sygnał muzyczny.

Zazwyczaj systemy muzyczne muszą wymusić określone ograniczenia kontrolne na generowanych przez siebie sekwencjach o skończonej długości, ale ograniczenia kontrolne nie są kompatybilne z modelami Markowa, ponieważ wywołują zależności dalekiego zasięgu, które naruszają hipotezę Markowa o ograniczonej pamięci. Aby przezwyciężyć to ograniczenie, zaproponowano nowe podejście.

Baseball

Modele łańcuchów Markowa są używane w zaawansowanej analizie baseballowej od 1960 roku, chociaż ich użycie jest nadal rzadkie. Każda połowa rundy meczu baseballowego pasuje do stanu łańcucha Markowa, jeśli uwzględni się liczbę biegaczy i outów. Podczas każdego ataku, są 24 możliwe kombinacje liczby autów i pozycji biegaczy. Mark Pankin pokazuje, że modele łańcuchów Markowa można wykorzystać do oceny biegów stworzonych zarówno dla indywidualnych graczy, jak i dla zespołu. Omówił również różne rodzaje strategii i warunków gry: w jaki sposób modele łańcucha Markowa zostały wykorzystane do analizy statystyk dotyczących sytuacji w grze, takich jak bunting i kradzież bazy oraz różnice podczas gry na trawie vs. AstroTurf .

Generatory tekstu Markowa

Procesy Markowa mogą być również wykorzystywane do generowania pozornie rzeczywistego tekstu na podstawie przykładowego dokumentu. Procesy Markowa są używane w różnych programach rekreacyjnych „ generatorów parodii ” (patrz prasa dysocjacyjna , Jeff Harrison, Mark V. Shaney i Academias Neutronium ). Istnieje kilka bibliotek do generowania tekstu o otwartym kodzie źródłowym wykorzystujących łańcuchy Markowa, w tym The RiTa Toolkit .

Prognozowanie probabilistyczne

Łańcuchy Markowa zostały wykorzystane do prognozowania w kilku obszarach: na przykład trendów cenowych, energii wiatrowej i natężenia promieniowania słonecznego. Modele prognostyczne łańcucha Markowa wykorzystują różne ustawienia, od dyskretyzacji szeregów czasowych do ukrytych modeli Markowa w połączeniu z falkami oraz modelu rozkładu mieszanin łańcuchowych Markowa (MCM).

Zobacz też

Uwagi

Bibliografia

  • AA Markov (1906) "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie lek lub lek". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete , 2-ya seriya, tom 15, s. 135–156.
  • AA Markow (1971). „Rozszerzenie twierdzeń granicznych teorii prawdopodobieństwa do sumy zmiennych połączonych w łańcuch”. przedrukowane w załączniku B: R. Howard. Dynamiczne systemy probabilistyczne, tom 1: Łańcuchy Markowa . John Wiley i Synowie.
  • Tekst klasyczny w tłumaczeniu: Markov, AA (2006). Przetłumaczone przez Link, David. „Przykład badania statystycznego tekstu Eugeniusza Oniegina dotyczącego połączenia próbek w łańcuchy” . Nauka w kontekście . 19 (4): 591-600. doi : 10.1017/s026988970601074 . S2CID  144854176 .
  • Leo Breiman (1992) [1968] Prawdopodobieństwo . Oryginalne wydanie opublikowane przez Addison-Wesley; przedrukowane przez Society for Industrial and Applied Mathematics ISBN  0-89871-296-3 . (patrz rozdział 7)
  • JL Doob (1953) Procesy stochastyczne . Nowy Jork: John Wiley and Sons ISBN  0-471-52369-0 .
  • SP Meyn i RL Tweedie (1993) Łańcuchy Markowa i stabilność stochastyczna . Londyn: Springer-Verlag ISBN  0-387-19832-6 . online: MCSS . Drugie wydanie ma się ukazać, Cambridge University Press, 2009.
  • SP Meyn. Techniki sterowania dla złożonych sieci . Cambridge University Press, 2007. ISBN  978-0-521-88441-9 . Dodatek zawiera skrót Meyn & Tweedie. online: [1]
  • Booth, Taylor L. (1967). Maszyny sekwencyjne i teoria automatów (wyd. 1). Nowy Jork, NY: John Wiley and Sons, Inc. Numer katalogowy karty Biblioteki Kongresu 67-25924.] Obszerna, obszerna książka przeznaczona dla specjalistów, napisana zarówno dla informatyków teoretycznych, jak i inżynierów elektryków. Ze szczegółowymi wyjaśnieniami technik minimalizacji stanu, FSM, maszyn Turinga, procesów Markowa i nierozstrzygalności. Doskonałe traktowanie procesów Markowa s. 449ff. Omawia transformacje Z, transformacje D w ich kontekście.
  • Kemeny, John G.; Hazletona Mirkila; J. Laurie Snella; Gerald L. Thompson (1959). Skończone struktury matematyczne (wyd. 1). Englewood Cliffs, NJ: Prentice-Hall, Inc. Numer katalogowy karty Biblioteki Kongresu 59-12841.Tekst klasyczny. por. Rozdział 6 Skończone łańcuchy Markowa, s. 384 i n.
  • John G. Kemeny & J. Laurie Snell (1960) Skończone łańcuchy Markowa , D. van Nostrand Company ISBN  0-442-04328-7
  • E. Nummelin. „Ogólne nieredukowalne łańcuchy Markowa i nieujemne operatory”. Cambridge University Press, 1984, 2004. ISBN  0-521-60494-X
  • Seneta, E. Macierze nieujemne i łańcuchy Markowa . II rew. red., 1981, XVI, 288 s., Seria Springer w miękkiej oprawie w statystyce. (Pierwotnie opublikowane przez Allen & Unwin Ltd., Londyn, 1973) ISBN  978-0-387-29765-1
  • Kishor S. Trivedi , Probability and Statistics with Reliability, Queueing and Computer Science Applications , John Wiley & Sons, Inc. New York, 2002. ISBN  0-471-33341-7 .
  • KS Trivedi i RASahner, SHARPE w wieku dwudziestu dwóch lat , tom. 36, nie. 4, s. 52–57, ACM SIGMETRICS Performance Evaluation Review, 2009.
  • RA Sahner, KS Trivedi i A. Puliafito, Analiza wydajności i niezawodności systemów komputerowych: podejście oparte na przykładach przy użyciu pakietu oprogramowania SHARPE , Kluwer Academic Publishers, 1996. ISBN  0-7923-9650-2 .
  • G. Bolch, S. Greiner, H. de Meer i KS Trivedi, Sieci kolejkowania i łańcuchy Markowa , John Wiley, wydanie 2, 2006. ISBN  978-0-7923-9650-5 .

Zewnętrzne linki