Markov -Kette

Ein Diagramm, das einen zweistaatlichen Markov-Prozess darstellt, wobei die Zustände mit E und A gekennzeichnet sind, und A stellt die Wahrscheinlichkeit des Markov-Prozesses dar, wechselt von einem Zustand in einen anderen Zustand, wobei die vom Pfeil angegebene Richtung angezeigt wird. Wenn sich der Markov -Prozess beispielsweise in Zustand A befindet, beträgt die Wahrscheinlichkeit, dass er sich in den Zustand E ändert, 0,4, während die Wahrscheinlichkeit, dass sie in Zustand A bleibt, 0,6 beträgt.

A Markov -Kette oder Markov -Prozess ist ein Stochastisches Modell Beschreibung a Reihenfolge möglicher Ereignisse, bei denen die Wahrscheinlichkeit jedes Ereignisses nur von dem im vorherigen Ereignis erreichten Staat abhängt.[1][2][3] A Zähler Unendlich unendlich Sequenz, in der die Kette zu diskreten Zeitschritten den Zustand bewegt, gibt a diskrete Markov-Kette (DTMC). EIN kontinuierliche Zeit Prozess wird als a genannt Kontinuierliche Markov-Kette (CTMC). Es ist nach dem benannt Russisch Mathematiker Andrey Markov.

Markov -Ketten haben viele Anwendungen als Statistische Modelle von realen Prozessen,,[1][4][5][6] wie studieren Geschwindigkeitsregelungssysteme in Kraftfahrzeuge, Warteschlangen oder Kunden von Kunden, die an einem Flughafen, Währung ankamen, ankommen Wechselkurse und Tierpopulationsdynamik.[7]

Markov -Prozesse sind die Grundlage für allgemeine stochastische Simulationsmethoden als Markov -Kette Monte Carlo, die zur Simulation der Probenahme aus komplexen Wahrscheinlichkeitsverteilungen verwendet werden und die Anwendung in gefunden haben Bayes'sche Statistik, Thermodynamik, Statistische Mechanik, Physik, Chemie, Wirtschaft, Finanzen, Signalverarbeitung, Informationstheorie und Sprachverarbeitung.[7][8][9]

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

Einführung

Russischer Mathematiker Andrey Markov

Definition

Ein Markov -Prozess ist a stochastischer Prozess das erfüllt das Markov Eigenschaft[1] (manchmal als "charakterisiert als"Erinnerungslosigkeit"). In einfacherer Hinsicht ist es ein Prozess, für den Vorhersagen in Bezug auf zukünftige Ergebnisse ausschließlich auf seinem gegenwärtigen Zustand und - vor allem - wie die Vorhersagen beruhen, genauso gut sind wie diejenigen, die die vollen Geschichte des Prozesses kennen.[12] Mit anderen Worten, bedingt Im gegenwärtigen Zustand des Systems sind seine zukünftigen und vergangenen Staaten unabhängig.

Eine Markov -Kette ist eine Art Markov -Prozess, der entweder diskret ist Zustandsraum oder ein diskreter Indexsatz (häufig die Zeit darstellt), aber die genaue Definition einer Markov -Kette variiert.[13] Zum Beispiel ist es üblich, eine Markov -Kette als Markov -Prozess in beiden zu definieren diskrete oder kontinuierliche Zeit mit einem zählbaren Zustand (also unabhängig von der Art der Zeit),[14][15][16][17] Es ist aber auch üblich, eine Markov -Kette als diskrete Zeit im zählbaren oder kontinuierlichen Zustand zu definieren (daher unabhängig vom Zustandsraum).[13]

Arten von Markov -Ketten

Das System Zustandsraum und Zeitparameterindex muss angegeben werden. Die folgende Tabelle gibt einen Überblick über die verschiedenen Instanzen von Markov -Prozessen für verschiedene Ebenen der Allgemeinheit des Zustandsraums und für diskrete Zeit gegen die kontinuierliche Zeit:

Zählbarer Zustand Kontinuierlicher oder allgemeiner Zustandsraum
Diskrete Zeit (diskrete Zeit) Markov-Kette auf einem zählbaren oder endlichen Zustandsraum Markov -Kette auf einem messbaren Zustandsraum (zum Beispiel, Harris -Kette))
Kontinuierliche Zeit Kontinuierlicher Zeitmarkov-Prozess oder Markov-Sprungprozess Irgendein kontinuierlicher stochastischer Prozess mit der Markov -Eigenschaft (zum Beispiel die, die Wiener -Prozess))

Beachten Sie, dass in der Literatur keine endgültige Übereinstimmung über die Verwendung einiger Begriffe vorhanden ist, die Sonderfälle von Markov -Prozessen bedeuten. Normalerweise ist der Begriff "Markov -Kette" für einen Prozess mit einem diskreten Satz von Zeiten reserviert, dh a diskrete Markov-Kette (DTMC),[1][18] Einige Autoren verwenden jedoch den Begriff "Markov -Prozess", um sich auf a zu beziehen Markov-Kette kontinuierlicher Zeit (CTMC) ohne ausdrückliche Erwähnung.[19][20][21] Darüber hinaus gibt es andere Erweiterungen von Markov -Prozessen, die als solche bezeichnet werden, aber nicht unbedingt in eine dieser vier Kategorien fallen (siehe Markov -Modell). Darüber hinaus muss der Zeitindex nicht unbedingt realiert sein; Wie beim Zustandsraum gibt es denkbare Prozesse, die sich durch Indexsätze mit anderen mathematischen Konstrukten bewegen. Beachten Sie, dass die Markov-Kette des allgemeinen staatlichen Raums in einem solchen Grad allgemein ist, dass er keine bestimmte Laufzeit hat.

Während der Zeitparameter normalerweise diskret ist, ist die Zustandsraum einer Markov-Kette hat keine allgemein vereinbarten Beschränkungen: Der Begriff kann sich auf einen Prozess in einem willkürlichen Zustand verweisen.[22] Viele Anwendungen von Markov -Ketten verwenden jedoch endlich oder Zähler Unendlich unendlich 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 diskreten diskreten Zustands-Raum-Fall, sofern nicht anders erwähnt.

Übergänge

Die Änderungen des Status des Systems werden als Übergänge bezeichnet.[1] Die mit verschiedenen Zustandsänderungen verbundenen Wahrscheinlichkeiten werden als Übergangswahrscheinlichkeiten bezeichnet. Der Prozess ist durch einen Zustandsraum gekennzeichnet, a Übergangsmatrix Beschreibung der Wahrscheinlichkeiten bestimmter Übergänge und eines Ausgangszustands (oder anfänglicher Verteilung) über den Zustandsraum. Nach der Konvention nehmen wir an, dass alle möglichen Zustände und Übergänge in die Definition des Prozesses einbezogen wurden, sodass es immer einen nächsten Zustand gibt und der Prozess nicht endet.

Ein zufälliger Prozess mit diskreter Zeit umfasst ein System, das sich in einem bestimmten Zustand in einem bestimmten Zustand befindet und sich zwischen den Schritten zufällig ändert.[1] Die Schritte werden oft als Momente in der Zeit betrachtet, können sich jedoch ebenso gut auf die physische Entfernung oder eine andere diskrete Messung beziehen. Formal sind die Schritte die Ganzzahlen oder natürliche Zahlenund der zufällige Prozess ist eine Zuordnung von diesen zu Zuständen.[23] Das Markov -Eigentum gibt an, dass die Bedingte Wahrscheinlichkeitsverteilung Für das System im nächsten Schritt (und in allen zukünftigen Schritten) hängt nur der aktuelle Stand des Systems und nicht zusätzlich vom Status des Systems in früheren Schritten ab.

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

Geschichte

Markov studierte Markov Processe im frühen 20. Jahrhundert und veröffentlichte 1906 sein erstes Papier zu diesem Thema.[24][25][26][27] Markov -Prozesse in kontinuierlicher Zeit wurden lange zuvor entdeckt Andrey MarkovDie Arbeit im frühen 20. Jahrhundert[1] in Form der Poisson -Prozess.[28][29][30] Markov war daran interessiert, eine Erweiterung unabhängiger zufälliger Sequenzen zu untersuchen, motiviert durch eine Meinungsverschiedenheit mit Pavel Nekrasov Wer behauptete, Unabhängigkeit sei für die notwendig Schwaches Gesetz großer Anzahl halten.[1][31] In seinem ersten Artikel über Markov -Ketten, das 1906 veröffentlicht wurde, zeigte Markov, dass unter bestimmten Bedingungen die durchschnittlichen Ergebnisse der Markov -Kette zu einem festen Wertvektor konvergieren würden, wodurch ein schwaches Gesetz großer Zahlen ohne die Annahme der Unabhängigkeit nachgewiesen wurde.[1][25][26][27] die allgemein als Voraussetzung für solche mathematischen Gesetze angesehen worden war.[27] Markov verwendete später Markov -Ketten, um die Verteilung von Vokalen in zu untersuchen Eugene OneGin, geschrieben von Alexander Pushkin, und bewies a Zentralgrenze Theorem für solche Ketten.[1][25]

1912 Henri Poincaré studierte Markov -Ketten an Finite -Gruppen Mit dem Ziel, Kartenschlurfen zu studieren. Andere frühe Verwendungen von Markov -Ketten umfassen ein Diffusionsmodell, das von eingeführt wurde durch Paul und Tatyana Ehrenfest im Jahr 1907 und ein Verzweigungsprozess, eingeführt von durch Francis Galton und Henry William Watson 1873 vor der Arbeit von Markov.[25][26] Nach der Arbeit von Galton und Watson wurde später festgestellt, dass ihr Verzweigungsverfahren etwa drei Jahrzehnte zuvor unabhängig entdeckt und studiert wurde Irénée-Jules Bienaymé.[32] Ab 1928, Maurice Fréchet Interessierte sich für Markov -Ketten und führte schließlich dazu, dass er 1938 eine detaillierte Studie über Markov -Ketten veröffentlichte.[25][33]

Andrey Kolmogorov entwickelt in einem Papier von 1931 ein großer Teil der frühen Theorie der markov-Prozesse kontinuierlicher Zeit.[34][35] Kolmogorov wurde teilweise von Louis Bacheliers 1900 Arbeiten über Schwankungen an der Börse sowie von 1900 als auch von Börsenmärkten inspiriert Norbert WienerArbeiten zu Einsteins Modell der Brownschen Bewegung.[34][36] Er führte und untersuchte einen bestimmten Satz von Markov -Prozessen, die als Diffusionsprozesse bekannt sind, bei denen er eine Reihe von Differentialgleichungen abgeleitet hat, die die Prozesse beschreiben.[34][37] Unabhängig von Kolmogorovs Arbeit, Sydney Chapman abgeleitet in einem Papier von 1928 eine Gleichung, die jetzt die genannt wird Chapman -Kolmogorov -Gleichung, auf weniger mathematisch streng als Kolmogorov, während er Brownsche Bewegung studierte.[38] Die Differentialgleichungen werden jetzt Kolmogorov -Gleichungen bezeichnet[39] oder die Kolmogorov -Chapman -Gleichungen.[40] Andere Mathematiker, die erheblich zu den Grundlagen von Markov -Prozessen beigetragen haben William Fellerab 1930er Jahren und später Eugene Dynkinab den 1950er Jahren.[35]

Beispiele

  • Zufällige Spaziergänge Basierend auf Ganzzahlen und den Spieler des Spielers Problem sind Beispiele für Markov -Prozesse.[41][42] Einige Variationen dieser Prozesse wurden hunderte von Jahren im Zusammenhang mit unabhängigen Variablen untersucht.[43][44][45] Zwei wichtige Beispiele für Markov -Prozesse sind die Wiener -Prozess, auch bekannt als die Brownsche Bewegung Prozess und die Poisson -Prozess,[28] die als die wichtigsten und zentralsten stochastischen Prozesse in der Theorie stochastischer Prozesse angesehen werden.[46][47][48] Diese beiden Prozesse sind Markov -Prozesse in kontinuierlicher Zeit, während zufällige Spaziergänge auf den Ganzzahlen und das Ruinproblem des Spielers Beispiele für Markov -Prozesse in diskreter Zeit sind.[41][42]
  • Eine berühmte Markov-Kette ist der sogenannte "Drunkard's Walk", ein zufälliger Spaziergang auf der Zahlenlinie wobei bei jedem Schritt die Position mit gleicher Wahrscheinlichkeit um +1 oder -1 ändern kann. Aus 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, in der die Position erreicht wurde. Beispielsweise betragen die Übergangswahrscheinlichkeiten von 5 bis 4 und 5 bis 6 sowohl 0,5 als auch alle anderen Übergangswahrscheinlichkeiten von 5. Diese Wahrscheinlichkeiten sind unabhängig davon, ob das System zuvor in 4 oder 6 war.
  • Ein weiteres Beispiel sind die Ernährungsgewohnheiten eines hoch theoretischen Tieres, das nur Trauben, Käse oder Salat frisst und deren Ernährungsgewohnheiten den folgenden Regeln entsprechen:
    • Es isst genau einmal am Tag.
    • Wenn es heute Käse gegessen hat, wird es morgen mit gleicher Wahrscheinlichkeit Salat oder Trauben essen.
    • Wenn es heute Trauben aß, werden morgen Trauben mit Wahrscheinlichkeit 1/10, Käse mit Wahrscheinlichkeit 4/10 und Salat mit Wahrscheinlichkeit 5/10 gegessen.
    • Wenn es heute Salat gegessen hat, wird morgen Trauben mit Wahrscheinlichkeit 4/10 oder Käse mit Wahrscheinlichkeit 6/10 gegessen. Es wird morgen nicht wieder Salat essen.
  • Die Essgewohnheiten dieses Tieres können mit einer Markov -Kette modelliert werden, da seine Auswahl morgen nur davon abhängt, was es heute gegessen hat, nicht von dem, was es gestern oder zu einer anderen Zeit in der Vergangenheit gegessen hat. Eine statistische Eigenschaft, die berechnet werden könnte, ist der erwartete Prozentsatz über einen langen Zeitraum der Tage, an denen das Tier Trauben frisst.
  • Eine Reihe von unabhängigen Ereignissen (z. B. eine Reihe von Münzflips) erfüllt die formale Definition einer Markov -Kette. Die Theorie wird jedoch normalerweise nur angewendet, wenn die Wahrscheinlichkeitsverteilung des nächsten Schritts nicht trivial vom aktuellen Zustand abhängt.

Ein Nicht-Markov-Beispiel

Angenommen, es gibt eine Münzhandlung mit fünf Vierteln (jeweils 25 ¢), fünf Groschen (jeweils 10 ¢) und fünf Nickel (jeweils 5 ¢), und eins nach dem anderen werden zufällig aus der Geldbörse gezogen und sind sind auf einen Tisch setzen. Wenn repräsentiert den Gesamtwert der auf der Tabelle festgelegten Münzen danach n zeichnet, mit dann die Sequenz ist nicht ein Markov -Prozess.

Um zu sehen, warum dies der Fall ist, nehmen Sie an, dass in den ersten sechs Unentschieden alle fünf Nickel und ein Viertel gezogen werden. Daher . Wenn wir nicht nur wissen Aber auch die früheren Werte, dann können wir bestimmen, welche Münzen gezogen wurden, und wir wissen, dass die nächste Münze kein Nickel sein wird. So können wir das bestimmen mit Wahrscheinlichkeit 1. Wenn wir die früheren Werte jedoch nicht kennen, basieren Sie dann nur auf dem Wert Wir könnten vermuten, dass wir vier Groschen und zwei Nickel gezeichnet hatten. In diesem Fall wäre es sicherlich möglich, als nächstes einen weiteren Nickel zu zeichnen. So sind unsere Vermutungen zu werden von unserem Wertekenntnis zuvor betroffen .

Es ist jedoch möglich, dieses Szenario als Markov -Prozess zu modellieren. Anstatt zu definieren die darstellen Gesamtwert Von den Münzen auf dem Tisch konnten wir definieren die darstellen zählen der verschiedenen Münztypen auf der Tabelle. Zum Beispiel, könnte definiert werden, um den Staat zu repräsentieren, in dem nach 6 Einserzen ein Viertel, Zero Dimes und fünf Nickel auf dem Tisch liegen. Dieses neue Modell könnte durch dargestellt werden durch Mögliche Zustände, wobei jeder Zustand die Anzahl der Münzen jedes Typs (von 0 bis 5) darstellt, die auf der Tabelle liegen. (Nicht alle diese Zustände sind innerhalb von 6 Unentschieden erreichbar . Die Wahrscheinlichkeit des Erreichens Jetzt hängt ab ; Zum Beispiel der Staat Ist nicht möglich. Nach dem zweiten Unentschieden hängt die dritte Auslosung davon ab, welche Münzen bisher gezogen wurden, aber nicht mehr nur von den Münzen, die für den ersten Zustand gezogen wurden (da das Szenario wahrscheinlich probabilistisch wichtige Informationen hinzugefügt wurden). Auf diese Weise die Wahrscheinlichkeit der Der Zustand hängt ausschließlich vom Ergebnis der ab Zustand.

Formale Definition

Diskrete Markov-Kette

Eine diskrete Markov-Kette ist eine Abfolge von zufällige Variablen X1, X2, X3, ... mit dem Markov Eigenschaft, nämlich dass die Wahrscheinlichkeit, in den nächsten Zustand zu ziehen, nur vom gegenwärtigen Zustand und nicht von den vorherigen Zuständen abhängt:

Wenn beides bedingte Wahrscheinlichkeiten sind gut definiert, das heißt, wenn

Die möglichen Werte von Xi Form a Zählbar S genannt den Staatsraum der Kette.

Variationen

  • Zeithomogene Markov-Ketten sind Prozesse, bei denen
    für alle n. Die Wahrscheinlichkeit des Übergangs ist unabhängig von n.
  • Stationäre Markov -Ketten sind Prozesse, bei denen
    für alle n und k. Jede stationäre Kette kann nach Bayes 'Regel als zeithomogen erwiesen werden.
    Ein notwendiger und ausreichender Zustand für eine zeithomogene Markov-Kette, die stationär ist, ist, dass die Verteilung von ist eine stationäre Verteilung der Markov -Kette.
  • Eine Markov -Kette mit Speicher (oder eine Markov -Ordnungskette m) wo m ist endlich, ist ein Prozess erfüllt
    Mit anderen Worten, der zukünftige Zustand hängt von der Vergangenheit ab m Zustände. Es ist möglich, eine Kette zu konstruieren aus Das hat die 'klassische' Markov -Eigenschaft, indem er den bestellten Zustand als staatlichen Raum einnimmt m-Tupel von X Werte, d. h., .

Kontinuierliche Markov-Kette

Eine markov-Kette kontinuierlicher Zeit (Xt)t≥ 0 wird durch einen endlichen oder zählbaren Zustandsraum definiert S, a Übergangsrate Matrix Q mit Dimensionen, die dem des Zustandsraums und der anfänglichen Wahrscheinlichkeitsverteilung im Zustandsraum definiert sind. Zum ij, die Elemente qij sind nicht negativ und beschreiben die Rate des Prozessübergänge aus dem Staat i zu sagen j. Die Elemente qII werden so ausgewählt, dass jede Zeile der Übergangsrate-Matrix auf Null beträgt, während die Zeilen-Sum einer Wahrscheinlichkeitsübergangsmatrix in einer (diskreten) Markov-Kette alle gleich sind.

Es gibt drei äquivalente Definitionen des Prozesses.[49]

Infinitesimale Definition

Die kontinuierliche Zeitmarkov -Kette ist durch die Übergangsraten gekennzeichnet, die Derivate in Bezug auf die Zeit der Übergangswahrscheinlichkeiten zwischen den Zuständen I und j.

Lassen Seien Sie die zufällige Variable, die den Zustand des Prozesses zum Zeitpunkt beschreibt tund nehmen an, der Prozess ist in einem Zustand i zum Zeitpunkt t. Dann wissend , ist unabhängig von früheren Werten , und wie h → 0 für alle j und für alle tAnwesend

wo ist der Kronecker Delta, Verwendung der Little-o Notation. Das kann als Messung angesehen werden, wie schnell der Übergang von i zu j das passiert.

Sprungkette/Haltezeitdefinition

Definieren Sie eine diskrete Markov-Kette Yn um das zu beschreiben nDer Sprung des Prozesses und der Variablen S1, S2, S3, ... um die Haltezeiten in jedem der Staaten zu beschreiben, in denen Si folgt der Exponentialverteilung mit dem Ratenparameter -qYiYi.

Übergangswahrscheinlichkeitsdefinition

Für jeden Wert n = 0, 1, 2, 3, ... und Zeiten, die bis zu diesem Wert von indiziert sind n: t0, t1, t2, ... und alle Staaten, die zu diesen Zeiten aufgezeichnet wurden i0, i1, i2, i3, ... es hält das

wo pij ist die Lösung der Vorwärtsgleichung (a Differentialgleichung erster Ordnung))

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

Finite -State -Raum

Wenn der Staatsraum ist endlichDie Übergangswahrscheinlichkeitsverteilung kann durch a dargestellt werden Matrix, genannt die Übergangsmatrix, mit der (i, j) th Element von P gleicht

Da jede Reihe von P Summen zu einem und alle Elemente sind nicht negativ, P ist ein Rechte stochastische Matrix.

Stationäre Verteilungsbeziehung zu Eigenvektoren und Vereinfachungen

Eine stationäre Verteilung π ist ein (Reihe) Vektor, dessen Einträge nicht negativ und summe bis 1, durch den Betrieb der Übergangsmatrix unverändert P darauf und so wird definiert von

Durch Vergleich dieser Definition mit der von einem Eigenvektor Wir sehen, dass die beiden Konzepte verwandt sind und das

ist normalisiert () Vielfache eines linken Eigenvektors e der Übergangsmatrix P mit einem Eigenwert von 1. Wenn es mehr als einen Einheiten -Eigenvektor gibt, ist eine gewichtete Summe der entsprechenden stationären Zustände ebenfalls ein stationärer Zustand. Für eine Markov -Kette interessiert sich jedoch normalerweise mehr für einen stationären Zustand, der die Grenze der Verteilungssequenz für eine gewisse Erstverteilung darstellt.

Die Werte einer stationären Verteilung sind mit dem Zustandsraum von verbunden P und seine Eigenvektoren haben ihre relativen Proportionen erhalten. Da die Komponenten von π positiv sind und die Einschränkung, dass ihre Summe eine Einheit ist Wir sehen, dass das Punktprodukt von π mit einem Vektor, dessen Komponenten alle 1 sind und dass π auf a liegt Simplex.

Zeithomogene Markov-Kette mit einem endlichen Zustand

Wenn die Markov-Kette zeithomogen ist, dann die Übergangsmatrix P ist nach jedem Schritt gleich, also die k-Bep -Übergangswahrscheinlichkeit kann als die berechnet werden k-del der Übergangsmatrix, Pk.

Wenn die Markov -Kette nicht reduzierbar und aperiodisch ist, gibt es eine einzigartige stationäre Verteilung π.[50] Zusätzlich in diesem Fall Pk Konvergiert zu einer Rangeinmatrix, in der jede Zeile die stationäre Verteilung ist π:

wo 1 ist der Spaltenvektor mit allen Einträgen gleich 1. Dies wird von der angegeben Perron -Frobenius -Theorem. Wenn, was auch immer, was auch immer, Es wird gefunden, dann kann die stationäre Verteilung der betreffenden Markov -Kette für jede Startverteilung leicht bestimmt werden, wie nachstehend erläutert wird.

Für einige stochastische Matrizen P, das Limit existiert nicht während der stationären Verteilung, wie in diesem Beispiel gezeigt:

(Dieses Beispiel zeigt eine periodische Markov -Kette.)

Da es eine Reihe verschiedener Sonderfälle zu berücksichtigen gibt, kann der Prozess des Findens dieser Grenze, wenn sie vorhanden ist, eine lange Aufgabe sein. Es gibt jedoch viele Techniken, die dazu beitragen können, diese Grenze zu finden. Lassen P Bohne n×n Matrix und definieren

Es ist immer wahr, dass

Subtrahieren Q von beiden Seiten und Faktoren ergibt dann

wo In ist der Identitätsmatrix von Größe n, und 0n,n ist der Null Matrix von Größe n×n. Multiplizieren stochastische Matrizen immer wieder eine andere stochastische Matrix, also Q muss ein sein Stochastische Matrix (Siehe Definition oben). Es reicht manchmal aus, die obige Matrixgleichung und die Tatsache zu verwenden, dass Q ist eine stochastische Matrix für die Lösung Q. Einschließlich der Tatsache, dass die Summe jeder Reihen in P ist 1, da gibt es n+1 Gleichungen zur Bestimmung n Unbekannte, daher ist es rechnerisch einfacher, wenn man einerseits eine Zeile in auswählt Q und ersetzt jedes seiner Elemente durch den einen und auf dem anderen ersetzt das entsprechende Element (das in derselben Spalte) im Vektor 0und als nächst Q.

Hier ist eine Methode dafür: Definieren Sie zuerst die Funktion f(A) um die Matrix zurückzugeben A durch die rechts meistgesetzte Spalte durch alle 1 ersetzt. Wenn [f(PIn)]–1 existiert dann[51][50]

Erklären: Die ursprüngliche Matrixgleichung entspricht a System von n × n linearen Gleichungen in n × n Variablen. Und es gibt n lineare Gleichungen aus der Tatsache, dass Q ein Recht ist Stochastische Matrix deren jede Zeile auf 1 senkt. Daher benötigt sie n × n unabhängige lineare Gleichungen der (n × n+n) Gleichungen, um die n × n -Variablen zu lösen. In diesem Beispiel wurden die N-Gleichungen aus „q multipliziert mit der rechten Spalte (P-In)“ durch die n stochastischen N ersetzt.

Eine Sache zu bemerken ist, dass wenn P hat ein Element Pi,i auf seiner Hauptdiagonale, die gleich 1 und die entspricht iDie Zeile oder Spalte wird ansonsten mit 0 gefüllt, dann bleibt diese Zeile oder Spalte in allen nachfolgenden Kräften unverändert Pk. Daher die idie Zeile oder Spalte von Q wird die 1 und die 0 in denselben Positionen haben wie in P.

Konvergenzgeschwindigkeit zur stationären Verteilung

Wie bereits erwähnt, aus der Gleichung (falls vorhanden) die stationäre (oder stationäre) Verteilung π ist ein linker Eigenvektor der Reihe Stochastische Matrix P. Dann angenommen P ist diagonalisierbar oder äquivalent P hat n Linear unabhängige Eigenvektoren, Konvergenzgeschwindigkeit wird wie folgt ausgearbeitet. (Für nicht-diagonalisierbare, das heißt, defekte Matrizen, man kann mit dem beginnen Jordanische Normalform von P und fahren Sie in ähnlicher Weise mit etwas mehr Argumenten fort.[52]

Lassen U Seien Sie die Matrix der Eigenvektoren (jeweils normalisiert auf eine L2 -Norm gleich 1), wobei jede Säule ein linker Eigenvektor von ist P und lass Σ die diagonale Matrix der linken Eigenwerte von sein P, das ist, Σ = Diag (λ1,λ2,λ3, ...,λn). Dann vorbei Eigenschaft

Lassen Sie die Eigenwerte so aufgezählt werden, dass:

Seit P ist eine Reihe stochastischer Matrix, der größte linke Eigenwert ist 1. Wenn es eine einzigartige stationäre Verteilung gibt, dann ist der größte Eigenwert und der entsprechende Eigenvektor auch einzigartig (weil es kein anderes gibt π Dies löst die obige stationäre Verteilungsgleichung). Lassen ui sei der i-TH -Spalte von U Matrix, das heißt, ui ist der linke Eigenvektor von P entsprechend λi. Lass es auch x eine Länge sein n Zeilenvektor, der eine gültige Wahrscheinlichkeitsverteilung darstellt; Seit den Eigenvektoren ui Spanne wir können schreiben

Wenn wir uns vermehren x mit P Von rechts und fortsetzen Sie diesen Vorgang mit den Ergebnissen fort, erhalten wir am Ende die stationäre Verteilung π. Mit anderen Worten, π = uixpp...P = XPk wie k → ∞. Das bedeutet

Seit π = u1, π(k) Ansätze zur π wie k → ∞ mit einer Geschwindigkeit in der Reihenfolge von λ2/λ1 exponentiell. Dies folgt, weil somit λ2/λ1 ist der dominante Begriff. Je kleiner das Verhältnis ist, desto schneller ist die Konvergenz.[53] Zufallsrauschen in der Zustandsverteilung π kann diese Konvergenz auch zur stationären Verteilung beschleunigen.[54]

Allgemeiner Staatsraum

Harris -Ketten

Viele Ergebnisse für Markov -Ketten mit endlichem Zustand können auf Ketten mit unzähligen Zustand verallgemeinert werden Harris -Ketten.

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

Lokal interagierende Markov -Ketten

In Anbetracht einer Sammlung von Markov -Ketten, deren Evolution den Zustand anderer Markov -Ketten berücksichtigt, hängt mit dem Begriff lokal interagierender Markov -Ketten zusammen. Dies entspricht der Situation, in der der Staatsraum eine (kartesische) Produktform hat. Sehen Interaktionsteilchensystem und Stochastische zelluläre Automaten (probabilistische zelluläre Automaten). Siehe zum Beispiel Interaktion von Markov -Prozessen[55] oder.[56]

Eigenschaften

Zwei Zustände kommunizieren miteinander, wenn beide durch eine Abfolge von Übergängen mit positiver Wahrscheinlichkeit voneinander erreichbar sind. Dies ist eine Äquivalenzbeziehung, die eine Reihe von Kommunikationsklassen ergibt. Eine Klasse ist geschlossen, wenn die Wahrscheinlichkeit, die Klasse zu verlassen, Null ist. Eine Markov -Kette ist nicht reduzierbar, wenn es eine Kommunikationsklasse gibt, den Staatsraum.

Ein Staat i hat Periode wenn ist der größter gemeinsamer Teiler der Anzahl der Übergänge, durch die i kann erreicht werden, beginnend von i. Das ist:

Ein Staat i soll vorübergehend sein, wenn er von abhängig von iEs gibt eine Wahrscheinlichkeit ungleich Null, dass die Kette niemals zurückkehren wird i. Es ist sonst wiederkehrend. Für einen wiederkehrenden Zustand iDie mittlere Trefferzeit ist definiert als:

Bundesland i ist positiv wiederkehrend, wenn ist sonst endlich und null wiederkehrend. Periodizität, Vergleich, Wiederholung und positives und nulles Wiederauftreten sind Klasseneigenschaften - wenn ein Staat über das Eigentum verfügt, haben alle Staaten in seiner kommunizierenden Klasse das Eigentum.

Ein Staat i wird als absorbierend bezeichnet, wenn es keine ausgehenden Übergänge aus dem Zustand gibt.

Ergodizität

Ein Staat i wird gesagt, dass Ergodisch Wenn es aperiodisch und positiv wiederkehrend ist. Mit anderen Worten, ein Zustand i ist ergodisch, wenn es wiederkehrend ist, eine Zeit von von 1und hat eine endliche mittlere Wiederholungszeit. Wenn alle Staaten in einer nicht reduzierbaren Markov -Kette ergod sind, gilt die Kette als ergod.[zweifelhaft ]

Es kann gezeigt werden, dass eine endliche, nicht reduzierbare Markov -Kette endlich ergodisch ist, wenn sie einen aperiodischen Zustand hat. Allgemeiner ist eine Markov -Kette ergodisch, wenn es eine Zahl gibt N so dass jeder Staat in einer beliebigen Anzahl von Schritten weniger oder gleich einer Zahl aus einem anderen Zustand erreicht werden kann N. Bei einer vollständig verbundenen Übergangsmatrix, bei der alle Übergänge eine Wahrscheinlichkeit ungleich Null aufweisen, wird diese Bedingung erfülltN= 1.

Eine Markov-Kette mit mehr als einem Zustand und nur einem außerfeiligen Übergang pro Zustand ist entweder nicht irreduzibler oder nicht aperiodisch, daher kann nicht ergodisch sein.

Markovsche Darstellungen

In einigen Fällen haben anscheinend nicht-markovische Prozesse möglicherweise noch markovische Darstellungen, die durch Erweiterung des Konzepts der "aktuellen" und "zukünftigen" Staaten erstellt werden. Zum Beispiel lassen X ein nicht markovischer Prozess sein. Dann einen Prozess definieren Y, so dass jeder Zustand von Y repräsentiert ein Zeitinterval von Zuständen von X. Mathematisch nimmt dies die Form an:

Wenn Y hat die markov -Eigenschaft, dann ist es eine markovsche Darstellung von X.

Ein Beispiel für einen nicht-markovischen Prozess mit einer Markovschen Darstellung ist eine autoregressiv Zeitfolgen von Ordnung größer als eins.[57]

Trefferzeiten

Die Trefferzeit ist die Zeit, die in einem bestimmten Satz von Staaten beginnt, bis die Kette in einem bestimmten Zustand oder in Staaten eintrifft. Die Verteilung eines solchen Zeitraums hat eine Phasentypverteilung. Die einfachste solche Verteilung ist die eines einzelnen exponentiell verteilten Übergangs.

Erwartete Trefferzeiten

Für eine Teilmenge von Zuständen AS, der Vektor kA Trefferzeiten (wo Element repräsentiert die erwarteter Wert, beginnend im Staat i dass die Kette einen der Staaten im Set betritt A) ist die minimale nicht negative Lösung für[58]

Zeitumkehr

Für einen CTMC XtDer zeitlich umgestaltete Prozess wird definiert sein . Durch Kellys Lemma Dieser Prozess hat die gleiche stationäre Verteilung wie der Vorwärtsverfahren.

Eine Kette soll reversibel sein, wenn der umgekehrte Prozess dem Vorwärtsprozess übereinstimmt. Kolmogorovs Kriterium Gibt an, dass die notwendige und ausreichende Bedingung für ein reversibeles Verfahren besteht, dass das Produkt der Übergangsraten um eine geschlossene Schleife in beiden Richtungen gleich sein muss.

Embedded Markov -Kette

Eine Methode zum Auffinden der Stationäre Wahrscheinlichkeitsverteilung, π, von einem Ergodisch Markov-Kette kontinuierlicher Zeit, Q, ist, indem er zuerst seine findet Embedded Markov -Kette (EMC). Streng genommen ist der EMC eine regelmäßige diskrete Markov-Kette, die manchmal als als bezeichnet wird Sprungprozess. Jedes Element der Ein-Schritt-Übergangswahrscheinlichkeitsmatrix des EMC, S, wird bezeichnet durch sij, und repräsentiert die bedingte Wahrscheinlichkeit des Übergangs vom Staat i in den Zustand j. Diese bedingten Wahrscheinlichkeiten können von gefunden werden

Davon, S kann geschrieben werden als

wo I ist der Identitätsmatrix und Diag (Q) ist der diagonale Matrix gebildet durch Auswahl der Hauptdiagonale Aus der Matrix Q und alle anderen Elemente auf Null setzen.

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

mit ein Zeilenvektor sein, so dass alle Elemente in sind größer als 0 und = 1. Daraus, π kann gefunden werden als

(S kann periodisch sein, auch wenn Q ist nicht. Einmal π wird gefunden, es muss auf a normalisiert werden Einheitsvektor.))

Ein weiterer diskreter Zeitprozess, der von einer Markov-Kette kontinuierlicher Zeit abgeleitet werden kann X(t) in Intervallen von δ -Zeiteinheiten. Die zufälligen Variablen X(0),X(δ),X(2δ), ... Geben Sie die Sequenz der vom δ-Skelett besuchten Zustände an.

Spezielle Arten 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 an der Grundlage von Beobachtungen angepasst werden soll:

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

Bernoulli -Schema

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

Beachten Sie jedoch von der Ornstein Isomorphismus Theorem, dass jede aperiodische und irreduzible Markov -Kette isomorph für ein Bernoulli -Schema ist;[59] Man könnte daher gleichermaßen behaupten, dass Markov -Ketten ein "Sonderfall" von Bernoulli -Schemata sind. Der Isomorphismus erfordert im Allgemeinen eine komplizierte Rekodierung. Der Isomorphismus -Theorem ist noch ein bisschen stärker: Es heißt, dass das heißt irgendein Stationärer stochastischer Prozess ist isomorph für ein Bernoulli -Schema; Die Markov -Kette ist nur ein solches Beispiel.

Unterschreibung des endlichen Typs

Wenn die Markov -Matrix durch die ersetzt wird Adjazenzmatrix von a Finite GraphDie resultierende Verschiebung wird als a bezeichnet Topologische Markov -Kette oder ein Unterschreibung des endlichen Typs.[59] Eine Markov -Matrix, die mit der Adjazenzmatrix kompatibel ist messen Auf der Unterschicht. Viele chaotisch Dynamische Systeme sind isomorph bis topologische Markov -Ketten; Beispiele beinhalten Diffeomorphismen von geschlossene Verbrennungen, das Prouhet -Thue -Morse -System, das Chacon -System, Sofic -Systeme, kontextfreie Systeme und Blockkodierungssysteme.[59]

Anwendungen

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

Physik

Markovsche Systemen erscheinen ausführlich in Thermodynamik und Statistische Mechanik, wann immer Wahrscheinlichkeiten verwendet werden, um unbekannte oder nicht modellierte Details des Systems darzustellen, wenn angenommen werden kann, dass die Dynamik zeitinvariant ist und dass kein relevanter Verlauf berücksichtigt werden muss, was nicht bereits in die Zustandsbeschreibung enthalten ist.[60][61] Beispielsweise arbeitet ein thermodynamischer Zustand unter einer Wahrscheinlichkeitsverteilung, die schwierig oder teuer zu erwerben ist. Daher kann die Markov-Ketten-Monte-Carlo-Methode verwendet werden, um Proben zufällig aus einer Schwarzkiste zu zeichnen, um die Wahrscheinlichkeitsverteilung von Attributen über einen Bereich von Objekten zu approximieren.[61]

Die Pfade in der Pfadintegralformulierung der Quantenmechanik sind Markov -Ketten.[62]

Markov -Ketten werden in verwendet Gitter QCD Simulationen.[63]

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 kontinuierliche Zeitmarkov -Kette, wobei der Zustand die Anzahl der Moleküle jeder Spezies und mit Reaktionen als mögliche Übergänge der Kette ist.[64] Markov-Ketten und kontinuierliche Markov-Prozesse sind in der Chemie nützlich, wenn physikalische Systeme die Markov-Eigenschaft genau annähern. Stellen Sie sich zum Beispiel eine große Anzahl vor n von Molekülen in Lösung in Zustand A, von denen jeder eine chemische Reaktion auf den Zustand B mit einer bestimmten Durchschnittsrate erleiden kann. Vielleicht ist das Molekül ein Enzym, und die Zustände beziehen sich darauf, wie es gefaltet ist. Der Zustand eines einzelnen Enzyms folgt einer Markov -Kette, und da die Moleküle im Wesentlichen unabhängig voneinander sind, ist die Anzahl der Moleküle in Zustand A oder B jeweils n Mal die Wahrscheinlichkeit, dass ein bestimmtes Molekül in diesem Zustand ist.

Das klassische Modell der Enzymaktivität, Michaelis -Mentenkinetik, kann als Markov -Kette angesehen werden, wobei zu jedem Zeitschritt die Reaktion in eine Richtung verläuft. Während Michaelis-Menten ziemlich einfach ist, können weitaus kompliziertere Reaktionsnetzwerke auch mit Markov-Ketten modelliert werden.[65]

Ein auf einer Markov-Kette basierender Algorithmus wurde auch verwendet, um das fragmentbasierte Wachstum von Chemikalien zu fokussieren in Silico auf eine gewünschte Klasse von Verbindungen wie Arzneimitteln oder Naturprodukten.[66] Wenn ein Molekül gezüchtet wird, wird ein Fragment aus dem entstehenden Molekül als "Strom" -Zustand ausgewählt. Es ist sich seiner Vergangenheit nicht bewusst (dh, es ist sich nicht bewusst, was bereits damit verbunden ist). Es wechselt dann in den nächsten Zustand, wenn ein Fragment daran gebunden ist. Die Übergangswahrscheinlichkeiten werden in Datenbanken authentischer Verbindungsklassen geschult.[67]

Auch das Wachstum (und die Zusammensetzung) von Copolymere Kann mit 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, wechselnd oder in langen Läufen desselben Monomers zu wechseln). Wegen sterische EffekteMarkov-Effekte zweiter Ordnung können auch eine Rolle beim Wachstum einiger Polymerketten spielen.

In ähnlicher Weise wurde vermutet, dass die Kristallisation und das Wachstum einiger Epitaxien Superlattice Oxidmaterialien können von Markov -Ketten genau beschrieben werden.[68]

Biologie

Markov -Ketten werden in verschiedenen Bereichen der Biologie verwendet. Bemerkenswerte Beispiele sind:

Testen

Mehrere Theoretiker haben die Idee des Markov -Kettenstatistikstests (MCST) vorgeschlagen, einer Methode zur Konjizieren von Markov -Ketten, um a zu bilden "Markov -Decke", ordnen diese Ketten in mehreren rekursiven Schichten (" Wafering ") und erzeugen effizientere Testsätze-Sampeln-als Ersatz für erschöpfende Tests. MCSTs werden auch in zeitlichen staatlichen Netzwerken verwendet; Chilukuri et al. Zwerber -Unsicherheits -Argumentationsnetzwerke für Evidence Fusion mit Anwendungen für die Erkennung und Verfolgung von Objekten "(Sciencedirect) liefert eine Hintergrund- und Fallstudie für die Anwendung von MCSTs auf einen größeren Anwendungsbereich.

Variabilität der Sonneneinstrahlung

Variabilitätsbewertungen der Sonneneinstrahlung sind nützlich für Solarenergie Anwendungen. Die Variabilität der Sonneneinstrahlung an jedem Ort im Laufe der Zeit ist hauptsächlich eine Folge der deterministischen Variabilität des Sonnenwegs über die Himmelskuppel und die Variabilität der Trübung. Die Variabilität der zugänglichen Sonneneinstrahlung auf der Erdoberfläche wurde unter Verwendung von Markov -Ketten modelliert.[71][72][73][74] einschließlich der Modellierung der beiden Zustände klar und bewölkt als zweistaatliche Markov-Kette.[75][76]

Spracherkennung

Versteckte Markov -Modelle sind die Grundlage für die meisten modernsten Automatische Spracherkennung Systeme.

Informationstheorie

Markov -Ketten werden während der gesamten Informationsverarbeitung verwendet. Claude Shannon'S berühmte Papier von 1948 Eine mathematische Kommunikationstheorie, was in einem einzigen Schritt das Feld von erstellte Informationstheorie, eröffnet durch Einführung des Konzepts von Entropie Durch Markov -Modellierung der englischen Sprache. Solche idealisierten Modelle können viele der statistischen Regelmäßigkeiten von Systemen erfassen. Auch ohne die vollständige Struktur des Systems perfekt zu beschreiben, können solche Signalmodelle sehr effektiv ermöglichen Datenkompression durch Entropie -Codierung Techniken wie arithmetische Kodierung. Sie erlauben auch effektive Zustandsschätzung und Mustererkennung. Markov -Ketten spielen auch eine wichtige Rolle in Verstärkungslernen.

Markov -Ketten sind auch die Grundlage für versteckte Markov -Modelle, die ein wichtiges Instrument in verschiedenen Bereichen wie Telefonnetzwerken sind (die die verwenden Viterbi -Algorithmus für die Fehlerkorrektur), Spracherkennung und Bioinformatik (z. B. bei der Umständigkeitserkennung[77]).

Das Lzma Verlustloser Datenkomprimierungsalgorithmus kombiniert Markov -Ketten mit Lempel-Ziv-Kompression um sehr hohe Kompressionsverhältnisse zu erreichen.

Warteschlangenentheorie

Markov -Ketten sind die Grundlage für die analytische Behandlung von Warteschlangen (Warteschlangenentheorie). Agner Krarup Erlang Initiierte das Thema 1917.[78] Dies macht sie für die Optimierung der Leistung von Telekommunikationsnetzwerken von entscheidender Bedeutung, bei denen Nachrichten häufig um begrenzte Ressourcen (wie Bandbreite) konkurrieren müssen.[79]

Zahlreiche Warteschlangenmodelle verwenden kontinuierliche Markov-Ketten. Zum Beispiel eine M/M/1 -Warteschlange ist ein CTMC auf den nicht negativen Ganzzahlen i zu i+1 tritt mit Geschwindigkeit auf λ nach a Poisson -Prozess und beschreiben Jobankömmlinge, während Übergänge von i zu i- 1 (für i> 1) mit Geschwindigkeit auftreten μ (Jobservice -Zeiten sind exponentiell verteilt) und beschreiben abgeschlossene Dienste (Abfahrten) aus der Warteschlange.

Internetanwendungen

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

Das Seitenrang einer Webseite, wie sie verwendet von Google wird durch eine Markov -Kette definiert.[80][81][82] Es ist die Wahrscheinlichkeit, auf der Seite zu sein in der stationären Verteilung auf der folgenden Markov -Kette auf allen (bekannten) Webseiten. Wenn ist die Anzahl der bekannten Webseiten und eine Seite hat Links dazu hat es dann die Übergangswahrscheinlichkeit für alle Seiten, die mit und verbunden sind für alle Seiten, mit denen nicht verbunden sind. Der Parameter wird ungefähr 0,15 angesehen.[83]

Markov -Modelle wurden auch verwendet, um das Web -Navigationsverhalten von Benutzern zu analysieren. Der Web-Link-Übergang eines Benutzers auf einer bestimmten Website kann mit Markov-Modellen erster oder zweiter Ordnung modelliert werden und kann verwendet werden, um Vorhersagen in Bezug auf zukünftige Navigation zu treffen und die Webseite für einen einzelnen Benutzer zu personalisieren.

Statistiken

Markov -Kettenmethoden sind auch sehr wichtig, um Sequenzen von Zufallszahlen zu generieren, um sehr komplizierte gewünschte Wahrscheinlichkeitsverteilungen über einen Prozess namens Markov Chain Monte Carlo (MCMC) genau widerzuspiegeln. In den letzten Jahren hat dies die Praktikabilität von revolutioniert Bayes'sche Inferenz Methoden, die eine breite Palette von ermöglichen hintere Verteilungen simuliert und ihre Parameter numerisch gefunden.

Wirtschaft und Finanzen

Markov -Ketten werden in Finanzen und Wirtschaftswissenschaften verwendet, um eine Vielzahl verschiedener Phänomene zu modellieren, einschließlich der Verteilung des Einkommens, der Größenverteilung von Unternehmen, Vermögenspreisen und Marktunfällen. D. G. Champernowne baute ein Markov -Kettenmodell der Einkommensverteilung im Jahr 1953.[84] Herbert A. Simon Der Co-Autor Charles Bonini verwendete ein Markov-Kettenmodell, um eine stationäre Yule-Verteilung der Unternehmensgrößen abzuleiten.[85] Louis Bachelier war der erste, der beobachtete, dass die Aktienkurse einen zufälligen Spaziergang folgten.[86] Der Zufallsspaziergang wurde später als Beweis für die Effizienzmarkthypothese und Random Walk -Modelle waren in der Literatur der 1960er Jahre beliebt.[87] Regime-sankte Modelle von Geschäftszyklen wurden populär von James D. Hamilton (1989), die eine Markov -Kette verwendeten, um Schalter zwischen hohem und niedrigem BIP -Wachstum (oder alternativ wirtschaftliche Expansionen und Rezessionen) zu modellieren.[88] Ein neueres Beispiel ist das Markov Switching Multifractal Modell von Laurent E. Calvet und Adlai J. Fisher, der auf der Bequemlichkeit früherer Regime-Switching-Modelle aufbaut.[89][90] Es verwendet eine willkürlich große Markov -Kette, um das Volatilität von Vermögenswerten zu steigern.

Die dynamische Makroökonomie nutzt Markov -Ketten stark. Ein Beispiel ist die Verwendung von Markov -Ketten, um exogen zu modellieren. Allgemeines Gleichgewicht Einstellung.[91]

Ratingagenturen Erstellen Sie jährliche Tabellen der Übergangswahrscheinlichkeiten für Anleihen verschiedener Kreditratings.[92]

Sozialwissenschaften

Markov -Ketten werden im Allgemeinen zur Beschreibung verwendet Pfadabhängig Argumente, bei denen die aktuellen strukturellen Konfigurationen zukünftige Ergebnisse bedeuten. Ein Beispiel ist die Umformulierung der Idee, ursprünglich aufgrund Karl Marx's Das Kapital, Binden wirtschaftliche Entwicklung zum Aufstieg von Kapitalismus. In der aktuellen Forschung ist es üblich, eine Markov -Kette zu verwenden, um zu modellieren, wie ein Land, sobald ein Land ein bestimmtes Maß an wirtschaftlicher Entwicklung erreicht, die Konfiguration struktureller Faktoren wie die Größe des Mittelklasse, das Verhältnis von städtisch zu ländlicher Residenz, die Rate von politisch Mobilisierung usw. erzeugt eine höhere Wahrscheinlichkeit des Übergangs von autoritär zu demokratisches Regime.[93]

Spiele

Markov -Ketten können verwendet werden, um viele Zufallsspiele zu modellieren.[1] Die Kinderspiele Schlangen und Leitern und "Hi ho! Cherry-o"Zum Beispiel werden genau durch Markov -Ketten dargestellt. In jeder Runde beginnt der Spieler in einem bestimmten Zustand (auf einem bestimmten Platz) und hat von dort festgelegt, dass sie in bestimmte andere Zustände (Quadrate) umziehen.

Musik

Markov -Ketten sind in beschäftigt in Algorithmische Musikkomposition, speziell in Software wie zum Beispiel Cound, Max, und Supercollider. In einer Kette erster Ordnung werden die Zustände des Systems zu Note- oder Tonhöhenwerten und a Wahrscheinlichkeitsvektor Für jede Note wird eine Übergangswahrscheinlichkeitsmatrix erstellt (siehe unten). Ein Algorithmus wird aufgebaut MIDI Beachten Sie Werte, Frequenz (Hz) oder eine andere wünschenswerte Metrik.[94]

Matrix der 1. Ordnung
Notiz A C E
EIN 0,1 0,6 0,3
C 0,25 0,05 0,7
E 0,7 0,3 0
2nd-Ordnung Matrix
Anmerkungen A 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
Dg 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 unter Berücksichtigung des aktuellen Zustands eingeführt werden und Auch der vorherige Zustand, wie in der zweiten Tabelle angegeben. Höher, nTH-Ordnungsketten neigen dazu, bestimmte Noten zusammen zu "gruppieren", während sie gelegentlich in andere Muster und Sequenzen einbrechen. Diese Ketten höherer Ordnung neigen dazu, Ergebnisse mit einem Gefühl von zu erzielen Phrasal Struktur und nicht das "ziellose Wandering", das von einem System erster Ordnung erzeugt wird.[95]

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

Normalerweise müssen Musiksysteme spezifische Kontrollbeschränkungen für die von ihnen erzeugten Sequenzen endlicher Länge durchsetzen, aber Kontrollbeschränkungen sind nicht mit Markov-Modellen kompatibel, da sie Langstreckenabhängigkeiten induzieren, die gegen die Markov-Hypothese des begrenzten Gedächtnisses verstoßen. Um diese Einschränkung zu überwinden, wurde ein neuer Ansatz vorgeschlagen.[98]

Baseball

Markov -Kettenmodelle werden seit 1960 in der fortschrittlichen Baseballanalyse verwendet, obwohl ihre Verwendung immer noch selten ist. Jedes halbe Inning eines Baseballspiels passt zum Markov-Kettenstatus, wenn die Anzahl der Läufer und Outs berücksichtigt wird. Während eines AT-Bats gibt es 24 mögliche Kombinationen von Outs und Position der Läufer. 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.[99] Er diskutiert auch verschiedene Arten von Strategien und Spielbedingungen: Wie Markov -Kettenmodelle verwendet wurden, um Statistiken für Spielsituationen wie z. Ammer und Basisdiebstahl und Unterschiede beim Spielen auf Gras vs. Astroturf.[100]

Markov Textgeneratoren

Markov -Prozesse können auch verwendet werden Erzeugen Sie oberflächlich aussehenden Text bei einem Beispieldokument. Markov -Prozesse werden in einer Vielzahl von Erholung verwendet. "Parodiegenerator"Software (siehe dissoziierte Presse, Jeff Harrison,[101] Mark V. Shaney,[102][103] und Akademien Neutronium). Es gibt mehrere Open-Source-Textgenerierungsbibliotheken, die Markov-Ketten verwenden, einschließlich des Rita-Toolkits.

Probabilistische Prognose

Markov -Ketten wurden für die Prognose in mehreren Bereichen verwendet: zum Beispiel Preistrends,[104] Windkraft,[105] und Sonneneinstrahlung.[106] Die Markov -Kettenprognosemodelle verwenden eine Vielzahl von Einstellungen, aus der Diskretisierung der Zeitreihen.[105] zu versteckte Markov -Modelle kombiniert mit Wavelets,[104] und das Markov -Kettenmischungsverteilungsmodell (MCM).[106]

Siehe auch

Anmerkungen

  1. ^ a b c d e f g h i j k l Gagniuc, Paul A. (2017). Markov -Ketten: Von der Theorie zur Implementierung und Experimente. USA, NJ: John Wiley & Sons. S. 1–235. ISBN 978-1-119-38755-8.
  2. ^ "Markov -Kette | Definition der Markov -Kette in den USA Englisch durch Oxford -Wörterbücher". Oxford Wörterbücher | Englisch. Abgerufen 2017-12-14.
  3. ^ Definition bei Brilliant.org "Brilliant Math and Science Wiki". Abgerufen am 12. Mai 2019
  4. ^ Samuel Karlin; Howard E. Taylor (2. Dezember 2012). Ein erster Kurs in stochastischen Prozessen. Akademische Presse. p. 47. ISBN 978-0-08-057041-9. Archiviert Aus dem Original am 23. März 2017.
  5. ^ Bruce Hajek (12. März 2015). Zufällige Prozesse für Ingenieure. Cambridge University Press. ISBN 978-1-316-24124-0. Archiviert Aus dem Original am 23. März 2017.
  6. ^ G. Latouche; V. Ramaswami (1. Januar 1999). Einführung in die matrixanalytischen Methoden in der stochastischen Modellierung. SIAM. S. 4–. ISBN 978-0-89871-425-8. Archiviert Aus dem Original am 23. März 2017.
  7. ^ a b Sean Meyn; Richard L. Tweedie (2. April 2009). Markov -Ketten und stochastische Stabilität. Cambridge University Press. p. 3. ISBN 978-0-521-73182-9. Archiviert Aus dem Original am 23. März 2017.
  8. ^ Reuven Y. Rubinstein; Dirk P. Kroese (20. September 2011). Simulation und die Monte -Carlo -Methode. John Wiley & Sons. p. 225. ISBN 978-1-118-21052-9. Archiviert Aus dem Original am 23. März 2017.
  9. ^ Dani Gamerman; Hedibert F. Lopes (10. Mai 2006). Markov -Kette Monte Carlo: Stochastische Simulation für Bayes'sche Inferenz, zweite Ausgabe. CRC Press. ISBN 978-1-58488-587-0. Archiviert Aus dem Original am 23. März 2017.
  10. ^ "Markovian". Oxford Englisch Wörterbuch (Online ed.). Oxford University Press. (Abonnement oder teilnehmende Institutsmitgliedschaft erforderlich.)
  11. ^ Modellbasierte Signalverarbeitung. John Wiley & Sons. 27. Oktober 2005. ISBN 9780471732662.
  12. ^ Øksendal, B. K. (Bernt Karsten) (2003). Stochastische Differentialgleichungen: Eine Einführung mit Anwendungen (6. Aufl.). Berlin: Springer. ISBN 3540047581. OCLC 52203046.
  13. ^ a b Søren Asmussen (15. Mai 2003). Angewandte Wahrscheinlichkeit und Warteschlangen. Springer Science & Business Media. p. 7. ISBN 978-0-387-00211-8. Archiviert Aus dem Original am 23. März 2017.
  14. ^ Emanuel Parzen (17. Juni 2015). Stochastische Prozesse. Courier Dover Publications. p. 188. ISBN 978-0-486-79688-8. Archiviert Aus dem Original am 20. November 2017.
  15. ^ Samuel Karlin; Howard E. Taylor (2. Dezember 2012). Ein erster Kurs in stochastischen Prozessen. Akademische Presse. S. 29 und 30. ISBN 978-0-08-057041-9. Archiviert Aus dem Original am 23. März 2017.
  16. ^ John Lamperti (1977). Stochastische Prozesse: Eine Übersicht über die mathematische Theorie. Springer-Verlag. S. 106–121. ISBN 978-3-540-90275-1. Archiviert vom Original am 2017-03-23.
  17. ^ Sheldon M. Ross (1996). Stochastische Prozesse. Wiley. S. 174 und 231. ISBN 978-0-471-12062-9. Archiviert vom Original am 2017-03-23.
  18. ^ Everitt, B.S. (2002) Das Cambridge Dictionary of Statistics. TASSE. ISBN0-521-81099-x
  19. ^ Parzen, E. (1962) Stochastische Prozesse, Holden-Day. ISBN0-8162-6664-6 (Tabelle 6.1)
  20. ^ Dodge, Y. (2003) Das Oxford -Wörterbuch über statistische Begriffe, OUP. ISBN0-19-920613-9 (Eintrag für "Markov-Kette")
  21. ^ Dodge, Y. Das Oxford -Wörterbuch über statistische Begriffe, OUP. ISBN0-19-920613-9
  22. ^ Meyn, S. Sean P. und Richard L. Tweedie. (2009) Markov -Ketten und stochastische Stabilität. Cambridge University Press. (Vorwort, S. iii)
  23. ^ a b c Gagniuc, Paul A. (2017). Markov -Ketten: Von der Theorie zur Implementierung und Experimente. USA, NJ: John Wiley & Sons. S. 159–163. ISBN 978-1-119-38755-8.
  24. ^ Gagniuc, Paul A. (2017). Markov -Ketten: Von der Theorie zur Implementierung und Experimente. USA, NJ: John Wiley & Sons. S. 2–8. ISBN 978-1-119-38755-8.
  25. ^ a b c d e Charles Miller Grinstead; James Laurie Snell (1997). Einführung in die Wahrscheinlichkeit. American Mathematical Soc. pp.464–466. ISBN 978-0-8218-0749-1.
  26. ^ a b c Pierre Bremaud (9. März 2013). Markov -Ketten: Gibbs Fields, Monte Carlo -Simulation und Warteschlangen. Springer Science & Business Media. p. ix. ISBN 978-1-4757-3124-8. Archiviert Aus dem Original am 23. März 2017.
  27. ^ a b c Hayes, Brian (2013). "Erste Glieder in der Markov -Kette". Amerikanischer Wissenschaftler. 101 (2): 92–96. doi:10.1511/2013.101.92.
  28. ^ a b Sheldon M. Ross (1996). Stochastische Prozesse. Wiley. S. 235 und 358. ISBN 978-0-471-12062-9. Archiviert vom Original am 2017-03-23.
  29. ^ Jarrow, Robert; Protter, Philip (2004). "Eine kurze Geschichte der stochastischen Integration und der mathematischen Finanzierung: die frühen Jahre 1880–1970". Eine Festschreibung für Herman Rubin. Institut für mathematische Statistik Lecture Notes - Monographieserie. S. 75–91. Citeseerx 10.1.1.114.632. doi:10.1214/lnms/1196285381. ISBN 978-0-940600-61-4. ISSN 0749-2170.
  30. ^ Guttorp, Peter; Thorarinsdottir, Thordis L. (2012). "Was ist mit diskretem Chaos, dem Quenouille -Prozess und der scharfen Markov -Eigenschaft passiert? Einige Geschichte stochastischer Punkte Prozesse". Internationale statistische Überprüfung. 80 (2): 253–268. doi:10.1111/j.1751-5823.2012.00181.x. ISSN 0306-7734. S2CID 80836.
  31. ^ Seneta, E. (1996). "Markov und die Geburt der Kettenabhängigkeitstheorie". Internationale statistische Überprüfung / Revue Internationale de Statistique. 64 (3): 255–257. doi:10.2307/1403785. ISSN 0306-7734. JStor 1403785.
  32. ^ Seneta, E. (1998). "I.J. Bienaymé [1796–1878]: Kritikalität, Ungleichheit und Internationalisierung". Internationale statistische Überprüfung / Revue Internationale de Statistique. 66 (3): 291–292. doi:10.2307/1403518. ISSN 0306-7734. JStor 1403518.
  33. ^ Bru B, Hertz S (2001). "Maurice Fréchet". In Heyde CC, Seneta E, Crépel P, Fienberg SE, Gani J (Hrsg.). Statistiker der Jahrhunderte. New York, NY: Springer. S. 331–334. doi:10.1007/978-1-4613-0179-0_71. ISBN 978-0-387-95283-3.
  34. ^ a b c Kendall, D. G.; Batchelor, G. K.; Bingham, N. H.; Hayman, W. K.; Hyland, J. M. E.; Lorentz, G. G.; Moffatt, H. K.; Parry, W.; Razborov, A. A.; Robinson, C. A.; Whittle, P. (1990). "Andrei Nikolaevich Kolmogorov (1903–1987)". Bulletin der London Mathematical Society. 22 (1): 33. doi:10.1112/BLMS/22.1.31. ISSN 0024-6093.
  35. ^ a b Cramér, Harald (1976). "Ein halbes Jahrhundert mit Wahrscheinlichkeitstheorie: Einige persönliche Erinnerungen". Die Annalen der Wahrscheinlichkeit. 4 (4): 509–546. doi:10.1214/AOP/1176996025. ISSN 0091-1798.
  36. ^ Marc Barbut; Bernard Locker; Laurent Mazliak (23. August 2016). Paul Lévy und Maurice Fréchet: 50 Jahre Korrespondenz in 107 Briefen. Springer London. p. 5. ISBN 978-1-4471-7262-8. Archiviert Aus dem Original am 23. März 2017.
  37. ^ Valeriy Skorokhod (5. Dezember 2005). Grundprinzipien und Anwendungen der Wahrscheinlichkeitstheorie. Springer Science & Business Media. p. 146. ISBN 978-3-540-26312-8. Archiviert Aus dem Original am 23. März 2017.
  38. ^ Bernstein, Jeremy (2005). "Bachelier". American Journal of Physics. 73 (5): 395–398. Bibcode:2005amjph..73..395b. doi:10.1119/1.1848117. ISSN 0002-9505.
  39. ^ William J. Anderson (6. Dezember 2012). Markov-Ketten mit kontinuierlicher Zeit: Ein von Anwendungen ausgerichteter Ansatz. Springer Science & Business Media. p. vii. ISBN 978-1-4612-3038-0. Archiviert Aus dem Original am 23. März 2017.
  40. ^ Kendall, D. G.; Batchelor, G. K.; Bingham, N. H.; Hayman, W. K.; Hyland, J. M. E.; Lorentz, G. G.; Moffatt, H. K.; Parry, W.; Razborov, A. A.; Robinson, C. A.; Whittle, P. (1990). "Andrei Nikolaevich Kolmogorov (1903–1987)". Bulletin der London Mathematical Society. 22 (1): 57. doi:10.1112/BLMS/22.1.31. ISSN 0024-6093.
  41. ^ a b Ionut Florescu (7. November 2014). Wahrscheinlichkeit und stochastische Prozesse. John Wiley & Sons. S. 373 und 374. ISBN 978-1-118-59320-2. Archiviert Aus dem Original am 23. März 2017.
  42. ^ a b Samuel Karlin; Howard E. Taylor (2. Dezember 2012). Ein erster Kurs in stochastischen Prozessen. Akademische Presse. p. 49. ISBN 978-0-08-057041-9. Archiviert Aus dem Original am 23. März 2017.
  43. ^ Gagniuc, Paul A. (2017). Markov -Ketten: Von der Theorie zur Implementierung und Experimente. USA, NJ: John Wiley & Sons. S. 1–2. ISBN 978-1-119-38755-8.
  44. ^ Weiss, George H. (2006). "Zufällige Spaziergänge". Enzyklopädie der statistischen Wissenschaften. p. 1. doi:10.1002/0471667196.ESS2180.Pub2. ISBN 978-0471667193.
  45. ^ Michael F. Shlesinger (1985). Die wundervolle Welt der Stochastik: Eine Hommage an Elliott W. Montroll. Nordholland. S. 8–10. ISBN 978-0-444-86937-1. Archiviert vom Original am 2017-03-23.
  46. ^ Emanuel Parzen (17. Juni 2015). Stochastische Prozesse. Courier Dover Publications. p. 7 und 8. ISBN 978-0-486-79688-8. Archiviert Aus dem Original am 20. November 2017.
  47. ^ Joseph L. Doob (1990). Stochastipoische Prozesse. Wiley. p. 46 und 47. Archiviert vom Original am 2017-11-20.
  48. ^ Donald L. Snyder; Michael I. Miller (6. Dezember 2012). Zufällige Punktprozesse in Zeit und Raum. Springer Science & Business Media. p. 32. ISBN 978-1-4612-3166-0. Archiviert Aus dem Original am 20. November 2017.
  49. ^ Norris, J. R. (1997). "Kontinuierliche Markov-Ketten I". Markov -Ketten. S. 60–107. doi:10.1017/CBO9780511810633.004. ISBN 9780511810633.
  50. ^ a b Serfozo, Richard (2009). "Grundlagen von angewandten stochastischen Prozessen". Wahrscheinlichkeit und ihre Anwendungen. doi:10.1007/978-3-540-89332-5. ISBN 978-3-540-89331-8. ISSN 1431-7028.
  51. ^ "Kapitel 11" Markov -Ketten "" (PDF). Archiviert (PDF) vom Original am 2017-02-15. Abgerufen 2017-06-02.
  52. ^ Schmitt, Florian; Rothlauf, Franz (2001). "Über die Bedeutung des zweitgrößten Eigenwerts für die Konvergenzrate genetischer Algorithmen". Verfahren des 14. Symposiums zu zuverlässigen verteilten Systemen. Citeseerx 10.1.1.28.6191.
  53. ^ Rosenthal, Jeffrey S. (1995). "Konvergenzraten für Markov -Ketten". Siam Review. 37 (3): 387–405. doi:10.1137/1037083. ISSN 0036-1445. JStor 2132659. Abgerufen 2021-05-31.
  54. ^ Franzke, Brandon; Kosko, Bart (1. Oktober 2011). "Rauschen kann die Konvergenz in Markov -Ketten beschleunigen". Physische Bewertung e. 84 (4): 041112. Bibcode:2011phrve..84d1112f. doi:10.1103/Physreve.84.041112. PMID 22181092.
  55. ^ Spitzer, Frank (1970). "Interaktion von Markov -Prozessen". Fortschritte in der Mathematik. 5 (2): 246–290. doi:10.1016/0001-8708 (70) 90034-4.
  56. ^ R. L. DoBrushhin; V. I. Kri︠u︡kov; A. L. Toom (1978). Stochastische zelluläre Systeme: Ergodizität, Gedächtnis, Morphogenese. ISBN 9780719022067. Archiviert vom Original am 2017-02-05. Abgerufen 2016-03-04.
  57. ^ Dolinger, G. (September 1998). "Glättung von lauten AR -Signalen mit einem adaptiven Kalman -Filter" (PDF). 9. Europäische Signalverarbeitungskonferenz (EUSIPCO 1998): 781–784.
  58. ^ Norris, J. R. (1997). "Kontinuierliche Markov-Ketten II". Markov -Ketten. S. 108–127. doi:10.1017/CBO9780511810633.005. ISBN 9780511810633.
  59. ^ a b c Matthew Nicol und Karl Petersen, (2009) "Ergodische Theorie: grundlegende Beispiele und Konstruktionen",",Enzyklopädie der Komplexität und Systemwissenschaft, Springer https://doi.org/10.1007/978-0-387-30440-3_177
  60. ^ Fitzpatrick, Richard. "Thermodynamik und statistische Mechanik" (PDF). Archiviert (PDF) vom Original am 2016-11-30. Abgerufen 2017-06-02.
  61. ^ a b Van Ravenzwaaij, Don; Cassey, Pete; Brown, Scott D. (2016-03-11). "Eine einfache Einführung in die Markov -Kette Monte -Carlo -Stichprobe". Psychonomisches Bulletin & Review. 25 (1): 143–154. doi:10.3758/s13423-016-1015-8. ISSN 1069-9384. PMC 5862921. PMID 26968853.
  62. ^ Ryder, Lewis H. (1985). Quantenfeldtheorie. Cambridge [Cambridgeshire]: Cambridge University Press. pp.160. ISBN 978-0521338592. OCLC 10533049.
  63. ^ Gattringer, Christof; Lang, Christian B (2010). Quantenchromodynamik auf dem Gitter. Vorlesungsnotizen in der Physik. Vol. 788. Springer-Verlag Berlin Heidelberg. doi:10.1007/978-3-642-01850-3. ISBN 978-3-642-01849-7. Archiviert vom Original am 2017-08-01.
  64. ^ Anderson, David F.; Kurtz, Thomas G. (2011), "Continuous Time Markov -Kettenmodelle für chemische Reaktionsnetzwerke", Design und Analyse von Biomolekularen Schaltungen, Springer New York, S. 3–42, doi:10.1007/978-1-4419-6766-4_1, ISBN 9781441967657
  65. ^ Du, chao; Kou, S. C. (September 2012). "Korrelationsanalyse der enzymatischen Reaktion eines einzelnen Proteinmoleküls". Die Annalen der angewandten Statistiken. 6 (3): 950–976. Arxiv:1209.6210. Bibcode:2012ArXIV1209.6210d. doi:10.1214/12-AOAS541. ISSN 1932-6157. PMC 3568780. PMID 23408514.
  66. ^ Kutchukian, Peter; Lou, David; Shakhnovich, Eugene (2009). "Nebel: Fragment optimierte Wachstumsalgorithmus für die De -novo -Generation von Molekülen, die eine medikamentenähnliche Chemikalie besetzen". Journal of Chemical Information and Modeling. 49 (7): 1630–1642. doi:10.1021/ci9000458. PMID 19527020.
  67. ^ Kutchukian, Peter S.; Lou, David; Shakhnovich, Eugene I. (2009-06-15). "Nebel: Fragment optimierte Wachstumsalgorithmus für die De -novo -Erzeugung von Molekülen, die den medikamenten chemischen Raum besetzen". Journal of Chemical Information and Modeling. 49 (7): 1630–1642. doi:10.1021/ci9000458. ISSN 1549-9596. PMID 19527020.
  68. ^ Kopp, V. S.; Kaganer, V. M.; Schwarzkopf, J.; Waidick, F.; Remmele, T.; Kwasniewski, a.; Schmidbauer, M. (2011). "Röntgenbeugung von nichtperiodischen geschichteten Strukturen mit Korrelationen: Analytische Berechnung und Experiment mit gemischten Aurivillius-Filmen". Acta Crystallographica Abschnitt a. 68 (Pt 1): 148–155. Bibcode:2012ACCRA..68..148K. doi:10.1107/s0108767311044874. PMID 22186291.
  69. ^ George, Dileep; Hawkins, Jeff (2009). Friston, Karl J. (Hrsg.). "Auf dem Weg zu einer mathematischen Theorie kortikaler Mikrokreislauf". PLoS Comput Biol. 5 (10): E1000532. Bibcode:2009PLSCB ... 5E0532G. doi:10.1371/journal.pcbi.1000532. PMC 2749218. PMID 19816557.
  70. ^ Gupta, Ankur; Rawlings, James B. (April 2014). "Vergleich der Parameterschätzungsmethoden in stochastischen chemischen kinetischen Modellen: Beispiele in der Systembiologie". Aiche Journal. 60 (4): 1253–1268. doi:10.1002/AIC.14409. PMC 4946376. PMID 27429455.
  71. ^ Aguiar, R. J.; Collares-Pereira, M.; Conde, J. P. (1988). "Einfaches Verfahren zum Generieren von Sequenzen täglicher Strahlungswerte unter Verwendung einer Bibliothek von Markov -Übergangsmatrizen". Solarenergie. 40 (3): 269–279. Bibcode:1988Soen ... 40..269a. doi:10.1016/0038-092X (88) 90049-7.
  72. ^ Ngoko, B. O.; Sugihara, H.; Funaki, T. (2014). "Synthetische Erzeugung von Solarstrahlungsdaten mit hoher zeitlicher Auflösung unter Verwendung von Markov -Modellen". Solarenergie. 103: 160–170. Bibcode:2014soen..103..160n. doi:10.1016/j.Solener.2014.02.026.
  73. ^ Bright, J. M.; Smith, C. I.; Taylor, P. G.; Crook, R. (2015). "Stochastische Erzeugung von synthetischen Zeitreihen, die aus mittleren stündlichen Wetterbeobachtungsdaten abgeleitet sind". Solarenergie. 115: 229–242. Bibcode:2015soen..115..229b. doi:10.1016/j.Solener.2015.02.032.
  74. ^ Munkhammar, J.; Widén, J. (2018). "Ein N-State Markov-Ketten-Mischungsverteilungsmodell des Clear-Sky-Index". Solarenergie. 173: 487–495. Bibcode:2018soen..173..487m. doi:10.1016/j.Solener.2018.07.056. S2CID 125538244.
  75. ^ Morf, H. (1998). "Das stochastische Zwei-Zustands-Solar-Bestrahlungsstärkermodell (STSIM)". Solarenergie. 62 (2): 101–112. Bibcode:1998Soen ... 62..101m. doi:10.1016/s0038-092X (98) 00004-8.
  76. ^ Munkhammar, J.; Widén, J. (2018). "Ein Ansatz der Wahrscheinlichkeitsverteilungsverteilungsmischung aus Markov-Ketten zum Clear-Sky-Index". Solarenergie. 170: 174–183. Bibcode:2018soen..170..174m. doi:10.1016/j.Solener.2018.05.055. S2CID 125867684.
  77. ^ Pratas, D; Silva, R; Pinho, a; Ferreira, P (18. Mai 2015). "Eine ausgerichtungsfreie Methode, um Neulagerungen zwischen Paaren von DNA-Sequenzen zu finden und zu visualisieren". Wissenschaftliche Berichte. 5 (10203): 10203. Bibcode:2015natsr ... 510203p. doi:10.1038/srep10203. PMC 4434998. PMID 25984837.
  78. ^ O'Connor, John J.; Robertson, Edmund F., "Markov -Kette", Archiv der Maktorgeschichte des Mathematiks, Universität von St. Andrews
  79. ^ S. P. Meyn, 2007. Steuerungstechniken für komplexe Netzwerke Archiviert 2015-05-13 bei der Wayback -Maschine, Cambridge University Press, 2007.
  80. ^ US -Patent 6.285.999
  81. ^ Gupta, Brij; Agrawal, Dharma P.; Yamaguchi, Shingo (16. Mai 2016). Handbuch der Forschung zu modernen kryptografischen Lösungen für Computer- und Cybersicherheit. IGI Global. S. 448–. ISBN 978-1-5225-0106-0. Archiviert Aus dem Original am 23. März 2017.
  82. ^ Langville, Amy N.; Meyer, Carl D. (2006). "Eine Neuordnung für das PageRank -Problem" (PDF). Siam Journal über wissenschaftliches Computer. 27 (6): 2112–2113. Citeseerx 10.1.1.58.8652. doi:10.1137/040607551. ISSN 1064-8275. Archiviert (PDF) vom Original am 2017-09-21.
  83. ^ Seite, Lawrence; Brin, Sergey; Motwani, Rajeev; Winograd, Terry (1999). Das Pageank Citation Ranking: Bestellung in das Web bringen (Technischer Bericht). Citeseerx 10.1.1.31.1768.
  84. ^ Champernowne, D (1953). "Ein Modell der Einkommensverteilung". Das Economic Journal. 63 (250): 318–51. doi:10.2307/2227127. JStor 2227127.
  85. ^ Simon, Herbert; C Bonini (1958). "Die Größenverteilung der Geschäftsfirmen". Bin. ECON. Rev. 42: 425–40.
  86. ^ Bachelier, Louis (1900). "Théorie de la Spéculation". Annales Scientifiques de l'école Normale Supérieure. 3: 21–86. doi:10.24033/Assen.476. HDL:2027/COO.31924001082803.
  87. ^ z.B. Fama, E (1965). "Das Verhalten der Börsenpreise". Journal of Business. 38.
  88. ^ Hamilton, James (1989). "Ein neuer Ansatz zur wirtschaftlichen Analyse der nichtstationären Zeitreihen und des Geschäftszyklus". Econometrica. 57 (2): 357–84. Citeseerx 10.1.1.397.3582. doi:10.2307/1912559. JStor 1912559.
  89. ^ Calvet, Laurent E.; Fisher, Adlai J. (2001). "Vorhersage der multifriktalen Volatilität". Journal of Econometrics. 105 (1): 27–58. doi:10.1016/s0304-4076 (01) 00069-0. S2CID 119394176.
  90. ^ Calvet, Laurent; Adlai Fisher (2004). "Wie man langfristige Volatilität prognostiziert: Regime-Schalter und Schätzung multifraktaler Prozesse". Journal of Financial Econometrics. 2: 49–83. Citeseerx 10.1.1.536.8334. doi:10.1093/jjfinec/nbh003. S2CID 6020401.
  91. ^ Brennan, Michael; Xiab, Yihong. "Aktienkursvolatilität und die Eigenkapitalprämie" (PDF). Finanzabteilung, Anderson School of Management, UCLA. Archiviert von das Original (PDF) am 2008-12-28.
  92. ^ "Ein Beispiel für die Markov -Kette in der Kreditrisikomodellierung der Columbia University Lectures" (PDF). Archiviert von das Original (PDF) am 24. März 2016.
  93. ^ Acemoglu, Daron; Georgy Egorov; Konstantin Sonin (2011). "Politisches Modell der sozialen Evolution". Verfahren der National Academy of Sciences. 108: 21292–21296. Bibcode:2011pnas..10821292a. Citeseerx 10.1.1.225.6090. doi:10.1073/pnas.1019454108. PMC 3271566. PMID 22198760.
  94. ^ K McAlpine; E Miranda; S Hoggar (1999). "Musik mit Algorithmen machen: ein Fallstudiumsystem". Computer Music Journal. 23 (2): 19–30. doi:10.1162/014892699559733. S2CID 40057162.
  95. ^ Curtis Roads, hrsg. (1996). Das Computermusik -Tutorial. MIT Press. ISBN 978-0-262-18158-7.
  96. ^ Xenakis, Iannis; Kanach, Sharon (1992) Formalisierte Musik: Mathematik und Denken in Komposition, Pendragon Press. ISBN1576470792
  97. ^ "Continuator". Archiviert von das Original am 13. Juli 2012.
  98. ^ Pachet, F.; Roy, P.; Barbieri, G. (2011) "Markov-Prozesse mit endlicher Länge mit Einschränkungen" Archiviert 2012-04-14 bei der Wayback -Maschine, Verfahren der 22. Internationalen gemeinsamen Konferenz über künstliche Intelligenz, IJCAI, Seiten 635–642, Barcelona, ​​Spanien, Juli 2011
  99. ^ Pankin, Mark D. "Markov -Kettenmodelle: Theoretischer Hintergrund". Archiviert von das Original Am 2007-12-09. Abgerufen 2007-11-26.
  100. ^ Pankin, Mark D. "Baseball als Markov -Kette". Archiviert vom Original am 2009-05-13. Abgerufen 2009-04-24.
  101. ^ "Dichter's Corner - Fieralingue". Archiviert von das Original am 6. Dezember 2010.
  102. ^ Kenner, Hugh; O'Rourke, Joseph (November 1984). "Ein Travestiegenerator für Micros". BYTE. 9 (12): 129–131, 449–469.
  103. ^ Hartman, Charles (1996). Virtuelle Muse: Experimente in Computerpoesie. Hannover, NH: Wesleyan University Press. ISBN 978-0-8195-2239-9.
  104. ^ a b de Souza e Silva, z. B.; Legey, L.F.L.; de Souza e Silva, E.A. (2010). "Vorhersage von Ölpreistrends mit Wavelets und versteckten Markov -Modellen". Energieökonomie. 32.
  105. ^ a b Karpinone, a; Giorgio, M; Langella, R.; Testa, A. (2015). "Markov-Kettenmodellierung für die Vorhersage von Windkraft im sehr scheißen Zeit". Forschung für elektrische Stromversorgungssysteme. 122: 152–158. doi:10.1016/j.epsr.2014.12.025.
  106. ^ a b Munkhammar, J.; van der Meer, D.W.; Widén, J. (2019). "Probabilistische Vorhersage der hochauflösenden Clear-Sky-Index-Zeitreihen unter Verwendung eines Markov-Ketten-Mischungsverteilungsmodells". Solarenergie. 184: 688–695. Bibcode:2019soen..184..688m. doi:10.1016/j.Solener.2019.04.014. S2CID 146076100.

Verweise

  • A.A. Izvestiya Fiziko-Matematicheskogo Obschestva Pri Kazanskom Universitete, 2-Ya Seriya, Tom 15, S. 135–156.
  • A. A. Markov (1971). "Erweiterung der Grenzwertsätze der Wahrscheinlichkeitstheorie auf eine Summe von Variablen, die in einer Kette verbunden sind". Nachdruck in Anhang B von: R. Howard. Dynamische probabilistische Systeme, Volumen 1: Markov -Ketten. John Wiley und Söhne.
  • Klassischer Text in der Übersetzung: Markov, A. A. (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 veröffentlicht von Addison-Wesley; Nachdruck von Gesellschaft für industrielle und angewandte Mathematik ISBN0-89871-296-3. (Siehe Kapitel 7)
  • J. L. Doob (1953) Stochastische Prozesse. New York: John Wiley und Söhne ISBN0-471-52369-0.
  • S. P. Meyn und R. L. Tweedie (1993) Markov -Ketten und stochastische Stabilität. London: Springer-Verlag ISBN0-387-19832-6. online: MCSS . Zweite Ausgabe zu erscheinen, Cambridge University Press, 2009.
  • S. P. Meyn. Steuerungstechniken für komplexe Netzwerke. Cambridge University Press, 2007. ISBN978-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. Library of Congress Card Catalog Nummer 67-25924. ] Umfangreiches, weitreichendes Buch für Spezialisten, die sowohl für theoretische Informatiker als auch für Elektroingenieure geschrieben wurden. Mit detaillierten Erklärungen zu Zustandsminimierungstechniken, FSMs, Turing -Maschinen, Markov -Prozessen und Unentschlossenheit. Hervorragende Behandlung von Markov -Prozessen S. 449ff. Diskutiert z-transformen, d transformiert in ihrem Kontext.
  • Kemeny, John G.; Hazleton Mirkil; J. Laurie Snell; Gerald L. Thompson (1959). Finite mathematische Strukturen (1. Aufl.). Englewood Cliffs, NJ: Prentice-Hall, Inc. Library of Congress Card Catalog Nummer 59-12841. Klassischer Text. vgl. Kapitel 6 Finite Markov -Ketten S. 384ff.
  • John G. Kemeny & J. Laurie Snell (1960) Finite Markov -Ketten, D. van Nostrand Company ISBN0-442-04328-7
  • E. Nummelin. "Allgemeine irreduzible Markov-Ketten und nicht negative Operatoren". Cambridge University Press, 1984, 2004. ISBN0-521-60494-x
  • Seneta, E. Nicht negative Matrizen und Markov-Ketten. 2. rev. Hrsg., 1981, XVI, 288 S., Softcover Springer -Serie in Statistik. (Ursprünglich veröffentlicht von Allen & Unwin Ltd., London, 1973) ISBN978-0-387-29765-1
  • Kishor S. Trivedi, Wahrscheinlichkeit und Statistiken mit Zuverlässigkeits-, Warteschlangen- und Informatikanwendungen, John Wiley & Sons, Inc. New York, 2002. ISBN0-471-33341-7.
  • K. S. Trivedi und R.A.Sahner, Sharpe im Alter von zweiundzwanzig Jahren, vol. 36, nein. 4, S. 52–57, ACM Sigmetrics Performance Evaluation Review, 2009.
  • R. A. Sahner, K. S. Trivedi und A. PuliaFito, Leistungs- und Zuverlässigkeitsanalyse von Computersystemen: Ein Beispielbasierter Ansatz mit dem Sharpe-Softwarepaket, Kluwer Academic Publishers, 1996. ISBN0-7923-9650-2.
  • G. Bolch, S. Greiner, H. de Meer und K. S. Trivedi, Warteschlangennetzwerke und Markov -KettenJohn Wiley, 2. Auflage, 2006. ISBN978-0-7923-9650-5.

Externe Links