Markov-Kette - Markov chain

Ein Diagramm, das einen Markov-Prozess mit zwei Zuständen darstellt, wobei die Zustände mit E und A bezeichnet sind. Jede Zahl stellt die Wahrscheinlichkeit dar, dass der Markov-Prozess von einem Zustand in einen anderen Zustand wechselt, wobei die Richtung durch den Pfeil angezeigt wird. Wenn sich der Markov-Prozess beispielsweise im Zustand A befindet, beträgt die Wahrscheinlichkeit, dass er in den Zustand E wechselt, 0,4, während die Wahrscheinlichkeit, dass er im Zustand A bleibt, 0,6 beträgt.

Eine Markov-Kette oder ein Markov-Prozess ist ein stochastisches Modell , das eine Abfolge möglicher Ereignisse beschreibt, bei denen die Wahrscheinlichkeit jedes Ereignisses nur von dem Zustand abhängt, der im vorherigen Ereignis erreicht wurde. Eine abzählbar unendliche Folge, in der sich die Kette in diskreten Zeitschritten bewegt, ergibt eine zeitdiskrete Markov-Kette (DTMC). Ein zeitkontinuierlicher Prozess wird als zeitkontinuierliche Markov-Kette (CTMC) bezeichnet. Es ist nach dem russischen Mathematiker Andrey Markov benannt .

Markov-Ketten haben viele Anwendungen als statistische Modelle von realen Prozessen, wie zum Beispiel das Studium von Geschwindigkeitsregelsystemen in Kraftfahrzeugen , Warteschlangen oder Schlangen von Kunden, die an einem Flughafen ankommen, Wechselkursen und Tierpopulationsdynamiken.

Markov-Prozesse sind die Grundlage für allgemeine stochastische Simulationsmethoden, die als Markov-Kette Monte Carlo bekannt sind und zur Simulation von Stichproben aus komplexen Wahrscheinlichkeitsverteilungen verwendet werden und in Bayes'scher Statistik , Thermodynamik , statistischer Mechanik , Physik , Chemie , Wirtschaft , Finanzen , Signalen Anwendung gefunden haben Verarbeitung , Informationstheorie und Sprachverarbeitung .

Die Adjektive Markovian und Markov werden verwendet, um etwas zu beschreiben, das mit einem Markov-Prozess zusammenhängt.

Einführung

russischer Mathematiker Andrey Markov

Definition

Ein Markov-Prozess ist ein stochastischer Prozess , der die Markov-Eigenschaft erfüllt (manchmal auch als „ Gedächtnislosigkeit “ bezeichnet). Einfacher ausgedrückt handelt es sich um einen Prozess, bei dem Vorhersagen über zukünftige Ergebnisse allein auf der Grundlage seines gegenwärtigen Zustands gemacht werden können, und – was am wichtigsten ist – solche Vorhersagen sind genauso gut wie solche, die mit Kenntnis der vollständigen Historie des Prozesses gemacht werden könnten. Mit anderen Worten, abhängig vom gegenwärtigen Zustand des Systems sind sein zukünftiger und vergangener Zustand unabhängig .

Eine Markov-Kette ist eine Art von Markov-Prozess, der entweder einen diskreten Zustandsraum oder eine diskrete Indexmenge (die oft die Zeit repräsentiert) hat, aber die genaue Definition einer Markov-Kette variiert. Es ist beispielsweise üblich, eine Markov-Kette als Markov-Prozess in diskreter oder kontinuierlicher Zeit mit einem abzählbaren Zustandsraum zu definieren (also unabhängig von der Natur der Zeit), aber es ist auch üblich, eine Markov-Kette als zeitdiskret zu definieren im abzählbaren oder stetigen Zustandsraum (also unabhängig vom Zustandsraum).

Arten von Markov-Ketten

Der Zustandsraum und der Zeitparameterindex des Systems müssen angegeben werden. Die folgende Tabelle gibt einen Überblick über die verschiedenen Instanzen von Markov-Prozessen für verschiedene Ebenen der Zustandsraum-Allgemeinheit und für diskrete Zeit vs. kontinuierliche Zeit:

Abzählbarer Zustandsraum Stetiger oder allgemeiner Zustandsraum
Diskrete Zeit (zeitdiskrete) Markov-Kette auf einem abzählbaren oder endlichen Zustandsraum Markov-Kette auf einem messbaren Zustandsraum (z. B. Harris-Kette )
Kontinuierliche Zeit Zeitkontinuierlicher Markov-Prozess oder Markov-Sprungprozess Jeder kontinuierliche stochastische Prozess mit der Markov-Eigenschaft (z. B. der Wiener-Prozess )

Beachten Sie, dass es in der Literatur keine endgültige Übereinstimmung über die Verwendung einiger der Begriffe gibt, die spezielle Fälle von Markov-Prozessen bezeichnen. In der Regel der Begriff „Markov - Kette“ für einen Prozess mit einer bestimmten Reihe von Zeiten reserviert, das heißt, ein Diskretzeit - Markov - Kette (DTMC) , aber einige Autoren verwenden den Begriff „Markov - Prozess“ beziehen sich auf eine zeitkontinuierliche Markov-Kette (CTMC) ohne ausdrückliche Erwähnung. Darüber hinaus gibt es weitere Erweiterungen von Markov-Prozessen, die als solche bezeichnet werden, aber nicht unbedingt in eine dieser vier Kategorien fallen (siehe Markov-Modell ). Außerdem muss der Zeitindex nicht unbedingt reellwertig sein; wie beim Zustandsraum sind Prozesse denkbar, die sich mit anderen mathematischen Konstrukten durch Indexmengen bewegen. Beachten Sie, dass die zeitkontinuierliche Markov-Kette im allgemeinen Zustandsraum so allgemein ist, dass sie keinen bestimmten Term hat.

Während der Zeitparameter normalerweise diskret ist, hat der Zustandsraum einer Markov-Kette keine allgemein vereinbarten Einschränkungen: Der Begriff kann sich auf einen Prozess auf einem beliebigen Zustandsraum beziehen. Viele Anwendungen von Markov-Ketten verwenden jedoch endliche oder abzählbar unendliche Zustandsräume, die eine einfachere statistische Analyse haben. Neben Zeitindex- und Zustandsraumparametern gibt es viele andere Variationen, Erweiterungen und Verallgemeinerungen (siehe Variationen ). Der Einfachheit halber konzentriert sich der größte Teil dieses Artikels auf den Fall der diskreten Zeit und des diskreten Zustandsraums, sofern nicht anders angegeben.

Übergänge

Die Zustandsänderungen des Systems werden Transitionen genannt. Die mit verschiedenen Zustandsänderungen verbundenen Wahrscheinlichkeiten werden Übergangswahrscheinlichkeiten genannt. Der Prozess ist gekennzeichnet durch einen Zustandsraum, eine Übergangsmatrix, die die Wahrscheinlichkeiten bestimmter Übergänge beschreibt, und einen Anfangszustand (oder eine Anfangsverteilung) über den Zustandsraum. Konventionell gehen wir davon aus, dass alle möglichen Zustände und Übergänge in die Definition des Prozesses aufgenommen wurden, sodass es immer einen nächsten Zustand gibt und der Prozess nicht beendet wird.

Ein zeitdiskreter Zufallsprozess umfasst ein System, das sich bei jedem Schritt in einem bestimmten Zustand befindet, wobei sich der Zustand zwischen den Schritten zufällig ändert. Die Schritte werden oft als zeitliche Momente betrachtet, sie können sich aber ebenso gut auf die physikalische Distanz oder jede andere diskrete Messung beziehen. Formal sind die Schritte die ganzen Zahlen oder natürlichen Zahlen , und der Zufallsprozess ist eine Abbildung dieser auf Zustände. Die Markov-Eigenschaft besagt, dass die bedingte Wahrscheinlichkeitsverteilung für das System beim nächsten Schritt (und tatsächlich bei allen zukünftigen Schritten) nur vom aktuellen Zustand des Systems abhängt und nicht zusätzlich vom Zustand des Systems in den vorherigen Schritten.

Da sich das System zufällig ändert, ist es im Allgemeinen unmöglich, den Zustand einer Markov-Kette zu einem bestimmten Zeitpunkt in der Zukunft mit Sicherheit vorherzusagen. Die statistischen Eigenschaften der Zukunft des Systems können jedoch vorhergesagt werden. In vielen Anwendungen sind es diese statistischen Eigenschaften, die wichtig sind.

Geschichte

Markov beschäftigte sich Anfang des 20. Jahrhunderts mit Markov-Prozessen und veröffentlichte 1906 seine erste Arbeit zu diesem Thema. Markov-Prozesse in kontinuierlicher Zeit wurden lange vor Andrey Markovs Arbeit im frühen 20. Jahrhundert in Form des Poisson-Prozesses entdeckt . Markov war daran interessiert, eine Erweiterung unabhängiger Zufallsfolgen zu untersuchen, motiviert durch eine Meinungsverschiedenheit mit Pavel Nekrasov, der behauptete, Unabhängigkeit sei notwendig, damit das schwache Gesetz der großen Zahlen gelten kann. In seiner ersten Arbeit über Markov-Ketten, die 1906 veröffentlicht wurde, zeigte Markov, dass die durchschnittlichen Ergebnisse der Markov-Kette unter bestimmten Bedingungen gegen einen festen Wertevektor konvergieren, was ein schwaches Gesetz der großen Zahlen ohne die Unabhängigkeitsannahme bewies, die allgemein als Voraussetzung für die Geltung solcher mathematischen Gesetze angesehen. Markov verwendete später Markov-Ketten, um die Verteilung von Vokalen in Eugen Onegin , geschrieben von Alexander Puschkin , zu studieren , und bewies einen zentralen Grenzwertsatz für solche Ketten.

1912 untersuchte Henri Poincaré Markov-Ketten auf endlichen Gruppen mit dem Ziel, das Kartenmischen zu untersuchen. Andere frühe Anwendungen von Markov-Ketten sind ein Diffusionsmodell, das 1907 von Paul und Tatyana Ehrenfest eingeführt wurde, und ein Verzweigungsprozess, der 1873 von Francis Galton und Henry William Watson eingeführt wurde und der Arbeit von Markov vorausging. Nach der Arbeit von Galton und Watson wurde später enthüllt, dass ihr Verzweigungsprozess etwa drei Jahrzehnte zuvor von Irénée-Jules Bienaymé unabhängig entdeckt und untersucht worden war . Ab 1928 interessierte sich Maurice Fréchet für Markov-Ketten, was schließlich dazu führte, dass er 1938 eine detaillierte Studie über Markov-Ketten veröffentlichte.

Andrei Kolmogorov entwickelte in einer Arbeit von 1931 einen großen Teil der frühen Theorie der zeitkontinuierlichen Markov-Prozesse. Kolmogorov wurde teilweise von Louis Bacheliers Arbeit über die Schwankungen des Aktienmarktes aus dem Jahr 1900 sowie von Norbert Wieners Arbeit über Einsteins Modell der Brownschen Bewegung inspiriert. Er führte und untersuchte eine bestimmte Reihe von Markov-Prozessen, die als Diffusionsprozesse bekannt sind, und leitete daraus eine Reihe von Differentialgleichungen ab, die die Prozesse beschreiben. Unabhängig von Kolmogorovs Arbeit leitete Sydney Chapman in einem Artikel von 1928 eine Gleichung ab, die heute Chapman-Kolmogorov-Gleichung genannt wird , auf eine weniger mathematisch rigorose Weise als Kolmogorov, während er die Brownsche Bewegung studierte. Die Differentialgleichungen heißen jetzt Kolmogorov-Gleichungen oder Kolmogorov-Chapman-Gleichungen. Andere Mathematiker, die maßgeblich zu den Grundlagen der Markov-Prozesse beigetragen haben, sind William Feller , beginnend in den 1930er Jahren, und später Eugene Dynkin , beginnend in den 1950er Jahren.

Beispiele

Random Walks basierend auf ganzen Zahlen und das Ruin- Problem des Spielers sind Beispiele für Markov-Prozesse. Einige Variationen dieser Prozesse wurden Hunderte von Jahren zuvor im Zusammenhang mit unabhängigen Variablen untersucht. Zwei wichtige Beispiele für Markov-Prozesse sind der Wiener-Prozess , auch bekannt als Brownscher Bewegungsprozess , und der Poisson-Prozess , die als die wichtigsten und zentralen stochastischen Prozesse in der Theorie der stochastischen Prozesse gelten. Diese beiden Prozesse sind Markov-Prozesse in kontinuierlicher Zeit, während Random Walks auf den ganzen Zahlen und das Ruin-Problem des Spielers Beispiele für Markov-Prozesse in diskreter Zeit sind.

Eine berühmte Markov-Kette ist der sogenannte "Drunkard's Walk", ein zufälliger Spaziergang auf der Zahlengeraden , bei dem sich die Position bei jedem Schritt mit gleicher Wahrscheinlichkeit um +1 oder -1 ändern kann. Von jeder Position gibt es zwei mögliche Übergänge, zur nächsten oder vorherigen Ganzzahl. Die Übergangswahrscheinlichkeiten hängen nur von der aktuellen Position ab, nicht von der Art und Weise, wie die Position erreicht wurde. Zum Beispiel sind die Übergangswahrscheinlichkeiten von 5 auf 4 und 5 auf 6 beide 0,5 und alle anderen Übergangswahrscheinlichkeiten von 5 sind 0. Diese Wahrscheinlichkeiten sind unabhängig davon, ob das System zuvor in 4 oder 6 war.

Ein weiteres Beispiel sind die Ernährungsgewohnheiten einer Kreatur, die nur Trauben, Käse oder Salat isst und deren Ernährungsgewohnheiten den folgenden Regeln entsprechen:

Markov-Käse-Salat-Trauben.svg
  • Es isst genau einmal am Tag.
  • Hat es heute Käse gegessen, frisst es morgen mit gleicher Wahrscheinlichkeit Salat oder Weintrauben.
  • Wenn es heute Trauben gegessen hat, frisst es morgen Trauben mit Wahrscheinlichkeit 1/10, Käse mit Wahrscheinlichkeit 4/10 und Salat mit Wahrscheinlichkeit 5/10.
  • Wenn es heute Salat gegessen hat, frisst es morgen Trauben mit Wahrscheinlichkeit 4/10 oder Käse mit Wahrscheinlichkeit 6/10. Es wird morgen keinen Salat mehr essen.

Die Essgewohnheiten dieser Kreatur können mit einer Markov-Kette modelliert werden, da ihre Entscheidung morgen allein davon abhängt, was sie heute gefressen hat, und nicht, was sie gestern oder zu irgendeinem anderen Zeitpunkt in der Vergangenheit gefressen hat. Eine statistische Eigenschaft, die berechnet werden könnte, ist der über einen langen Zeitraum erwartete Prozentsatz der Tage, an denen die Kreatur Trauben isst.

Eine Reihe unabhängiger Ereignisse (z. B. eine Reihe von Münzwürfen) erfüllt die formale Definition einer Markov-Kette. Die Theorie wird jedoch normalerweise nur angewendet, wenn die Wahrscheinlichkeitsverteilung des nächsten Schrittes nicht trivial vom aktuellen Zustand abhängt.

Ein Nicht-Markov-Beispiel

Angenommen, es gibt eine Geldbörse mit fünf Vierteln (jeweils im Wert von 25¢), fünf Groschen (jeweils im Wert von 10¢) und fünf Nickels (jeweils im Wert von 5¢) und nacheinander werden Münzen zufällig aus der Geldbörse gezogen und sind auf einen Tisch stellen. Wenn steht auf dem Tisch Münzen den Gesamtwert der nach der n zieht, wobei dann die Sequenz ist nicht ein Markov - Prozeß.

Um zu sehen, warum dies der Fall ist, nehmen Sie an, dass bei den ersten sechs Ziehungen alle fünf Nickel und ein Viertel gezogen werden. Also . Wenn wir nicht nur , sondern auch die früheren Werte kennen, können wir feststellen, welche Münzen gezogen wurden, und wir wissen, dass die nächste Münze kein Nickel sein wird; so können wir das mit Wahrscheinlichkeit 1 feststellen . Aber wenn wir die früheren Werte nicht kennen, dann könnten wir aufgrund des Wertes vermuten, dass wir vier Groschen und zwei Nickel gezogen haben, in diesem Fall wäre es sicherlich möglich, einen weiteren Nickel zu ziehen nächste. Daher werden unsere Vermutungen über unser Wissen über die Werte vor beeinflusst .

Es ist jedoch möglich, dieses Szenario als Markov-Prozess zu modellieren. Anstatt den Gesamtwert der Münzen in der Tabelle darzustellen , könnten wir die Anzahl der verschiedenen Münztypen in der Tabelle darstellen. Zum Beispiel könnte definiert werden, um den Zustand darzustellen, in dem nach 6 einzelnen Ziehungen ein Viertel, null Groschen und fünf Nickel auf dem Tisch liegen. Dieses neue Modell würde durch 216 mögliche Zustände repräsentiert (dh 6x6x6 Zustände, da jeder der drei Münztypen am Ende der 6 Ziehungen null bis fünf Münzen auf dem Tisch haben könnte). Angenommen, die erste Ziehung führt zu state . Die Wahrscheinlichkeit, jetzt zu erreichen, hängt davon ab ; zum Beispiel ist der Zustand nicht möglich. Nach der zweiten Ziehung hängt die dritte Ziehung davon ab, welche Münzen bisher gezogen wurden, aber nicht mehr nur von den Münzen, die für den ersten Staat gezogen wurden (da dem Szenario inzwischen wahrscheinlich wichtige Informationen hinzugefügt wurden). Auf diese Weise hängt die Wahrscheinlichkeit des Staates ausschließlich vom Ergebnis des Staates ab.

Formale Definition

Zeitdiskrete Markov-Kette

Eine zeitdiskrete Markov-Kette ist eine Folge von Zufallsvariablen X 1 , X 2 , X 3 , ... mit der Markov-Eigenschaft , nämlich dass die Wahrscheinlichkeit, in den nächsten Zustand zu gelangen, nur vom aktuellen Zustand abhängt und nicht vom vorherigen Zustände:

wenn beide bedingten Wahrscheinlichkeiten wohldefiniert sind, d. h. wenn

Die möglichen Werte von X i bilden eine abzählbare Menge S , den Zustandsraum der Kette.

Variationen

  • Zeithomogene Markovketten sind Prozesse, bei denen
    für alle n . Die Übergangswahrscheinlichkeit ist unabhängig von n .
  • Stationäre Markov-Ketten sind Prozesse, bei denen
    für alle n und k . Jede stationäre Kette kann durch die Bayes-Regel als zeithomogen bewiesen werden.
    Eine notwendige und hinreichende Bedingung dafür, dass eine zeithomogene Markov-Kette stationär ist, ist, dass die Verteilung von eine stationäre Verteilung der Markov-Kette ist.
  • Eine Markov-Kette mit Gedächtnis (oder eine Markov-Kette der Ordnung m ), wobei m endlich ist, ist ein Prozess, der
    Mit anderen Worten, der zukünftige Zustand hängt von den vergangenen m Zuständen ab. Es ist möglich , eine Kette zu konstruieren , von denen indem als Zustandsraum die ‚klassische‘ Markov - Eigenschaft hat die geordnete m -Tupel von X - Wert, das heißt .

Zeitkontinuierliche Markov-Kette

Eine zeitkontinuierliche Markov-Kette ( X t ) t  0 wird durch einen endlichen oder abzählbaren Zustandsraum S , eine Übergangsratenmatrix Q mit Dimensionen gleich der des Zustandsraums und einer im Zustandsraum definierten Anfangswahrscheinlichkeitsverteilung definiert. Für i  ≠  j sind die Elemente q ij nichtnegativ und beschreiben die Geschwindigkeit der Prozessübergänge vom Zustand i zum Zustand j . Die Elemente q ii werden so gewählt, dass jede Zeile der Übergangsratenmatrix zu null summiert, während die Zeilensummen einer Wahrscheinlichkeitsübergangsmatrix in einer (diskreten) Markov-Kette alle gleich eins sind.

Es gibt drei gleichwertige Definitionen des Prozesses.

Unendliche Definition

Die zeitkontinuierliche Markov-Kette ist charakterisiert durch die Übergangsraten, die zeitlichen Ableitungen der Übergangswahrscheinlichkeiten zwischen den Zuständen i und j.

Sei die Zufallsvariable, die den Zustand des Prozesses zum Zeitpunkt t beschreibt , und nehmen Sie an , dass sich der Prozess zum Zeitpunkt t in einem Zustand i befindet . Dann wissen , ist unabhängig von früheren Werten und als h → 0 für alle j und für alle t ,

,

wo ist das Kronecker-Delta , mit der kleinen-o-Notation . Das kann als Messung angesehen werden, wie schnell der Übergang von i nach j erfolgt.

Sprungkette/Haltezeitdefinition

Definieren Sie eine zeitdiskrete Markov-Kette Y n um den n- ten Sprung des Prozesses zu beschreiben und die Variablen S 1 , S 2 , S 3 , ... um Haltezeiten in jedem der Zustände zu beschreiben, wobei S i der Exponentialverteilung mit Rate . folgt Parameter − q Y i Y i .

Definition der Übergangswahrscheinlichkeit

Für jeden Wert n = 0, 1, 2, 3, ... und bis zu diesem Wert von n indizierte Zeiten : t 0 , t 1 , t 2 , ... und alle zu diesen Zeitpunkten aufgezeichneten Zustände i 0 , i 1 , i 2 , i 3 , ... es gilt das

wobei p ij die Lösung der Vorwärtsgleichung ist (eine Differentialgleichung erster Ordnung )

mit Anfangsbedingung P(0) ist die Identitätsmatrix .

Endlicher Zustandsraum

Wenn der Zustandsraum endlich ist , kann die Übergangswahrscheinlichkeitsverteilung durch eine Matrix dargestellt werden , die Übergangsmatrix genannt wird, mit dem ( i , j )-ten Element von P gleich

Da jede Reihe von P auf eins summiert und alle Elemente nicht negativ sind, ist P eine rechte stochastische Matrix .

Stationäre Verteilungsbeziehung zu Eigenvektoren und Simplizes

Eine stationäre Verteilung π ist ein (Zeilen-)Vektor, dessen Einträge nicht-negativ sind und die Summe 1 ergibt, der durch die Operation der Übergangsmatrix P darauf unverändert bleibt und somit definiert ist durch

Durch den Vergleich dieser Definition mit der eines Eigenvektors sehen wir, dass die beiden Konzepte verwandt sind und dass

ist ein normiertes ( ) Vielfaches eines linken Eigenvektors e der Übergangsmatrix P mit einem Eigenwert von 1. Wenn es mehr als einen Einheitseigenvektor gibt, dann ist auch eine gewichtete Summe der entsprechenden stationären Zustände ein stationärer Zustand. Aber für eine Markov-Kette ist man normalerweise eher an einem stationären Zustand interessiert, der die Grenze der Verteilungsfolge für eine Anfangsverteilung ist.

Die Werte einer stationären Verteilung sind mit dem Zustandsraum von P verbunden und ihre Eigenvektoren behalten ihre relativen Proportionen. Da die Komponenten von π positiv sind und die Einschränkung, dass ihre Summe Eins ist, umgeschrieben werden kann, wie wir sehen, dass das Skalarprodukt von π mit einem Vektor, dessen Komponenten alle 1 sind, Eins ist und dass π auf einem Simplex liegt .

Zeithomogene Markov-Kette mit endlichem Zustandsraum

Wenn die Markov - Kette zeit homogen ist, dann ist die Übergangsmatrix P das gleiche ist nach jedem Schritt, so dass die k kann -Schritt Übergangswahrscheinlichkeit als berechnet wird k -te Leistung der Übergangsmatrix, P k .

Ist die Markov-Kette irreduzibel und aperiodisch, dann gibt es eine eindeutige stationäre Verteilung π . Außerdem konvergiert in diesem Fall P k zu einer Rang-1-Matrix, in der jede Zeile die stationäre Verteilung π ist :

wobei 1 der Spaltenvektor mit allen Einträgen gleich 1 ist. Dies wird durch den Satz von Perron-Frobenius angegeben . Wenn, auf welche Weise auch immer, gefunden wird, dann kann die stationäre Verteilung der fraglichen Markov-Kette für jede Startverteilung leicht bestimmt werden, wie weiter unten erläutert wird.

Für einige stochastische Matrizen P existiert der Grenzwert nicht, während dies bei der stationären Verteilung der Fall ist, wie dieses Beispiel zeigt:

(Dieses Beispiel veranschaulicht eine periodische Markov-Kette.)

Da eine Reihe verschiedener Sonderfälle zu berücksichtigen sind, kann das Auffinden dieser Grenze, falls vorhanden, eine langwierige Aufgabe sein. Es gibt jedoch viele Techniken, die dabei helfen können, diese Grenze zu finden. Sei P eine n × n- Matrix und definiere

Das stimmt immer

Subtrahiert man Q von beiden Seiten und faktorisiert dann

wobei I n die Identitätsmatrix der Größe n ist und 0 n , n die Nullmatrix der Größe n × n ist . Die Multiplikation stochastischer Matrizen ergibt immer eine andere stochastische Matrix, also muss Q eine stochastische Matrix sein (siehe Definition oben). Manchmal reicht es aus, die obige Matrixgleichung und die Tatsache zu verwenden, dass Q eine stochastische Matrix ist, um nach Q aufzulösen . Einschließlich der Tatsache, dass die Summe jeder der Zeilen in P 1 ist, gibt es n+1 Gleichungen zur Bestimmung von n Unbekannten, daher ist es rechnerisch einfacher, wenn man einerseits eine Zeile in Q auswählt und jedes ihrer Elemente durch eins ersetzt , und auf der anderen ersetzt man das entsprechende Element (das in derselben Spalte) im Vektor 0 und multipliziert als nächstes diesen letzteren Vektor mit dem Inversen der transformierten früheren Matrix, um Q zu finden .

Hier ist eine Methode dafür: Definieren Sie zuerst die Funktion f ( A ), um die Matrix A zurückzugeben, wobei die Spalte ganz rechts durch alle Einsen ersetzt wird. Wenn [ f ( PI n )] −1 existiert, dann

Erklären Sie: Die ursprüngliche Matrixgleichung entspricht einem System von n×n linearen Gleichungen in n×n Variablen. Und es gibt n weitere lineare Gleichungen aus der Tatsache, dass Q eine rechte stochastische Matrix ist, deren jede Zeile die Summe 1 ergibt n Variablen. In diesem Beispiel wurden die n Gleichungen aus „Q multipliziert mit der äußersten rechten Spalte von (P-In)“ durch die n stochastischen ersetzt.

Es ist zu beachten, dass, wenn P ein Element P i , i auf seiner Hauptdiagonale hat, das gleich 1 ist und die i- te Zeile oder Spalte ansonsten mit Nullen gefüllt ist, diese Zeile oder Spalte in allen folgenden Fällen unverändert bleibt Kräfte P k . Daher ist die i - te Zeile oder Spalte von Q hat die 1 und die 0en in den gleichen Positionen wie in P .

Konvergenzgeschwindigkeit zur stationären Verteilung

Wie bereits erwähnt, aus der Gleichung des stationäre (oder steady state) -Verteilung (falls vorhanden) π ist eine linke Eigenvektor von Zeilen stochastische Matrix P . Dann unter der Annahme , dass P ist diagonalizable oder äquivalent , dass P hat n linear unabhängiger Eigenvektoren, die Geschwindigkeit der Konvergenz ausgearbeitet ist wie folgt. (Für Nicht-diagonalizable, das heißt, defekte Matrizen , kann man mit der Start Jordan Normalform von P und mit einem bisschen mehr beteiligt Reihe von Argumenten in ähnlicher Weise verfahren.

Sei U die Matrix der Eigenvektoren (jeweils normiert auf eine L2-Norm gleich 1) wobei jede Spalte ein linker Eigenvektor von P ist und sei Σ die Diagonalmatrix der linken Eigenwerte von P , d.h. Σ = diag( λ 1 , & lgr; 2 , & lgr; 3 , ..., λ n ). Dann nach Eigenzerlegung

Die Eigenwerte seien so aufgezählt, dass:

Da P eine stochastische Reihenmatrix ist, ist ihr größter linker Eigenwert 1. Wenn es eine eindeutige stationäre Verteilung gibt, dann sind auch der größte Eigenwert und der zugehörige Eigenvektor eindeutig (weil es kein anderes π gibt , das die obige stationäre Verteilungsgleichung löst). Sei u i die i- te Spalte der U- Matrix, dh u i ist der linke Eigenvektor von P entsprechend i . Sei auch x ein Zeilenvektor der Länge n , der eine gültige Wahrscheinlichkeitsverteilung darstellt; da die Eigenvektoren u ich aufspanne können wir schreiben

Multiplizieren wir x mit P von rechts und setzen diese Operation mit den Ergebnissen fort, erhalten wir am Ende die stationäre Verteilung π . Mit anderen Worten, π = u ixPP ... P = xP k als k → ∞. Das bedeutet

Da π = u 1 , π ( k ) Ansätze & pgr als k → ∞ mit einer Geschwindigkeit in der Größenordnung von λ 2 / λ 1 exponentiell. Dies folgt, weil somit λ 2 / λ 1 der dominante Term ist. Je kleiner das Verhältnis ist, desto schneller ist die Konvergenz. Auch zufälliges Rauschen in der Zustandsverteilung π kann diese Konvergenz zur stationären Verteilung beschleunigen.

Allgemeiner Zustandsraum

Harris-Ketten

Viele Ergebnisse für Markov-Ketten mit endlichem Zustandsraum können durch Harris-Ketten auf Ketten mit überzähligen Zustandsräumen verallgemeinert werden .

Die Verwendung von Markov-Ketten in Markov-Ketten-Monte-Carlo-Verfahren deckt Fälle ab, in denen der Prozess einem kontinuierlichen Zustandsraum folgt.

Lokal interagierende Markov-Ketten

Die Betrachtung einer Sammlung von Markov-Ketten, deren Entwicklung den Zustand anderer Markov-Ketten berücksichtigt, hängt mit dem Begriff der lokal wechselwirkenden Markov-Ketten zusammen . Dies entspricht der Situation, wenn der Zustandsraum eine (kartesische) Produktform hat. Siehe interagierendes Partikelsystem und stochastische zelluläre Automaten (probabilistische zelluläre Automaten). Siehe zum Beispiel Interaktion von Markov-Prozessen oder

Eigenschaften

Zwei Zustände kommunizieren miteinander, wenn beide durch eine Folge von Übergängen mit positiver Wahrscheinlichkeit voneinander erreichbar sind. Dies ist eine Äquivalenzrelation, die eine Menge von kommunizierenden Klassen ergibt. Eine Klasse ist abgeschlossen, wenn die Wahrscheinlichkeit, die Klasse zu verlassen, null ist. Eine Markov-Kette ist irreduzibel, wenn es eine kommunizierende Klasse gibt, den Zustandsraum.

Ein Zustand i hat eine Periode, wenn der größte gemeinsame Teiler der Anzahl von Übergängen ist, durch die i ausgehend von i erreicht werden kann . Das ist:

Ein Zustand i heißt transient, wenn ausgehend von i eine Wahrscheinlichkeit ungleich Null besteht, dass die Kette nie zu i zurückkehrt . Es kommt sonst immer wieder vor. Für einen wiederkehrenden Zustand i ist die mittlere Schlagzeit definiert als:

Zustand i ist positiv rekurrent, wenn er endlich ist, andernfalls null rekurrent. Periodizität, Vergänglichkeit, Rekursion und positive und Null-Rekursion sind Klasseneigenschaften – das heißt, wenn ein Zustand die Eigenschaft hat, dann haben alle Zustände in seiner kommunizierenden Klasse die Eigenschaft.

Ein Zustand i heißt absorbierend, wenn es keine ausgehenden Übergänge vom Zustand gibt.

Ergodizität

Ein Zustand i heißt ergodisch, wenn er aperiodisch und positiv rekurrent ist. Mit anderen Worten, ein Zustand i ist ergodisch, wenn er rekurrent ist, eine Periode von 1 hat und eine endliche mittlere Rezidivzeit hat. Wenn alle Zustände in einer irreduziblen Markov-Kette ergodisch sind, dann heißt die Kette ergodisch.

Es kann gezeigt werden, dass eine irreduzible Markov-Kette in endlichen Zuständen ergodisch ist, wenn sie einen aperiodischen Zustand hat. Allgemeiner gesagt ist eine Markov-Kette ergodisch, wenn es eine Zahl N gibt, so dass jeder Zustand von jedem anderen Zustand in einer beliebigen Anzahl von Schritten kleiner oder gleich einer Zahl N erreicht werden kann . Im Fall einer vollständig zusammenhängenden Übergangsmatrix, bei der alle Übergänge eine Wahrscheinlichkeit ungleich Null haben, ist diese Bedingung mit N  = 1 erfüllt  .

Eine Markov-Kette mit mehr als einem Zustand und nur einem ausgehenden Übergang pro Zustand ist entweder nicht irreduzibel oder nicht aperiodisch, kann also nicht ergodisch sein.

Markovasche Vertretungen

In einigen Fällen können scheinbar nicht-markowsche Prozesse immer noch Markovasche Darstellungen aufweisen, die durch Erweiterung des Konzepts der „aktuellen“ und „zukünftigen“ Zustände konstruiert wurden. Sei beispielsweise X ein nicht-markovscher Prozess. Definieren Sie dann einen Prozess Y , so dass jeder Zustand von Y ein Zeitintervall von Zuständen von X darstellt . Mathematisch hat dies die Form:

Wenn Y die Markov-Eigenschaft besitzt, dann ist es eine Markovasche Darstellung von X .

Ein Beispiel für einen nicht-markovianischen Prozess mit einer Markovaschen Darstellung ist eine autoregressive Zeitreihe der Ordnung größer als eins.

Schlagzeiten

Die Trefferzeit ist die Zeit, beginnend in einem bestimmten Satz von Zuständen, bis die Kette in einem bestimmten Zustand oder einer bestimmten Menge von Zuständen ankommt. Die Verteilung eines solchen Zeitraums weist eine Phasentypverteilung auf. Die einfachste Verteilung ist die eines einzelnen exponentiell verteilten Übergangs.

Voraussichtliche Schlagzeiten

Für eine Teilmenge von Zuständen A  ⊆  S ist der Vektor k A der Trefferzeiten (wobei element den erwarteten Wert darstellt , beginnend in Zustand i, dass die Kette in einen der Zustände in der Menge A eintritt ) die minimale nicht-negative Lösung von

Zeitumkehr

Für einen CTMC X t ist der zeitumgekehrte Prozess definiert als . Nach Kellys Lemma hat dieser Prozess die gleiche stationäre Verteilung wie der Vorwärtsprozess.

Eine Kette heißt reversibel, wenn der umgekehrte Prozess der gleiche ist wie der Vorwärtsprozess. Das Kolmogorov-Kriterium besagt, dass die notwendige und hinreichende Bedingung für die Reversibilität eines Prozesses darin besteht, dass das Produkt der Übergangsgeschwindigkeiten um eine geschlossene Schleife in beiden Richtungen gleich sein muss.

Eingebettete Markov-Kette

Ein Verfahren der Feststellung stationäre Wahrscheinlichkeitsverteilung , π , eine ergodischen zeitkontinuierliche Markov - Kette, Q , ist , indem zuerst seine eingebettete Markov - Kette (EMC) . Streng genommen handelt es sich bei der EMC um eine regelmäßige zeitdiskrete Markov-Kette, die manchmal auch als Sprungprozess bezeichnet wird . Jedes Element des Einstufen-Übergangswahrscheinlichkeitsmatrix des EMC, S , bezeichnet durch s ij und stellt die bedingte Wahrscheinlichkeit von Zustand über i in den Zustand j . Diese bedingten Wahrscheinlichkeiten können gefunden werden durch

Daraus lässt sich S schreiben als

wobei I die Identitätsmatrix und diag( Q ) die Diagonalmatrix ist, die gebildet wird, indem die Hauptdiagonale aus der Matrix Q ausgewählt und alle anderen Elemente auf Null gesetzt werden.

Um den stationären Wahrscheinlichkeitsverteilungsvektor zu finden, müssen wir als nächstes so finden , dass

mit einem Zeilenvektor, sodass alle Elemente in größer als 0 und = 1 sind. Daraus kann π gefunden werden als

( S kann periodisch sein, auch wenn Q nicht ist. Sobald π gefunden ist, muss es auf einen Einheitsvektor normiert werden .)

Ein weiterer zeitdiskreter Prozess, der aus einer zeitkontinuierlichen Markov-Kette abgeleitet werden kann, ist ein δ-Skelett – die (zeitdiskrete) Markov-Kette, die durch Beobachten von X ( t ) in Intervallen von δ Zeiteinheiten gebildet wird. Die Zufallsvariablen X (0),  X (δ),  X (2δ), ... geben die Folge der vom δ-Skelett besuchten Zustände an.

Sondertypen von Markov-Ketten

Markov-Modell

Markov-Modelle werden verwendet, um sich ändernde Systeme zu modellieren. Es gibt 4 Haupttypen von Modellen, die Markov-Ketten verallgemeinern, je nachdem, ob jeder sequentielle Zustand beobachtbar ist oder nicht und ob das System auf der Grundlage der gemachten Beobachtungen angepasst werden soll:

Systemzustand ist vollständig beobachtbar Systemzustand ist teilweise beobachtbar
System ist autonom Markov-Kette Hidden-Markov-Modell
System wird kontrolliert Markov-Entscheidungsprozess Teilweise beobachtbarer Markov-Entscheidungsprozess

Bernoulli-Schema

Ein Bernoulli-Schema ist ein Spezialfall einer Markov-Kette, bei der die Übergangswahrscheinlichkeitsmatrix identische Zeilen hat, was bedeutet, dass der nächste Zustand sogar vom aktuellen Zustand unabhängig ist (zusätzlich zu den vergangenen Zuständen). Ein Bernoulli-Schema mit nur zwei möglichen Zuständen wird als Bernoulli-Prozess bezeichnet .

Beachten Sie jedoch nach dem Ornstein-Isomorphismus-Theorem , dass jede aperiodische und irreduzible Markov-Kette zu einem Bernoulli-Schema isomorph ist; daher könnte man auch behaupten, dass Markov-Ketten ein "Sonderfall" von Bernoulli-Schemata sind. Der Isomorphismus erfordert im Allgemeinen eine komplizierte Umcodierung. Der Isomorphismussatz ist sogar noch etwas stärker: Er besagt, dass jeder stationäre stochastische Prozess isomorph zu einem Bernoulli-Schema ist; die Markov-Kette ist nur ein solches Beispiel.

Teilverschiebung endlichen Typs

Wenn die Markov-Matrix durch die Adjazenzmatrix eines endlichen Graphen ersetzt wird , ist die resultierende Verschiebung eine topologische Markov-Kette oder eine Teilverschiebung endlichen Typs . Eine mit der Adjazenzmatrix kompatible Markov-Matrix kann dann ein Maß für die Unterverschiebung liefern. Viele chaotische dynamische Systeme sind isomorph zu topologischen Markov-Ketten; Beispiele umfassen Diffeomorphismen der geschlossenen Verteiler , der Prouhet-Thue-Morse - System , das Chacon System , Sofic Systeme , kontextfreie Systeme und Blockcode - Systeme .

Anwendungen

Die Forschung hat die Anwendung und Nützlichkeit von Markov-Ketten in einer Vielzahl von Themen wie Physik, Chemie, Biologie, Medizin, Musik, Spieltheorie und Sport berichtet.

Physik

Markovasche Systeme treten häufig in der Thermodynamik und statistischen Mechanik auf , wenn Wahrscheinlichkeiten verwendet werden, um unbekannte oder unmodellierte Details des Systems darzustellen, wenn davon ausgegangen werden kann, dass die Dynamik zeitinvariant ist und keine relevante Geschichte berücksichtigt werden muss, die nicht bereits enthalten ist in der Zustandsbeschreibung. Beispielsweise arbeitet ein thermodynamischer Zustand unter einer Wahrscheinlichkeitsverteilung, die schwer oder teuer zu erlangen ist. Daher kann die Markov-Chain-Monte-Carlo-Methode verwendet werden, um zufällig Stichproben aus einer Blackbox zu ziehen, um die Wahrscheinlichkeitsverteilung von Attributen über eine Reihe von Objekten anzunähern.

Die Pfade sind in der Pfadintegralformulierung der Quantenmechanik Markov-Ketten.

Markov-Ketten werden in Gitter-QCD- Simulationen verwendet.

Chemie

Michaelis-Menten-Kinetik . Das Enzym (E) bindet ein Substrat (S) und produziert ein Produkt (P). Jede Reaktion ist ein Zustandsübergang in einer Markov-Kette.

Ein Reaktionsnetzwerk ist ein chemisches System, das mehrere Reaktionen und chemische Spezies umfasst. Die einfachsten stochastischen Modelle solcher Netzwerke behandeln das System als eine zeitkontinuierliche Markov-Kette, wobei der Zustand die Anzahl der Moleküle jeder Spezies ist und Reaktionen als mögliche Kettenübergänge modelliert werden. Markov-Ketten und zeitkontinuierliche Markov-Prozesse sind in der Chemie nützlich, wenn physikalische Systeme der Markov-Eigenschaft sehr nahe kommen. Stellen Sie sich zum Beispiel eine große Anzahl n Moleküle in Lösung im Zustand A vor, von denen jedes mit einer bestimmten durchschnittlichen Geschwindigkeit eine chemische Reaktion in den Zustand B eingehen kann. Vielleicht ist das Molekül ein Enzym, und die Zustände beziehen sich darauf, wie es gefaltet ist. Der Zustand jedes einzelnen Enzyms folgt einer Markov-Kette, und da die Moleküle im Wesentlichen unabhängig voneinander sind, beträgt die Anzahl der Moleküle im Zustand A oder B gleichzeitig die n- fache Wahrscheinlichkeit, dass sich ein bestimmtes Molekül in diesem Zustand befindet.

Das klassische Modell der Enzymaktivität, die Michaelis-Menten-Kinetik , kann als Markov-Kette angesehen werden, bei der die Reaktion bei jedem Schritt in eine bestimmte Richtung abläuft. Während Michaelis-Menten recht einfach ist, lassen sich mit Markov-Ketten auch weitaus kompliziertere Reaktionsnetzwerke modellieren.

Ein auf einer Markov-Kette basierender Algorithmus wurde auch verwendet, um das fragmentbasierte Wachstum von Chemikalien in silico auf eine gewünschte Substanzklasse wie Medikamente oder Naturstoffe zu fokussieren . Wenn ein Molekül gezüchtet wird, wird ein Fragment aus dem entstehenden Molekül als "aktueller" Zustand ausgewählt. Es ist sich seiner Vergangenheit nicht bewusst (dh es ist sich dessen nicht bewusst, was bereits mit ihm verbunden ist). Es geht dann in den nächsten Zustand über, wenn ein Fragment daran angehängt wird. Die Übergangswahrscheinlichkeiten werden auf Datenbanken authentischer Verbindungsklassen trainiert.

Auch das Wachstum (und die Zusammensetzung) von Copolymeren kann unter Verwendung von Markov-Ketten modelliert werden. Basierend auf den Reaktivitätsverhältnissen der Monomere, aus denen die wachsende Polymerkette besteht, kann die Zusammensetzung der Kette berechnet werden (z. B. ob Monomere dazu neigen, sich abwechselnd oder in langen Reihen des gleichen Monomers hinzuzufügen). Aufgrund sterischer Effekte können auch Markov-Effekte zweiter Ordnung beim Wachstum einiger Polymerketten eine Rolle spielen.

In ähnlicher Weise wurde vorgeschlagen, dass die Kristallisation und das Wachstum einiger epitaktischer Übergitteroxidmaterialien genau durch Markov-Ketten beschrieben werden können.

Biologie

Markovketten werden in verschiedenen Bereichen der Biologie verwendet. Bemerkenswerte Beispiele sind:

Testen

Mehrere Theoretiker haben die Idee des statistischen Markov-Ketten-Tests (MCST) vorgeschlagen, einer Methode, um Markov-Ketten zu einer " Markov-Decke " zu verbinden, diese Ketten in mehreren rekursiven Schichten anzuordnen ("Wafering") und effizientere Testsätze zu erzeugen - Stichproben – als Ersatz für umfassende Tests. MCSTs haben auch Verwendungen in temporalen zustandsbasierten Netzwerken; Das Papier von Chilukuri et al. mit dem Titel "Temporal Uncertainty Reasoning Networks for Evidence Fusion with Applications to Object Detection and Tracking" (ScienceDirect) bietet einen Hintergrund und eine Fallstudie für die Anwendung von MCSTs auf eine breitere Palette von Anwendungen.

Variabilität der Sonneneinstrahlung

Variabilitätsbewertungen der Sonneneinstrahlung sind für Solarstromanwendungen nützlich . Die Variabilität der Sonneneinstrahlung an jedem Ort im Laufe der Zeit ist hauptsächlich eine Folge der deterministischen Variabilität des Sonnenverlaufs über die Himmelskuppel und der Variabilität der Bewölkung. Die Variabilität der zugänglichen Sonnenstrahlung auf der Erdoberfläche wurde unter Verwendung von Markov-Ketten modelliert, einschließlich der Modellierung der beiden Zustände Klar und Bewölkt als Zwei-Zustands-Markov-Kette.

Spracherkennung

Hidden-Markov-Modelle sind die Grundlage für die meisten modernen automatischen Spracherkennungssysteme .

Informationstheorie

Markov-Ketten werden während der gesamten Informationsverarbeitung verwendet. Claude Shannons berühmter Aufsatz A Mathematical Theory of Communication aus dem Jahr 1948 , der in einem einzigen Schritt das Gebiet der Informationstheorie schuf , beginnt mit der Einführung des Konzepts der Entropie durch die Markov-Modellierung der englischen Sprache. Solche idealisierten Modelle können viele der statistischen Gesetzmäßigkeiten von Systemen erfassen. Auch ohne die vollständige Struktur des Systems perfekt zu beschreiben, können solche Signalmodelle eine sehr effektive Datenkompression durch Entropiecodierungstechniken wie etwa arithmetische Codierung ermöglichen . Sie ermöglichen auch eine effektive Zustandsschätzung und Mustererkennung . Auch beim Reinforcement Learning spielen Markovketten eine wichtige Rolle .

Markov-Ketten sind auch die Grundlage für Hidden-Markov-Modelle, die in so unterschiedlichen Bereichen wie Telefonnetzen (die den Viterbi-Algorithmus zur Fehlerkorrektur verwenden), Spracherkennung und Bioinformatik (wie bei der Erkennung von Umordnungen) ein wichtiges Werkzeug sind .

Der verlustfreie LZMA- Datenkomprimierungsalgorithmus kombiniert Markov-Ketten mit Lempel-Ziv-Komprimierung , um sehr hohe Komprimierungsraten zu erzielen.

Warteschlangentheorie

Markov-Ketten sind die Grundlage für die analytische Behandlung von Warteschlangen ( Queuing-Theorie ). Agner Krarup Erlang hat das Thema 1917 initiiert. Dies macht sie entscheidend für die Leistungsoptimierung von Telekommunikationsnetzen, in denen Nachrichten oft um begrenzte Ressourcen (wie Bandbreite) konkurrieren müssen.

Zahlreiche Warteschlangenmodelle verwenden zeitkontinuierliche Markov-Ketten. Zum Beispiel ist eine M/M/1-Warteschlange eine CTMC auf den nicht-negativen ganzen Zahlen, bei der Aufwärtsübergänge von i zu i  + 1 mit einer Rate λ gemäß einem Poisson-Prozess auftreten und Jobankünfte beschreiben, während Übergänge von i zu i  – 1 (für i  > 1) treten mit der Rate μ auf (Job-Service-Zeiten sind exponentiell verteilt) und beschreiben abgeschlossene Services (Abfahrten) aus der Warteschlange.

Internetanwendungen

Ein Zustandsdiagramm, das den PageRank-Algorithmus mit einer Übergangswahrscheinlichkeit von M darstellt, oder .

Der von Google verwendete PageRank einer Webseite wird durch eine Markov-Kette definiert. Es ist die Wahrscheinlichkeit, in der stationären Verteilung auf der folgenden Markov-Kette auf allen (bekannten) Webseiten auf Seite zu sein. Wenn die Zahl der bekannten Web - Seiten ist, und eine Seite hat Links zu ihr dann hat es Übergangswahrscheinlichkeit für alle Seiten, die auf und verknüpft sind , für alle Seiten, die nicht miteinander verbunden sind. Der Parameter wird mit etwa 0,15 angenommen.

Markov-Modelle wurden auch verwendet, um das Webnavigationsverhalten von Benutzern zu analysieren. Der Übergang eines Weblinks eines Benutzers auf einer bestimmten Website kann unter Verwendung von Markov-Modellen erster oder zweiter Ordnung modelliert werden und kann verwendet werden, um Vorhersagen bezüglich der zukünftigen Navigation zu treffen und die Webseite für einen einzelnen Benutzer zu personalisieren.

Statistiken

Markov-Kettenverfahren sind auch sehr wichtig geworden, um Sequenzen von Zufallszahlen zu erzeugen, um sehr komplizierte gewünschte Wahrscheinlichkeitsverteilungen über einen Prozess namens Markov-Kette Monte Carlo (MCMC) genau wiederzugeben. Dies hat in den letzten Jahren die Praktikabilität von Bayes'schen Inferenzverfahren revolutioniert , da eine Vielzahl von Posterior-Verteilungen simuliert und deren Parameter numerisch ermittelt werden können.

Wirtschaft und Finanzen

Markov-Ketten werden in den Finanz- und Wirtschaftswissenschaften verwendet, um eine Vielzahl unterschiedlicher Phänomene zu modellieren, einschließlich der Einkommensverteilung, der Größenverteilung von Unternehmen, Vermögenspreisen und Marktcrashs. Die DG Champernowne erstellte 1953 ein Markov-Kettenmodell der Einkommensverteilung. Herbert A. Simon und Co-Autor Charles Bonini verwendeten ein Markov-Kettenmodell, um eine stationäre Yule-Verteilung der Unternehmensgrößen abzuleiten. Louis Bachelier beobachtete als erster, dass die Aktienkurse einem Random Walk folgten. Der Random Walk wurde später als Beweis für die Efficiency-Market-Hypothese angesehen und Random-Walk-Modelle waren in der Literatur der 1960er Jahre populär. Regime-Switching-Modelle von Konjunkturzyklen wurden von James D. Hamilton (1989) populär gemacht , der eine Markov-Kette verwendete, um den Wechsel zwischen Perioden mit hohem und niedrigem BIP-Wachstum (oder alternativ Wirtschaftsexpansion und Rezession) zu modellieren. Ein neueres Beispiel ist das multifraktale Markov-Switching- Modell von Laurent E. Calvet und Adlai J. Fisher, das auf der Bequemlichkeit früherer Regime-Switching-Modelle aufbaut. Es verwendet eine beliebig große Markov-Kette, um die Volatilität der Vermögensrenditen zu erhöhen.

Die dynamische Makroökonomie macht stark von Markov-Ketten Gebrauch. Ein Beispiel ist die Verwendung von Markov-Ketten zur exogenen Modellierung von Aktienkursen (Aktien) in einem allgemeinen Gleichgewicht .

Ratingagenturen erstellen jährliche Tabellen der Übergangswahrscheinlichkeiten für Anleihen unterschiedlicher Bonität.

Sozialwissenschaften

Markov-Ketten werden im Allgemeinen bei der Beschreibung pfadabhängiger Argumente verwendet, bei denen aktuelle strukturelle Konfigurationen zukünftige Ergebnisse bedingen. Ein Beispiel ist die Neuformulierung der Idee, die ursprünglich auf Karl Marx ' Das Kapital zurückgeht und die wirtschaftliche Entwicklung an den Aufstieg des Kapitalismus knüpft . In der aktuellen Forschung ist es üblich, eine Markov-Kette zu verwenden, um zu modellieren, wie ein Land, sobald ein bestimmtes wirtschaftliches Entwicklungsniveau erreicht ist, die Konfiguration struktureller Faktoren, wie Größe der Mittelschicht , das Verhältnis von Stadt zu Land, die Rate der politischen Mobilisierung usw. wird eine höhere Wahrscheinlichkeit des Übergangs von einem autoritären zu einem demokratischen Regime erzeugen .

Spiele

Mit Markov-Ketten lassen sich viele Glücksspiele modellieren. Die Kinderspiele Snakes and Ladders und „ Hi Ho! Cherry-O “ beispielsweise werden exakt durch Markov-Ketten repräsentiert. In jeder Runde beginnt der Spieler in einem bestimmten Zustand (auf einem bestimmten Feld) und hat von dort aus eine feste Chance, sich in bestimmte andere Zustände (Felder) zu bewegen.

Musik

Markov-Ketten werden in der algorithmischen Musikkomposition verwendet , insbesondere in Software wie Csound , Max und SuperCollider . In einer Kette erster Ordnung werden die Zustände des Systems zu Noten- oder Tonhöhenwerten, und ein Wahrscheinlichkeitsvektor für jede Note wird konstruiert, wodurch eine Übergangswahrscheinlichkeitsmatrix vervollständigt wird (siehe unten). Ein Algorithmus ist konstruiert, um Ausgabenotenwerte basierend auf den Übergangsmatrixgewichtungen zu erzeugen, die MIDI- Notenwerte, Frequenz ( Hz ) oder jede andere gewünschte Metrik sein können.

Matrix 1. Ordnung
Notiz EIN C E
EIN 0,1 0,6 0,3
C 0,25 0,05 0,7
E 0,7 0,3 0
Matrix 2. Ordnung
Anmerkungen EIN D g
AA 0,18 0,6 0,22
ANZEIGE 0,5 0,5 0
AG 0,15 0,75 0,1
DD 0 0 1
DA 0,25 0 0,75
GD 0,9 0,1 0
GG 0,4 0,4 0,2
GA 0,5 0,25 0,25
GD 1 0 0

Eine Markov-Kette zweiter Ordnung kann eingeführt werden, indem der aktuelle Zustand und auch der vorherige Zustand betrachtet werden, wie in der zweiten Tabelle angegeben. Höhere Ketten n- ter Ordnung neigen dazu, bestimmte Noten zu "gruppieren", während sie gelegentlich in andere Muster und Sequenzen "abbrechen". Diese Ketten höherer Ordnung neigen dazu, Ergebnisse mit einem Sinn für eine phrasale Struktur zu erzeugen , anstatt das 'ziellose Wandern', das von einem System erster Ordnung erzeugt wird.

Markov-Ketten können strukturell verwendet werden, wie in Xenakis' Analogique A und B. Markov-Ketten werden auch in Systemen verwendet, die ein Markov-Modell verwenden, um interaktiv auf Musikeingaben zu reagieren.

Normalerweise müssen Musiksysteme spezifische Kontrollbeschränkungen für die von ihnen erzeugten Sequenzen endlicher Länge erzwingen, aber Kontrollbeschränkungen sind nicht mit Markov-Modellen kompatibel, da sie weitreichende Abhängigkeiten induzieren, die die Markov-Hypothese des begrenzten Speichers verletzen. Um diese Einschränkung zu überwinden, wurde ein neuer Ansatz vorgeschlagen.

Baseball

Markov-Kettenmodelle werden seit 1960 in der fortgeschrittenen Baseballanalyse verwendet, obwohl sie noch selten verwendet werden. Jedes halbe Inning eines Baseballspiels entspricht dem Zustand der Markov-Kette, wenn die Anzahl der Runner und Outs berücksichtigt wird. Bei jedem At-Bat gibt es 24 mögliche Kombinationen aus Anzahl der Outs und Position der Runner. Mark Pankin zeigt, dass Markov-Kettenmodelle verwendet werden können, um Läufe zu bewerten, die sowohl für einzelne Spieler als auch für ein Team erstellt wurden. Er bespricht auch verschiedene Arten von Strategien und Spielbedingungen: wie Markov-Kettenmodelle verwendet wurden, um Statistiken für Spielsituationen wie Ammer und Bodendiebstahl und Unterschiede beim Spielen auf Gras vs. AstroTurf zu analysieren .

Markov-Textgeneratoren

Markov-Prozesse können auch verwendet werden, um anhand eines Beispieldokuments oberflächlich echt aussehenden Text zu erzeugen . Markov Prozesse verwendet werden in einer Vielzahl von Freizeit " Parodie - Generator " -Software (siehe dissoziierte drücken , Jeff Harrison, Mark V. Shaney und Academias Neutronium ). Es gibt mehrere Open-Source-Bibliotheken zur Textgenerierung, die Markov-Ketten verwenden, darunter The RiTa Toolkit .

Wahrscheinlichkeitsprognose

Markov-Ketten wurden für Vorhersagen in mehreren Bereichen verwendet: zum Beispiel Preistrends, Windkraft und Sonneneinstrahlung. Die Markov-Chain-Prognosemodelle verwenden eine Vielzahl von Einstellungen, von der Diskretisierung der Zeitreihen über Hidden-Markov-Modelle in Kombination mit Wavelets bis hin zum Markov-Chain-Mischungsverteilungsmodell (MCM).

Siehe auch

Anmerkungen

Verweise

  • AA Markov (1906) "Rasprostranenie zakona bol'shih meißel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazankom universitete , 2-ya seriya, tom 15, S. 135–156.
  • A. A. Markov (1971). „Erweiterung der Grenzwertsätze der Wahrscheinlichkeitstheorie auf eine Summe von in einer Kette verbundenen Variablen“. abgedruckt in Anhang B von: R. Howard. Dynamische Wahrscheinlichkeitssysteme, Band 1: Markov-Ketten . John Wiley und Söhne.
  • Klassischer Text in Übersetzung: Markov, AA (2006). Übersetzt von Link, David. "Ein Beispiel für die statistische Untersuchung des Textes Eugene Onegin bezüglich der Verbindung von Proben in Ketten" . Wissenschaft im Kontext . 19 (4): 591–600. doi : 10.1017/s0269889706001074 . S2CID  144854176 .
  • Leo Breiman (1992) [1968] Wahrscheinlichkeit . Originalausgabe herausgegeben von Addison-Wesley; nachgedruckt von Society for Industrial and Applied Mathematics ISBN  0-89871-296-3 . (Siehe Kapitel 7)
  • JL Doob (1953) Stochastische Prozesse . New York: John Wiley und Söhne ISBN  0-471-52369-0 .
  • SP Meyn und RL Tweedie (1993) Markov-Ketten und stochastische Stabilität . London: Springer-Verlag ISBN  0-387-19832-6 . Online: MCSS . Zweite Ausgabe, Cambridge University Press, 2009.
  • SP Meyn. Steuerungstechniken für komplexe Netzwerke . Cambridge University Press, 2007. ISBN  978-0-521-88441-9 . Anhang enthält gekürzte Meyn & Tweedie. online: [1]
  • Booth, Taylor L. (1967). Sequentielle Maschinen und Automatentheorie (1. Aufl.). New York, NY: John Wiley and Sons, Inc. Bibliothek des Kongresses Kartenkatalognummer 67-25924.] Umfangreiches, breit gefächertes Fachbuch, geschrieben sowohl für theoretische Informatiker als auch für Elektroingenieure. Mit ausführlichen Erläuterungen zu Zustandsminimierungstechniken, FSMs, Turingmaschinen, Markov-Prozessen und Unentscheidbarkeit. Ausgezeichnete Behandlung von Markov-Prozessen S. 449ff. Bespricht Z-Transformationen, D-Transformationen in ihrem Kontext.
  • Kemeny, John G.; Hazleton Mirkil; J. Laurie Snell; Gerald L. Thompson (1959). Endliche mathematische Strukturen (1. Aufl.). Englewood Cliffs, NJ: Prentice-Hall, Inc. Bibliothek des Kongresses Kartenkatalognummer 59-12841.Klassischer Text. vgl. Kapitel 6 Endliche Markov-Ketten S. 384ff.
  • John G. Kemeny & J. Laurie Snell (1960) Finite Markov Chains , D. van Nostrand Company ISBN  0-442-04328-7
  • E. Nummelin. „Allgemeine irreduzible Markov-Ketten und nicht-negative Operatoren“. Cambridge University Press, 1984, 2004. ISBN  0-521-60494-X
  • Seneta, E. Nicht-negative Matrizen und Markov-Ketten . 2. Rev. Hg., 1981, XVI, 288 S., Softcover Springer Series in Statistics. (Ursprünglich herausgegeben von Allen & Unwin Ltd., London, 1973) ISBN  978-0-387-29765-1
  • Kishor S. Trivedi , Wahrscheinlichkeit und Statistik mit Zuverlässigkeit, Warteschlangen und Informatikanwendungen , John Wiley & Sons, Inc. New York, 2002. ISBN  0-471-33341-7 .
  • KS Trivedi und RASahner, SHARPE im Alter von 22 Jahren , Bd. 36, nein. 4, S. 52–57, ACM SIGMETRICS Performance Evaluation Review, 2009.
  • RA Sahner, KS Trivedi und A. Puliafito, Leistungs- und Zuverlässigkeitsanalyse von Computersystemen: ein beispielbasierter Ansatz unter Verwendung des SHARPE-Softwarepakets , Kluwer Academic Publishers, 1996. ISBN  0-7923-9650-2 .
  • G. Bolch, S. Greiner, H. de Meer und KS Trivedi, Queuing Networks and Markov Chains , John Wiley, 2. Auflage, 2006. ISBN  978-0-7923-9650-5 .

Externe Links