Jakie są łańcuchy Markowa?

Obecnie czytam kilka artykułów na temat wypychania łańcucha Markowa i nie dostrzegam różnicy między łańcuchem Markowa a zwykłym, ważonym wykresem.

Na przykład w artykule Optymalne zbieranie przestrzeni stanu w łańcuchach Markowa podają następującą definicję CTMC (ciągły łańcuch Markowa w czasie):

Rozważamy skończony CTMC z przestrzenią stanów według macierzy szybkości przejścia .$(\mathcal{S}, Q)$$\mathcal{S} = \{x_1, x_2, \ldots, x_n\}$$Q: \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$

W ogóle nie wspominają o własności Markowa, a jeśli ciężar na krawędziach reprezentuje prawdopodobieństwo, to uważam, że właściwość Markowa trywialnie utrzymuje się, ponieważ prawdopodobieństwo zależy tylko od bieżącego stanu łańcucha, a nie od ścieżki, która prowadzi do tego.

W innym artykule o relacyjnych właściwościach bryłowości łańcuchy Markowa są zdefiniowane podobnie:

Łańcuch Markowa będzie reprezentowany jako tryplet gdzie jest skończonym zbiorem stanów , macierzą prawdopodobieństwa przejścia wskazującą prawdopodobieństwo przejścia z jednego stanu do drugiego, a jest początkowy rozkład prawdopodobieństwa reprezentujący prawdopodobieństwo uruchomienia systemu w określonym stanie.$M$$(S, P, \pi)$$S$$M$$P$$\pi$

Znowu nie ma wzmianki o przeszłości, przyszłości ani niezależności.

Jest trzeci artykuł Proste O (m logn) Czasowe łańcuchowe zbicie Markowa, w którym nie tylko nigdy nie stwierdzają, że ciężary na krawędziach są prawdopodobieństwami, ale nawet mówią:

W wielu zastosowaniach wartości są nieujemne. Nie przyjmujemy tego założenia, ponieważ istnieją również aplikacje, w których jest celowo wybierane jako , co zwykle powoduje, że jest ono ujemne.$W(s, s')$$W(s, s)$$-W(s, S \setminus \{s\})$

Ponadto stwierdzono, że zbijanie powinno być sposobem na zmniejszenie liczby stanów przy jednoczesnym zachowaniu własności Markowa (poprzez agregację stanu „równoważnego” w stan większy). Jednak dla mnie wygląda na to, że po prostu sumuje prawdopodobieństwa i nie powinno nawet gwarantować, że wynikowe możliwości przejścia do / ze stanów zagregowanych mieszczą się w zakresie . Co zatem właściwie utrzymuje bryła?$[0,1]$

Widzę więc dwie możliwości:

• Nie zrozumiałem, co to jest łańcuch Markowa, lub
• Użycie terminu „łańcuch Markowa” w tych dokumentach jest fałszywe

Czy ktoś może wyjaśnić sytuację?

Wygląda na to, że istnieją różne społeczności używające tego terminu i oznaczają one bardzo różne rzeczy. Z tych 3 artykułów, które uważam, że wygląda na to, że własność Markowa jest albo trywialna, albo bezużyteczna, a patrząc na inny rodzaj dokumentów, wygląda na fundamentalny.

Ciągłej czas Markowa Łańcuch może być przedstawiony w postaci skierowanego wykresie stałych nieujemne wag krawędzi. Równoważna reprezentacja stałych wag krawędzi ukierunkowanego wykresu za pomocą$N$ węzły są jak $N \times N$matryca. Właściwość Markowa (że przyszłe stany zależą tylko od bieżącego stanu) jest implikowana w stałych wagach krawędzi (lub stałych wpisach w macierzy). Domniemane środki implikowane przez . Matematycy używają go jako eufemizmu oznaczającego: „powinieneś sam to udowodnić”.

Ale pierwszy artykuł definiuje notację zgodną z ciągiem Markowa w czasie ciągłym , czasami nazywanym procesem Markowa , podczas gdy drugi artykuł definiuje notację zgodną z łańcuchem Markova w czasie dyskretnym . Mówią

$P$jest macierzą prawdopodobieństwa przejścia wskazującą prawdopodobieństwo przejścia z jednego stanu do drugiego, oraz$\pi$to początkowy rozkład prawdopodobieństwa reprezentujący prawdopodobieństwo uruchomienia systemu w określonym stanie. [podkreślenie dodane]

Zakładają, że macierz jest stała w czasie (co implikuje właściwość Markowa). Domniemany termin „ prawdopodobieństwo” polega na tym, że każda stała jest w zakresie$[0,1]$, że wpisy w każdej kolumnie $P$ suma do $1$i że suma wpisów w $\pi$ suma do $1$.

Nie mogę przeczytać trzeciego artykułu, jest on zaporowy. Jeśli wpisy w każdej kolumnie macierzy mają sumować się do 1, są to prawdopodobieństwa i mówią o łańcuchach Markowa w czasie dyskretnym. Jeśli wpisy w każdej kolumnie mogą być sumowane na dowolną liczbę, to wpisy reprezentują stawki, a nie prawdopodobieństwa i mówią o ciągłych łańcuchach Markowa.

Łańcuchy Markowa w czasie ciągłym to nie to samo, co łańcuchy Markowa w czasie dyskretnym . W ciągłym łańcuchu Markowa wagi krawędzi nie reprezentują prawdopodobieństw, ale raczej wskaźniki przejściowe . Wagi krawędzi muszą być nieujemne, ale mogą być dowolnie duże, a wagi krawędzi zewnętrznych mogą sumować się do dowolnej liczby nieujemnej. Suma nie jest wymagana$1$.

Zarówno w przypadku łańcuchów Markowa w czasie ciągłym, jak i dyskretnym, właściwość Markowa jest implikowana przez stałe wagi krawędzi (lub równoważnie stałe wpisy w macierzy przejścia).

Łańcuchy Markowa występują w dwóch wariantach: ciągłym i dyskretnym.

Zarówno ciągłe łańcuchy czasowe markowa (CTMC), jak i dyskretne łańcuchy czasowe markowa (DTMC) są reprezentowane jako ukierunkowane wykresy ważone.

W przypadku DTMC przejścia zawsze zajmują jedną jednostkę „czasu”. W rezultacie nie ma wyboru, jaka powinna być twoja waga na łuku - stawiasz prawdopodobieństwo przejścia na „j”, biorąc pod uwagę, że jesteś na „i”.

W przypadku CTMC czas przejścia między dowolnymi dwoma stanami jest koniecznie podany przez wykładniczą zmienną losową. Jest to kluczowa różnica między CTMC i DTMC: DTMC zawsze mają czas przejścia jednostki. CTMC mają losowy czas przejścia.

W przypadku CTMC konwencja polega zazwyczaj na umieszczaniu ciężarów na łuku zgodnie z częstością wykładniczej zmiennej losowej przechodzącej od źródła do miejsca docelowego. To jest - konwencja polega na nakładaniu stóp na łuki, a nie prawdopodobieństw.

Stawki ujemne

Chociaż wszystkie CTMC, które pamiętam, były reprezentowane z dodatnimi wskaźnikami na krawędziach, ujemne wskaźniki pojawiają się w analizie CTMC.

Powiedzmy, że stoimy w stanie A, który jest podłączony do B, C i D, jak poniżej.

A -> B (współczynnik do A z B jest ujemny) A -> C (wskaźnik do A z C jest ujemny) D -> A (wskaźnik do A z D jest dodatni)

Prawdopodobnie nie jest to do czego odnosi się twój artykuł; Podnoszę to, aby pokazać, że ujemne ciężary niekoniecznie są śmieszne, jeśli ktoś pracował z odpowiednią konwencją.

Nieruchomość Markowa

Dla DTMC masz rację. Właściwość markov jest spełniona w sposób trywialny. W przypadku CTMC właściwość markov jest spełniona, ponieważ przejścia są przekazywane przez wykładnicze zmienne losowe (które są „bez pamięci”). Jeśli przejścia nie zostałyby podane przez wykładnicze zmienne losowe (powiedzmy, że były one jednolite), wówczas mówilibyśmy o „łańcuchach półmarkowskich” lub „procesach półmarkowskich”.