Was sind Markov-Ketten?

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 × S → R$(\mathcal{S}, Q)$$\mathcal{S} = \{x_1, x_2, \ldots, x_n\}$$Q: \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$

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, \pi)$$S$$M$$P$$\pi$

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

$N$$N \times 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$$\pi$

$[0,1]$$P$$1$$\pi$$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.

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.