Was sind Markov-Ketten?

9

Ich lese gerade einige Artikel über Markov-Kettenklumpen und sehe keinen Unterschied zwischen einer Markov-Kette und einem einfach gerichteten gewichteten Graphen.

Zum Beispiel bieten sie im Artikel Optimale Zustandsraum-Klumpenbildung in Markov-Ketten die folgende Definition einer CTMC (zeitkontinuierliche Markov-Kette):

Wir betrachten eine endliche CTMC mit dem Zustandsraum durch eine Übergangsratenmatrix .S = { x 1 , x 2 , ... , x n } Q : S × SR +(S,Q)S={x1,x2,,xn}Q:S×SR+

Sie erwähnen die Markov-Eigenschaft überhaupt nicht, und tatsächlich, wenn das Gewicht an den Kanten eine Wahrscheinlichkeit darstellt, glaube ich, dass die Markov-Eigenschaft trivial gilt, da die Wahrscheinlichkeit nur vom aktuellen Zustand der Kette und nicht vom Pfad abhängt, der führt dazu.

In einem anderen Artikel über relationale Eigenschaften der Klumpbarkeit werden Markov-Ketten ähnlich definiert:

Eine Markov-Kette wird als Triplett wobei die endliche Menge von Zuständen von , die Übergangswahrscheinlichkeitsmatrix ist, die die Wahrscheinlichkeit angibt, von einem Zustand in einen anderen zu gelangen, und ist anfängliche Wahrscheinlichkeitsverteilung, die die Wahrscheinlichkeit darstellt, mit der das System in einem bestimmten Zustand startet.( S , P , π ) S M P πM(S,P,π)SMPπ

Wieder keine Erwähnung von Vergangenheit oder Zukunft oder Unabhängigkeit.

Es gibt ein drittes Papier Simple O (m logn) Time Markov Chain Lumping, in dem nicht nur nie angegeben wird, dass die Gewichte an den Kanten Wahrscheinlichkeiten sind, sondern sogar:

In vielen Anwendungen sind die Werte nicht negativ. Wir gehen jedoch nicht davon aus, da es auch Anwendungen gibt, bei denen absichtlich als , was es normalerweise negativ macht.W ( s , s ) - W ( s , S { s } )W(s,s)W(s,s)W(s,S{s})

Darüber hinaus wird angegeben, dass das Zusammenfassen eine Möglichkeit sein sollte, die Anzahl der Zustände zu verringern, während die Markov-Eigenschaft beibehalten wird (indem der "äquivalente" Zustand zu einem größeren Zustand zusammengefasst wird). Für mich sieht es jedoch so aus, als würde es einfach Wahrscheinlichkeiten summieren und es sollte nicht einmal garantieren, dass die resultierenden Peobabilitäten der Übergänge zu / von den aggregierten Zuständen im Bereich . Was bewahrt der Klumpen dann tatsächlich?[0,1]

Ich sehe also zwei Möglichkeiten:

  • Ich habe nicht verstanden, was eine Markov-Kette ist, oder
  • Die Verwendung des Begriffs Markov-Kette in diesen Papieren ist falsch

Könnte jemand die Situation klären?

Es sieht wirklich so aus, als ob es verschiedene Gemeinschaften gibt, die diesen Begriff verwenden, und sie bedeuten sehr unterschiedliche Dinge. Aus diesen 3 Artikeln, von denen ich denke, dass sie so aussehen, als ob die Markov-Eigenschaft entweder trivial oder nutzlos ist, sieht sie bei Betrachtung einer anderen Art von Papieren grundlegend aus.

Bakuriu
quelle
Es gibt Unmengen von Lehrbüchern und Ressourcen im Internet, die erklären, (a) was eine Markov-Kette ist und (b) was die genaue mathematische Definition ist. Wir erwarten von Ihnen, dass Sie eine beträchtliche Menge an Forschung und Selbststudium betreiben, bevor Sie fragen. Haben Sie eine dieser Ressourcen konsultiert? Was hast du dort gefunden? PS Ich würde vermuten, dass Artikel in der Literatur davon ausgehen würden, dass Sie die Definition einer Markov-Kette kennen, und diese Sätze wären nicht unbedingt als genaue formale Definition einer Markov-Kette gedacht, sondern lediglich, um die Notation festzulegen, die sie beim Sprechen verwenden über einen.
DW
Vergangenheit oder Zukunft oder Unabhängigkeit sind Eigenschaften, die folgen, iirc. Es sollte jedoch einige Einschränkungen hinsichtlich des Gewichts geben; Vielleicht können einige Dinge implizit bleiben, z. B. das Zuweisen eines fehlenden ausgehenden Gewichts zu einer Kante, die zu einem Senkenzustand führt (vgl. verschiedene DFA-Definitionen).
Raphael
4
@ DW Ja, das habe ich getan. Was ich fand, ist, dass der Begriff der Markov-Kette im Lehrbuch nichts mit dem Konzept zu tun zu haben scheint, wie es in solchen Papieren verwendet wird. Genau deshalb frage ich das.
Bakuriu
4
Wieder gibt es eine dritte Möglichkeit. Ich denke, der Fehler, den Sie machen, besteht darin, die Aussage in diesen Papieren als Definition einer Markov-Kette zu interpretieren. Ich würde vermuten, dass dies wahrscheinlich nicht die Absicht dieser Aussagen ist. Ich würde vermuten, dass die Autoren davon ausgehen, dass Sie bereits mit der Definition einer Markov-Kette vertraut sind und nur versuchen, eine Notation zu erstellen (es gibt mehrere Arten von Notationen, die Sie für dasselbe Konzept verwenden können). Schauen Sie sich diesen Standpunkt noch einmal an und prüfen Sie, ob Sie in den Zeitungen etwas finden, das dem widerspricht (wenn Sie etwas finden, fügen Sie es der Frage hinzu).
DW
4
@DW Es scheint, als hätte das OP anständige Nachforschungen angestellt und seine Frage akzeptabel strukturiert. Ja, wir können Google verwenden, um zu lernen. Aber haben Sie bemerkt, wie hochrangig SE-Websites in Google sind? Das liegt daran, dass wir Informationen zu (normalerweise) einzelnen, genau definierten Fragen verdichten. Die Zusammenarbeit unserer Community schafft sehr reichhaltige und wertvolle Inhalte, die oftmals nützlicher sind als die Seiten und Seiten mit Informationen, was zu einem effizienteren Lernen führt.
Bar

Antworten:

10

NN×N

Das erste Papier definiert jedoch eine Notation, die mit einer zeitkontinuierlichen Markov-Kette übereinstimmt , die manchmal als Markov-Prozess bezeichnet wird , während das zweite Papier eine Notation definiert, die mit einer zeitdiskreten Markov-Kette übereinstimmt . Man sagt

Pπ

[0,1]P1π1

Ich kann die dritte Zeitung nicht lesen, sie ist kostenpflichtig. Wenn die Einträge in jeder Spalte der Matrix zu 1 summiert werden müssen, handelt es sich um Wahrscheinlichkeiten, und es handelt sich um zeitdiskrete Markov-Ketten. Wenn die Einträge in jeder Spalte eine beliebige Zahl ergeben können, stellen die Einträge Raten und keine Wahrscheinlichkeiten dar und es handelt sich um zeitkontinuierliche Markov-Ketten.

1

Sowohl bei zeitkontinuierlichen als auch bei zeitdiskreten Markov-Ketten wird die Markov-Eigenschaft durch die konstanten Kantengewichte (oder äquivalent die konstanten Einträge in der Übergangsmatrix) impliziert.

Wanderlogik
quelle
8

Markov-Ketten gibt es in zwei Varianten: kontinuierliche Zeit und diskrete Zeit.

Sowohl kontinuierliche Zeitmarkovketten (CTMC) als auch diskrete Zeitmarkovketten (DTMC) werden als gerichtete gewichtete Graphen dargestellt.

Bei DTMCs dauern die Übergänge immer eine Einheit "Zeit". Infolgedessen gibt es keine Wahl, wie hoch Ihr Gewicht auf einem Bogen sein soll - Sie setzen die Wahrscheinlichkeit, auf "j" zu gehen, vorausgesetzt, Sie befinden sich bei "i".

Für CTMCs ist die Übergangszeit zwischen zwei beliebigen Zuständen notwendigerweise durch eine exponentielle Zufallsvariable gegeben. Dies ist der Hauptunterschied zwischen CTMCs und DTMCs: DTMCs haben immer eine Einheitsübergangszeit. CTMCs haben eine zufällige Übergangszeit.

Für eine CTMC besteht die Konvention im Allgemeinen darin, einen Bogen entsprechend der Rate der exponentiellen Zufallsvariablen zu gewichten, die von der Quelle zum Ziel geht. Das heißt, die Konvention besteht darin, Raten auf die Bögen zu setzen, nicht auf Wahrscheinlichkeiten.

Negative Preise

Obwohl alle CTMCs, an die ich mich erinnere, mit positiven Raten an den Rändern dargestellt wurden, treten in der CTMC-Analyse negative Raten auf.

Angenommen, wir stehen im Zustand A, der wie unten mit B, C und D verbunden ist.

A -> B (die Rate in A von B ist negativ) A -> C (die Rate in A von C ist negativ) D -> A (die Rate in A von D ist positiv)

Dies ist wahrscheinlich nicht ganz das, worauf sich Ihr Artikel bezieht. Ich spreche es an, um zu zeigen, dass negative Gewichte nicht unbedingt lächerlich sind, wenn jemand mit einer geeigneten Konvention arbeitet.

Markov Eigentum

Für DTMCs haben Sie Recht. Die Markov-Eigenschaft ist trivial erfüllt. Für CTMCs ist die Markov-Eigenschaft erfüllt, da die Übergänge durch exponentielle Zufallsvariablen (die "memoryless" sind) gegeben sind. Wenn die Übergänge nicht durch exponentielle Zufallsvariablen gegeben wären (sagen wir stattdessen, sie wären einheitlich), dann würden wir über "Semi-Markov-Ketten" oder "Semi-Markov-Prozesse" sprechen.

Riley
quelle
W(s,s)W(s,S{s})s
W(s,s)=W(s,S{s})