Jakie są łańcuchy Markowa?

9

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 .(S,Q)S={x1,x2,,xn}Q:S×SR+

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,π)SMPπ

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{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.

Bakuriu
źródło
Istnieje mnóstwo podręczników i zasobów w Internecie, które wyjaśniają (a) co to jest łańcuch Markowa i (b) jaka jest dokładna definicja matematyczna. Oczekujemy, że wykonasz znaczną ilość badań i samokształcenia przed zapytaniem. Czy skonsultowałeś się z którymś z tych zasobów? Co tam znalazłeś PS Domyślam się, że artykuły w literaturze zakładałyby, że znasz definicję łańcucha Markowa, a zdania te niekoniecznie miałyby być dokładną formalną definicją łańcucha Markowa, a raczej jedynie w celu ustalenia zapisu, którego używają podczas rozmowy o jednym.
DW
Przeszłość, przyszłość lub niezależność to nieruchomości, które następują, iirc. Należy jednak wprowadzić pewne ograniczenia dotyczące wagi; być może pewne rzeczy mogą pozostać niejawne, np. przypisując brakującą wagę wychodzącą krawędzi, która prowadzi do stanu zatapiania (por. różne definicje DFA).
Raphael
4
@DW Tak zrobiłem. Odkryłem, że pojęcie łańcucha Markowa w podręczniku wydaje się nie mieć nic wspólnego z jego koncepcją stosowaną w takich artykułach. Właśnie o to pytam.
Bakuriu
4
Znowu istnieje trzecia możliwość. Myślę, że błędem, który popełniacie, jest interpretacja wypowiedzi w tych dokumentach jako definicji łańcucha Markowa. Sądzę, że prawdopodobnie nie o to chodzi w tych stwierdzeniach. Wydaje mi się, że autorzy zakładają, że znasz już definicję łańcucha Markowa i próbują jedynie ustalić notację (istnieje wiele rodzajów notacji, których możesz użyć dla tej samej koncepcji). Więc spójrz jeszcze raz z tego punktu widzenia i sprawdź, czy znajdziesz coś, co temu zaprzecza w gazetach (jeśli znajdziesz, dodaj to do pytania).
DW
4
@DW Wygląda na to, że PO przeprowadził przyzwoite badania i ustrukturyzował swoje pytanie w sposób akceptowalny. Tak, możemy używać Google do nauki. Ale czy zauważyłeś, jak wysoko oceniane witryny SE znajdują się w Google? Jest tak, ponieważ łączymy informacje w (zwykle) pojedyncze, dobrze zdefiniowane pytania. Wspólne wysiłki naszej społeczności tworzą bardzo bogate i cenne treści, które są wielokrotnie bardziej przydatne niż strony i strony z informacjami tam, co skutkuje bardziej efektywnym uczeniem się.
BAR

Odpowiedzi:

10

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×Nmatryca. 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ą

Pjest macierzą prawdopodobieństwa przejścia wskazującą prawdopodobieństwo przejścia z jednego stanu do drugiego, orazπ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 1i że suma wpisów w π 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 wymagana1.

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).

Wędrująca logika
źródło
8

Ł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”.

Riley
źródło
Dzięki za wyjaśnienie, że wykładniczy brak pamięci. To ma sens. Dokładnie sprawdziłem trzeci artykuł, a oni wyraźnie stwierdzili, że nie zakładają, że wagi są nieujemne, ponieważ istnieje osobliwa definicjaW(s,s) (współczynnik stanu w siebie), który zwykle jest definiowany jako W(s,S{s}) (tj. minus suma stawek w wysokości sdla wszystkich innych stanów), co sprawia, że ​​prawie zawsze jest negatywna.
Bakuriu
Ostatni artykuł jest dla mnie dość tajemniczy, ponieważ nie używają terminologii łańcucha Markowa w większości artykułów. Możliwe, że rozwiązują bardziej ogólny problem, chociaż motywacją są łańcuchy Markowa. To mówi,W(s,s)=W(s,S{s})jest spójny z pracą z operatorem Laplace'a (a raczej jego negacją ... z jakiegoś powodu).
Sasho Nikolov