Eine Kette von Markov, genannt nach Andrey Markov, ist ein mathematisches System, das Übergänge von einem Staat bis einen anderen zwischen einer begrenzten oder zählbaren Zahl von möglichen Staaten erlebt. Es ist ein Zufallsprozess charakterisiert als memoryless: Der folgende Staat hängt nur vom aktuellen Staat und nicht von der Folge von Ereignissen ab, die ihm vorangegangen sind. Diese spezifische Art von "memorylessness" wird das Eigentum von Markov genannt. Ketten von Markov haben viele Anwendungen als statistische Modelle von wirklichen Prozessen.

Einführung

Formell ist eine Kette von Markov ein Zufallsprozess mit dem Eigentum von Markov. Häufig wird der Begriff "Kette von Markov" gebraucht, um einen Prozess von Markov zu bedeuten, der einen getrennten (begrenzt oder zählbar) Zustandraum hat. Gewöhnlich wird eine Kette von Markov für einen getrennten Satz von Zeiten definiert (d. h., eine diskrete Zeit Kette von Markov), obwohl einige Autoren dieselbe Fachsprache verwenden, wo "Zeit" dauernde Werte nehmen kann. Der Gebrauch des Begriffes in der Kette von Markov Methodik von Monte Carlo bedeckt Fälle, wo der Prozess in der diskreten Zeit (getrennte Algorithmus-Schritte) mit einem dauernden Zustandraum ist. Der folgende konzentriert sich auf den Fall des getrennten Zustandraums der diskreten Zeit.

Ein Zufallsprozess der diskreten Zeit ist mit einem System verbunden, das in einem bestimmten Staat an jedem Schritt mit dem Staat ist, der sich zufällig zwischen Schritten ändert. Von den Schritten wird häufig als Momente rechtzeitig gedacht, aber sie können sich auf die physische Entfernung oder jedes andere getrennte Maß ebenso gut beziehen; formell sind die Schritte die ganzen Zahlen oder natürlichen Zahlen, und der Zufallsprozess ist von diesen zu Staaten kartografisch darzustellen. Das Eigentum von Markov stellt fest, dass der bedingte Wahrscheinlichkeitsvertrieb für das System am nächsten Schritt (und tatsächlich an allen zukünftigen Schritten) nur vom aktuellen Staat des Systems, und nicht zusätzlich auf dem Staat des Systems an vorherigen Schritten abhängt.

Da sich das System zufällig ändert, ist es allgemein unmöglich, mit der Gewissheit den Staat einer Kette von Markov an einem gegebenen Punkt in der Zukunft vorauszusagen. Jedoch können die statistischen Eigenschaften der Zukunft des Systems vorausgesagt werden. In vielen Anwendungen sind es diese statistischen Eigenschaften, die wichtig sind.

Die Änderungen des Staates des Systems werden Übergänge genannt, und die mit verschiedenen Zustandsänderungen vereinigten Wahrscheinlichkeiten werden Übergangswahrscheinlichkeiten genannt. Der Satz aller Staaten und Übergangswahrscheinlichkeiten charakterisiert völlig eine Kette von Markov. Durch die Tagung nehmen wir alle möglichen Staaten an, und Übergänge sind in die Definition der Prozesse eingeschlossen worden, also gibt es immer einen folgenden Staat und der Prozess für immer weitergeht.

Eine berühmte Kette von Markov ist der Spaziergang des so genannten "Alkoholikers", ein zufälliger Spaziergang auf dem Zahlenstrahl, wo, an jedem Schritt, sich die Position um +1 oder 1 mit der gleichen Wahrscheinlichkeit ändern kann. Von jeder Position gibt es zwei mögliche Übergänge zur folgenden oder vorherigen ganzen Zahl. Die Übergangswahrscheinlichkeiten hängen nur von der aktuellen Position ab, nicht von der Weise, auf die die Position erreicht wurde. Zum Beispiel sind die Übergangswahrscheinlichkeiten von 5 bis 4 und 5 bis 6 sowohl 0.5, als auch alle anderen Übergangswahrscheinlichkeiten von 5 sind 0. Diese Wahrscheinlichkeiten sind dessen unabhängig, ob das System vorher in 4 oder 6 war.

Ein anderes Beispiel ist die diätetischen Gewohnheiten zu einem Wesen, das nur Trauben, Käse oder Kopfsalat isst, und dessen sich diätetische Gewohnheiten den folgenden Regeln anpassen:

• Es isst genau einmal täglich.
• Wenn es Käse heute gegessen hat, Morgen wird es Kopfsalat oder Trauben mit der gleichen Wahrscheinlichkeit essen.
• Wenn es Trauben heute gegessen hat, Morgen wird es Trauben mit der Wahrscheinlichkeit 1/10, Käse mit der Wahrscheinlichkeit 4/10 und Kopfsalat mit der Wahrscheinlichkeit 5/10 essen.
• Wenn es Kopfsalat heute gegessen hat, wird es Kopfsalat wieder Morgen nicht essen, aber wird Trauben mit der Wahrscheinlichkeit 4/10 oder Käse mit der Wahrscheinlichkeit 6/10 essen.

Die Essgewohnheiten dieses Wesens können mit einer Kette von Markov modelliert werden, da seine Wahl Morgen allein davon abhängt, was sie heute, nicht gegessen hat, was sie gestern oder noch weiter in der Vergangenheit gegessen hat. Ein statistisches Eigentum, das berechnet werden konnte, ist der erwartete Prozentsatz im Laufe eines langen Zeitraumes der Tage, an denen das Wesen Trauben essen wird.

Eine Reihe von unabhängigen Ereignissen (zum Beispiel, eine Reihe von Münzflips) befriedigen die formelle Definition einer Kette von Markov. Jedoch wird die Theorie gewöhnlich nur angewandt, wenn der Wahrscheinlichkeitsvertrieb des nächsten Schrittes nichttrivial vom aktuellen Staat abhängt.

Viele andere Beispiele von Ketten von Markov bestehen.

Formelle Definition

Eine Kette von Markov ist eine Folge von zufälligen Variablen X, X, X... mit dem Eigentum von Markov nämlich, dass, in Anbetracht des aktuellen Zustandes, die zukünftigen und vorigen Staaten unabhängig sind. Formell,

:

Die möglichen Werte von X formen sich ein zählbarer Satz hat S den Zustandraum der Kette genannt.

Ketten von Markov werden häufig durch einen geleiteten Graphen beschrieben, wo die Ränder durch die Wahrscheinlichkeiten des Gehens von einem Staat bis die anderen Staaten etikettiert werden.

Schwankungen

• Dauernd-malige Prozesse von Markov haben einen dauernden Index.
• Zeithomogene Ketten von Markov (oder stationäre Ketten von Markov) sind Prozesse wo

::

: für den ganzen n. Die Wahrscheinlichkeit des Übergangs ist von n unabhängig.

• Eine Kette von Markov der Ordnung M (oder eine Kette von Markov mit dem Gedächtnis m), wo M begrenzt ist, sind ein Prozess, der befriedigt

::

\begin {richten }\aus

{} &\\Pr (X_n=x_n|X_ {n-1} =x_ {n-1}, X_ {n-2} =x_ {n-2}, \dots, X_1=x_1) \\

&\\Pr (X_n

x_n|X_ {n-1} =x_ {n-1}, X_ {n-2} =x_ {n-2}, \dots, X_ {n-m} =x_ {n-m})

\text {für} die n> M

\end {richten }\aus

</Mathematik>

: Mit anderen Worten hängt der zukünftige Staat von der vorigen M Staaten ab. Es ist möglich, eine Kette (Y) von (X) zu bauen, der das 'klassische' Eigentum von Markov wie folgt hat:

: Es kann bewiesen werden, dass eine Kette von Markov der Ordnung M tatsächlich auf eine Kette von Markov der Ordnung M = 1 (eine einfache Kette von Markov) reduziert werden kann. Lassen Sie tatsächlich Y = (X, X..., X), die bestellte M Tupel von X Werten. Dann ist Y eine Kette von Markov mit dem Zustandraum S und hat das klassische Eigentum von Markov.

• Ein Zusatz Kette von Markov der Ordnung M wird durch eine zusätzliche bedingte Wahrscheinlichkeit, bestimmt

::

Der Wert f (x, x, r) ist der zusätzliche Beitrag der Variable x zur bedingten Wahrscheinlichkeit.

Beispiel

Ein einfaches Beispiel wird in der Zahl rechts mit einem geleiteten Graphen gezeigt, um die Zustandübergänge darzustellen. Die Staaten vertreten, ob die Wirtschaft in einem Haussemarkt, einem Baissemarkt oder einem Zurücktreten während einer gegebenen Woche ist. Gemäß der Zahl wird einer männlichen Woche vor einer anderen männlichen Woche 90 % der Zeit, ein Baissemarkt 7.5 % der Zeit und ein Zurücktreten die anderen 2.5 % gefolgt. Von dieser Zahl ist es möglich, zum Beispiel, den langfristigen Bruchteil der Zeit zu berechnen, während deren die Wirtschaft in einem Zurücktreten, oder durchschnittlich ist, wie lange es nehmen wird, um von einem Zurücktreten bis einen Haussemarkt zu gehen. Mit den Übergangswahrscheinlichkeiten zeigen die Steady-Statewahrscheinlichkeiten an, dass 62.5 % von Wochen in einem Haussemarkt sein werden, werden 31.25 % von Wochen in einem Baissemarkt sein, und 6.25 % von Wochen werden in einem Zurücktreten sein.

Eine gründliche Entwicklung und viele Beispiele können in der Online-Monografie gefunden werden

Meyn & Tweedie 2005.

Der Anhang von Meyn 2007, auch verfügbar online, enthält gekürzten Meyn & Tweedie.

Eine Zustandsmaschine kann als eine Darstellung einer Kette von Markov verwendet werden. Eine Folge von unabhängigen und identisch verteilten Eingangssignalen (zum Beispiel, Symbole von einem binären Alphabet annehmend, das durch das Münzwerfen gewählt ist), wenn die Maschine im Staat y in der Zeit n ist, dann hängt die Wahrscheinlichkeit, dass es sich bewegt, um x in der Zeit n + 1 festzusetzen, nur vom aktuellen Staat ab.

Ketten von Markov

Die Wahrscheinlichkeit des Gehens vom Staat i, um j in n Zeitsprüngen festzusetzen, ist

:

und der Einzelschrittübergang ist

:

Für eine zeithomogene Kette von Markov:

:und:

Die N-Schritt-Übergangswahrscheinlichkeiten befriedigen die Gleichung des Hausierers-Kolmogorov, das für jeden solchen k dass 0

wo S der Zustandraum der Kette von Markov ist.

Der Randvertrieb Pr (X = x) ist der Vertrieb über Staaten in der Zeit n. Der anfängliche Vertrieb ist Pr (X = x). Die Evolution des Prozesses durch einen Zeitsprung wird durch beschrieben

:

Zeichen: Der Exponent (n) ist ein Index und nicht eine Hochzahl.

Reducibility

Wie man

sagt, ist ein Staat j von einem Staat i zugänglich (schriftlich ich  j), wenn ein System im Staat angefangen hat, habe ich eine Nichtnullwahrscheinlichkeit des Wechselns in den Staat j an einem Punkt. Formell ist Staat j vom Staat i zugänglich, wenn dort eine ganze Zahl n  0 solches dass besteht

:

Das Erlauben n, um Null zu sein, bedeutet, dass jeder Staat definiert wird, um von sich zugänglich zu sein.

Ein Staat, wie man sagt, kommuniziere ich mit dem Staat j (schriftlich ich  j) wenn sowohl ich  j als auch j  i. Eine Reihe von Staaten C ist eine kommunizierende Klasse, wenn jedes Paar von Staaten in C mit einander kommuniziert, und kein Staat in C mit jedem Staat nicht in C kommuniziert. Es kann gezeigt werden, dass die Kommunikation in diesem Sinn eine Gleichwertigkeitsbeziehung und so ist, dass kommunizierende Klassen die Gleichwertigkeitsklassen dieser Beziehung sind. Eine kommunizierende Klasse wird geschlossen, wenn die Wahrscheinlichkeit, die Klasse zu verlassen, Null nämlich ist, dass, wenn ich in C bin, aber j ist nicht dann, j von mir nicht zugänglich ist.

Ein Staat, wie man sagt, bin ich notwendig, wenn für den ganzen solchen j, dass ich  j es auch das j  i wahr bin. Ein Staat ich bin unwesentlich, wenn es nicht notwendig ist.

Schließlich, wie man sagt, ist eine Kette von Markov nicht zu vereinfachend, wenn sein Zustandraum eine einzelne kommunizierende Klasse ist; mit anderen Worten, wenn es möglich ist, zu Staat von Staat zu kommen.

Periodizität

Ein Staat ich habe Periode k, wenn eine Rückkehr, um festzusetzen, ich in Vielfachen von k Zeitsprüngen vorkommen muss. Formell wird die Periode eines Staates als definiert

:

(wo "gcd" der größte allgemeine Teiler ist). Bemerken Sie, dass, wenn auch ein Staat Periode k hat, es nicht möglich sein kann, den Staat in K-Schritten zu erreichen. Nehmen Sie zum Beispiel an, dass es möglich ist, zum Staat in {6, 8, 10, 12 zurückzukehren...} Zeitsprünge; k würde 2 sein, wenn auch 2 in dieser Liste nicht erscheint.

Wenn k = 1, dann, wie man sagt, ist der Staat aperiodisch: Umsatz, um festzusetzen, kann ich in unregelmäßigen Zeiten vorkommen. Mit anderen Worten, ein Staat ich bin aperiodisch, wenn dort n solch das für den ganzen n'  n, besteht

:

Sonst (k> 1), wie man sagt, ist der Staat mit der Periode k periodisch.

Jeder Staat eines zweiteiligen Graphen hat eine gleiche Periode.

Wiederauftreten

Ein Staat, wie man sagt, bin ich vergänglich, wenn, vorausgesetzt, dass wir im Staat i anfangen, es eine Nichtnullwahrscheinlichkeit gibt, dass wir zu mir nie zurückkehren werden. Lassen Sie formell die zufällige Variable T das erste Rückmal sein, um i (die "schlagende Zeit") festzusetzen:

:

Die Zahl

:

ist die Wahrscheinlichkeit, dass wir zurückkehren, um i zum ersten Mal danach n Schritte festzusetzen.

Deshalb Staat bin ich wenn vergänglich

:

Staat bin ich wiederkehrend (oder beharrlich), wenn es nicht vergänglich ist.

Wiederkehrende Staaten haben begrenzte schlagende Zeit mit der Wahrscheinlichkeit 1.

Mittelwiederauftreten-Zeit

Selbst wenn die schlagende Zeit mit der Wahrscheinlichkeit 1 begrenzt ist, braucht es keine begrenzte Erwartung zu haben.

Die Mittelwiederauftreten-Zeit am Staat bin ich die erwartete Rückzeit M:

:

Staat ich bin wiederkehrend positiv (oder nichtungültig beharrlich), wenn M begrenzt ist; sonst Staat bin ich wiederkehrend (oder ungültig beharrlich) ungültig.

Erwartete Zahl von Besuchen

Es kann gezeigt werden, dass ein Staat ich bin wiederkehrend, wenn, und nur wenn die erwartete Zahl von Besuchen in diesem Staat, d. h., unendlich

ist:

Das Aufsaugen von Staaten

Ein Staat ich werde fesselnd genannt, wenn es unmöglich ist, diesen Staat zu verlassen. Deshalb der Staat bin ich wenn und nur wenn fesselnd

:

Wenn jeder Staat einen fesselnden Staat erreichen kann, dann ist die Kette von Markov eine fesselnde Kette von Markov.

Ergodicity

Ein Staat, wie man sagt, bin ich ergodic, wenn es aperiodisch ist und positives wiederkehrend. Wenn alle Staaten in einer nicht zu vereinfachenden Kette von Markov ergodic sind, dann, wie man sagt, ist die Kette ergodic.

Es kann gezeigt werden, dass ein Endzustand nicht zu vereinfachende Kette von Markov ist ergodic, wenn es einen aperiodischen Staat hat. Ein Modell hat das ergodic Eigentum, wenn es eine begrenzte solche Nummer N gibt, dass jeder Staat von jedem anderen Staat in genau N Schritte erreicht werden kann. Im Falle einer völlig verbundenen Übergang-Matrix, wo alle Übergänge eine Nichtnullwahrscheinlichkeit haben, wird diese Bedingung mit N=1 erfüllt. Ein Modell mit mehr als einem Staat und gerade einem aus dem Amt scheiden Übergang pro Staat kann nicht ergodic sein.

Steady-Stateanalyse- und Begrenzungsvertrieb

Wenn die Kette von Markov eine zeithomogene Kette von Markov ist, so dass der Prozess durch eine einzelne, zeitunabhängige Matrix beschrieben wird, dann wird der Vektor einen stationären Vertrieb genannt (oder Invariant-Maß), wenn seine Einträge nichtnegativ sind und zu 1 resümieren, und wenn es befriedigt

:

Eine nicht zu vereinfachende Kette hat einen stationären Vertrieb, wenn, und nur wenn alle seine Staaten wiederkehrend positiv sind. In diesem Fall ist π einzigartig und ist mit der erwarteten Rückzeit verbunden:

:

wo das unveränderliche Normalisieren ist. Weiter, wenn die Kette sowohl nicht zu vereinfachend als auch, dann für irgendwelchen ich und j, aperiodisch

ist:

Bemerken Sie, dass es keine Annahme auf dem Startvertrieb gibt; die Kette läuft zum stationären Vertrieb unabhängig davon zusammen, wo es beginnt. Solcher π wird die Gleichgewichtsverteilung der Kette genannt.

Wenn eine Kette mehr als eine geschlossene kommunizierende Klasse hat, wird sein stationärer Vertrieb nicht einzigartig sein (denken Sie, dass irgendwelcher kommunizierende Klasse in der Kette geschlossen hat; jeder wird seinen eigenen einzigartigen stationären Vertrieb haben. Das Verlängern dieses Vertriebs zur gesamten Kette, das Setzen aller Werte zur Null außerhalb der Nachrichtenklasse, Erträge, dass der Satz von invariant Maßnahmen der ursprünglichen Kette der Satz aller konvexen Kombinationen 's) ist. Jedoch, wenn ein Staat j, dann aperiodisch

ist:

und für jeden anderen Staat i, lassen Sie f die Wahrscheinlichkeit sein, dass die Kette jemals Staat j besucht, wenn es an mir, anfängt

:

Wenn ein Staat ich mit der Periode k> 1 dann die Grenze periodisch

bin:

besteht obwohl die Grenze nicht

:

besteht wirklich für jede ganze Zahl r.

Steady-Stateanalyse und das Zeit-Inhomogeneous Kette von Markov

Eine Kette von Markov braucht nicht notwendigerweise zeithomogen zu sein, um eine Gleichgewichtsverteilung zu haben. Wenn es einen Wahrscheinlichkeitsvertrieb über solche Staaten dass gibt

:

für jeden Staat j und jedes Mal n ist dann eine Gleichgewichtsverteilung der Kette von Markov. Solcher kann in der Kette von Markov Monte Carlo (MCMC) Methoden in Situationen vorkommen, wo mehrer verschiedener Übergang matrices verwendet wird, weil jeder für eine besondere Art des Mischens effizient ist, aber jede Matrix respektiert eine geteilte Gleichgewichtsverteilung.

Zustandsraum

Wenn der Zustandraum begrenzt ist, kann der Übergangswahrscheinlichkeitsvertrieb durch eine Matrix, genannt die Übergang-Matrix, mit (ich, j) th Element von gleichem P vertreten werden

:

Seit jeder Reihe von P-Summen zu allen miteinander sind Elemente nichtnegativ, P ist eine richtige stochastische Matrix.

Zeithomogene Kette von Markov mit einem Zustandsraum

Wenn die Kette von Markov zeithomogen ist, dann ist die Übergang-Matrix P dasselbe nach jedem Schritt, so kann die K-Schritt-Übergangswahrscheinlichkeit als die k-th Macht der Übergang-Matrix, P geschätzt werden.

Der stationäre Vertrieb π ist (Reihe) Vektor, dessen Einträge nichtnegativ sind und zu 1 resümieren, der die Gleichung befriedigt

:

Mit anderen Worten ist der stationäre Vertrieb π ein normalisierter (das Meinen, dass die Summe seiner Einträge 1 ist) verlassen Eigenvektor der Übergang-Matrix, die mit dem eigenvalue 1 vereinigt ist.

Wechselweise kann π als ein fester Punkt des geradlinigen (folglich dauernd) Transformation auf dem Einheitssimplex angesehen werden, das zur Matrix P vereinigt ist. Da jede dauernde Transformation im Einheitssimplex einen festen Punkt hat, besteht ein stationärer Vertrieb immer, aber wird nicht versichert, im Allgemeinen einzigartig zu sein. Jedoch, wenn die Kette von Markov nicht zu vereinfachend und aperiodisch ist, dann gibt es einen einzigartigen stationären Vertrieb π. Zusätzlich in diesem Fall läuft P zu einer Reihe eine Matrix zusammen, in der jede Reihe der stationäre Vertrieb π ist, der, ist

:

wo 1 der Spaltenvektor mit allen Einträgen ist, die 1 gleich sind. Das wird durch den Perron-Frobenius Lehrsatz festgesetzt. Wenn, durch beliebige Mittel, gefunden wird, dann kann der stationäre Vertrieb der fraglichen Kette von Markov für jeden Startvertrieb leicht bestimmt werden, wie unten erklärt wird.

Für einen stochastischen matrices P besteht die Grenze, wie gezeigt, durch dieses Beispiel nicht:

:

Weil es mehrere verschiedene spezielle Fälle gibt, um, der Prozess in Betracht zu ziehen, diese Grenze zu finden, wenn es besteht, kann eine lange Aufgabe sein. Jedoch gibt es viele Techniken, die bei der Entdeckung dieser Grenze helfen können. Lassen Sie P eine n×n Matrix sein, und zu definieren

Es ist immer das wahr

:

Q von beiden Seiten und Factoring Abstriche zu machen, gibt dann nach

:

wo ich die Identitätsmatrix der Größe n bin, und 0 die Nullmatrix der Größe n×n ist. Das Multiplizieren zusammen stochastischen matrices gibt immer eine andere stochastische Matrix nach, so muss Q eine stochastische Matrix sein (sieh die Definition oben). Es ist manchmal genügend, die Matrixgleichung oben und die Tatsache zu verwenden, dass Q eine stochastische Matrix ist, um für Q zu lösen. Einschließlich der Tatsache, dass die Summe von jedem die Reihen in P 1 ist, gibt es n+1 Gleichungen, um n unknowns zu bestimmen, so ist es rechenbetont leichter, wenn einerseits man eine Reihe in Q auswählt und setzen Sie jedes seiner Elemente durch eines, und auf anderem einem Ersatz das entsprechende Element (dasjenige in derselben Säule) im Vektoren 0 ein, und multiplizieren Sie als nächstes diesen letzten Vektoren mit dem Gegenteil der umgestalteten ehemaligen Matrix nach links, um Q zu finden.

Hier ist eine Methode, um so zu tun: Definieren Sie erstens die Funktion f (A), um die Matrix mit seiner niedrigstwertigen Säule zurückzugeben, die durch alle 1's ersetzt ist. Wenn [f (P  I)] dann besteht

:

:Explain: Die ursprüngliche Matrixgleichung ist zu einem System von n×n geradlinigen Gleichungen in n×n Variablen gleichwertig. Und es gibt n mehr geradlinige Gleichungen von der Tatsache, dass Q eine richtige stochastische Matrix ist, deren jede Reihe zu 1 resümiert. So braucht es irgendwelche n×n unabhängigen geradlinigen Gleichungen der (n×n+n) Gleichungen, um für die n×n Variablen zu lösen. In diesem Beispiel sind die n Gleichungen von "Q multipliziert mit der niedrigstwertigen Säule (der NADEL)" durch die n stochastischen ersetzt worden.

Ein Ding zu bemerken besteht darin, dass, wenn P ein Element P auf seiner Hauptdiagonale hat, die 1 und die ith Reihe oder Säule gleich ist, mit 0's sonst gefüllt wird, dann werden diese Reihe oder Säule unverändert in allen nachfolgenden Mächten P bleiben. Folglich werden die ith Reihe oder Säule von Q 1 und der 0's in denselben Positionen wie in P haben.

Konvergenz-Geschwindigkeit zum stationären Vertrieb

Wie festgesetzt, früher, von der Gleichung, (wenn besteht) das stationäre (oder unveränderlicher Staat) ist Vertrieb π ein linker Eigenvektor der Reihe stochastische Matrix P. Lassen Sie U die Matrix von Eigenvektoren sein (jeder, der dazu normalisiert ist, eine L2 Norm zu haben, die 1 gleich ist), wo jede Säule ein linker Eigenvektor von P ist und lassen Sie Σ die Diagonalmatrix von linkem eigenvalues von P, d. h. Σ = diag (λ,λ,λ..., λ) sein. Dann durch eigendecomposition

:

Lassen Sie den eigenvalues solch dass 1 = |λ> |λ  |λ ...  | λ aufgezählt werden. Da P eine Reihe stochastische Matrix ist, ist sein größtes abgereist eigenvalue ist 1. Wenn es einen einzigartigen stationären Vertrieb gibt, dann sind der größte eigenvalue und der entsprechende Eigenvektor auch einzigartig (weil es keinen anderen π gibt, der die stationäre Vertriebsgleichung oben löst). Lassen Sie u die ith Säule der U Matrix sein, d. h. u ist der linke Eigenvektor von P entsprechend λ. Lassen Sie auch x eine willkürliche Länge n Zeilenvektor in der Spanne der Eigenvektoren u sein, der ist

:

für einen Satz eines . Wenn wir anfangen, P mit x vom linken zu multiplizieren, und diese Operation mit den Ergebnissen fortsetzen, schließlich bekommen wir den stationären Vertrieb π. Mit anderen Worten π = u  xPPP... P = xP weil geht k zur Unendlichkeit. Das bedeutet

::

seit UU = ich sind die Identitätsmatrix und Macht einer Diagonalmatrix auch eine Diagonalmatrix, wo jeder Zugang in diese Macht gebracht wird.

::

da die Eigenvektoren orthonormal sind. Dann

:

Seitdem π = u π Annäherungen an π weil geht k zur Unendlichkeit mit einer Geschwindigkeit bei der Ordnung von λ/λ exponential. Das folgt, weil | λ  |λ ...  | λ folglich λ/λ der dominierende Begriff ist.

Umkehrbare Kette von Markov

Wie man

sagt, ist eine Kette von Markov umkehrbar, wenn es einen Wahrscheinlichkeitsvertrieb über Staaten, π, solch dass gibt

:

seit allen Zeiten n und allen Staaten i und j.

Diese Bedingung ist, auch bekannt als die ausführliche Gleichgewicht-Bedingung (verweisen einige Bücher die lokale Gleichgewicht-Gleichung).

Mit einer zeithomogenen Kette von Markov ändert sich Pr (X = j | X = i) mit der Zeit n nicht, und es kann einfacher als geschrieben werden. In diesem Fall kann die ausführliche Gleichgewicht-Gleichung kompakter als geschrieben werden

:Wenn ich

die ursprüngliche Gleichung darüber summiere, gebe mich

:

so, für umkehrbare Ketten von Markov, ist π immer ein Steady-Statevertrieb von Pr (X = j | X = i) für jeden n.

Wenn die Kette von Markov im Steady-Statevertrieb beginnt, d. h. wenn Pr (X = i) = π, dann kann Pr (X = i) = π für den ganzen n und die ausführliche Gleichgewicht-Gleichung als geschrieben werden

:

Die nach links und Rechten dieser letzten Gleichung sind abgesehen von einem Umkehren der Zeitindizes n und n + 1 identisch.

Umkehrbare Ketten von Markov sind in der Kette von Markov Monte Carlo (MCMC) Annäherungen üblich, weil die ausführliche Gleichgewicht-Gleichung für einen gewünschten Vertrieb π notwendigerweise andeutet, dass die Kette von Markov gebaut worden ist, so dass π ein Steady-Statevertrieb ist. Sogar mit dem Zeit-Inhomogeneous Ketten von Markov, wo vielfacher Übergang matrices verwendet werden, wenn jede solche Übergang-Matrix ausführlich berichtetes Gleichgewicht mit dem gewünschten π Vertrieb ausstellt, deutet das notwendigerweise an, dass π ein Steady-Statevertrieb der Kette von Markov ist.

Schema von Bernoulli

Ein Schema von Bernoulli ist ein spezieller Fall einer Kette von Markov, wo die Übergangswahrscheinlichkeitsmatrix identische Reihen hat, was bedeutet, dass der folgende Staat sogar des aktuellen Staates (zusätzlich dazu unabhängig ist, unabhängig der vorigen Staaten zu sein). Ein Schema von Bernoulli mit nur zwei möglichen Staaten ist als ein Prozess von Bernoulli bekannt.

Allgemeiner Zustandraum

Viele Ergebnisse für Ketten von Markov mit dem Zustandsraum können zu Ketten mit dem unzählbaren Zustandraum durch Ketten von Harris verallgemeinert werden. Die Hauptidee ist zu sehen, ob es einen Punkt im Zustandraum gibt, dass die Kette mit der Wahrscheinlichkeit ein schlägt. Allgemein ist es für den dauernden Zustandraum jedoch nicht wahr, wir können Sätze A und B zusammen mit einer positiven Zahl ε und eine Wahrscheinlichkeit definieren

messen Sie ρ, solch dass

Dann konnten wir die Sätze in einen Hilfspunkt α ohnmächtig werden, und eine wiederkehrende Kette von Harris kann modifiziert werden, um α zu enthalten. Letzt ist die Sammlung von Ketten von Harris ein bequemes Niveau der Allgemeinheit, die breit genug ist, um eine Vielzahl von interessanten Beispielen, noch einschränkend genug zu enthalten, um eine reiche Theorie zu berücksichtigen.

Anwendungen

Ketten von Markov werden auf viele verschiedene Felder angewandt. Forschung ist seine Anwendung in einer breiten Reihe von Themen im Intervall von der Physik, Chemie, Medizin zur Musik, der Spieltheorie und den Sportarten berichtet worden.

Physik

Systeme von Markovian erscheinen umfassend in der Thermodynamik und statistischen Mechanik, wann auch immer Wahrscheinlichkeiten verwendet werden, um unbekannte oder unmodellierte Details des Systems zu vertreten, wenn es angenommen werden kann, dass die Triebkräfte Zeit-Invariant sind, und dass keine relevante Geschichte betrachtet werden muss, der in die Zustandbeschreibung nicht bereits eingeschlossen wird.

Chemie

Chemie ist häufig ein Platz, wo Ketten von Markov und dauernd-malige Prozesse von Markov besonders nützlich sind, weil diese einfachen physischen Systeme dazu neigen, das Eigentum von Markov ganz gut zu befriedigen. Das klassische Modell der Enzym-Tätigkeit, Michaelis-Menten Kinetik, kann als eine Kette von Markov angesehen werden, wohin jedes Mal der Reaktionserlös in einer Richtung gehen. Während Michaelis-Menten ziemlich aufrichtig ist, viel mehr komplizierte Reaktionsnetze auch mit Ketten von Markov modelliert werden können.

Ein auf einer Kette von Markov gestützter Algorithmus wurde auch verwendet, um das Bruchstück-basierte Wachstum von Chemikalien in silico zu einer gewünschten Klasse von Zusammensetzungen wie Rauschgifte oder natürliche Produkte einzustellen. Da ein Molekül angebaut wird, wird ein Bruchstück vom werdenden Molekül als der "aktuelle" Staat ausgewählt. Es ist seiner Vergangenheit nicht bewusst (d. h. es ist dessen nicht bewusst, was bereits dazu verpfändet wird). Es wechselt dann zum folgenden Staat, wenn ein Bruchstück ihm beigefügt wird. Die Übergangswahrscheinlichkeiten werden auf Datenbanken von authentischen Klassen von Zusammensetzungen erzogen.

Außerdem kann das Wachstum (und Zusammensetzung) Copolymerisate mit Ketten von Markov modelliert werden. Gestützt auf den Reaktionsfähigkeitsverhältnissen der monomers, die die wachsende Polymer-Kette zusammensetzen, kann die Zusammensetzung der Kette berechnet werden (z.B, ob monomers dazu neigen, auf die Wechselmode oder auf lange Läufe desselben monomer beizutragen). Wegen steric Effekten zweite Ordnung können Effekten von Markov auch eine Rolle im Wachstum von einigen Polymer-Ketten spielen.

Ähnlich ist es darauf hingewiesen worden, dass die Kristallisierung und das Wachstum von einigen epitaxialen Supergitter-Oxydmaterialien durch Ketten von Markov genau beschrieben werden können.

Prüfung

Mehrere Theoretiker haben die Idee von der Kette von Markov Statistischen Test (MCST), eine Methode vorgeschlagen, Ketten von Markov zu vereinigen, um eine "Decke von Markov" zu bilden, diese Ketten in mehreren rekursiven Schichten ("wafering") einordnend und effizientere Testsätze — Proben — als ein Ersatz für die erschöpfende Prüfung erzeugend. MCSTs haben auch Nutzen in zeitlichen Zustandnetzen; das Papier von Chilukuri et al. betitelt "Zeitliche Unklarheitsdenken-Netze für die Beweis-Fusion mit Anwendungen, um Entdeckung und das Verfolgen" (ScienceDirect) Einzuwenden, gibt einen Hintergrund und Fallstudie, um MCSTs auf eine breitere Reihe von Anwendungen anzuwenden.

Informationswissenschaften

Ketten von Markov werden während der Informationsverarbeitung verwendet. Das berühmte 1948-Papier von Claude Shannon Eine mathematische Theorie der Kommunikation, die in einem Einzelschritt das Feld der Informationstheorie geschaffen hat, öffnet sich durch das Einführen des Konzepts des Wärmegewichtes durch das Modellieren von Markov der englischen Sprache. Solche idealisierten Modelle können viele von der statistischen Regelmäßigkeit von Systemen gewinnen. Sogar ohne die volle Struktur des Systems vollkommen zu beschreiben, können solche Signalmodelle mögliche sehr wirksame Datenkompression durch Wärmegewicht-Verschlüsselungstechniken wie das arithmetische Codieren machen. Sie erlauben auch wirksame Zustandbewertung und Muster-Anerkennung.

Ketten von Markov sind auch die Basis für Verborgene Modelle von Markov, die ein wichtiges Werkzeug in solchen verschiedenen Feldern als Telefonnetze (für die Fehlerkorrektur), Spracherkennung und bioinformatics sind.

Die Handy-Systeme in der Welt hängen vom Algorithmus von Viterbi für die Fehlerkorrektur ab, während verborgene Modelle von Markov in der Spracherkennung und auch in bioinformatics zum Beispiel umfassend verwendet werden, um Vorhersage des Gebiets/Gens zu codieren. Ketten von Markov spielen auch eine wichtige Rolle im Verstärkungslernen.

Theorie von Queueing

Ketten von Markov sind die Basis für die analytische Behandlung von Warteschlangen (queueing Theorie). Das macht sie kritisch, für die Leistung von Fernmeldenetzen zu optimieren, wo sich Nachrichten häufig um beschränkte Mittel (wie Bandbreite) bewerben müssen.

Internetanwendungen

PageRank eines webpage, wie verwendet, durch Google wird durch eine Kette von Markov definiert. Es ist die Wahrscheinlichkeit, um an der Seite im stationären Vertrieb auf der folgenden Kette von Markov auf allen (bekannter) webpages zu sein. Wenn die Zahl bekannten webpages ist, und eine Seite Verbindungen dazu dann hat, hat es Übergangswahrscheinlichkeit für alle Seiten, die mit und für alle Seiten verbunden werden, die damit nicht verbunden werden. Der Parameter wird genommen, um ungefähr 0.85 zu sein.

Modelle von Markov sind auch verwendet worden, um Webnavigationsverhalten von Benutzern zu analysieren. Ein Webverbindungsübergang eines Benutzers auf einer besonderen Website kann mit zuerst - oder zweite Ordnung Modelle von Markov modelliert werden und kann verwendet werden, um Vorhersagen bezüglich der zukünftigen Navigation zu machen und die Webseite für einen individuellen Benutzer zu personifizieren.

Statistik

Kettenmethoden von Markov sind auch sehr wichtig geworden, um Folgen von Zufallszahlen zu erzeugen, um sehr komplizierten gewünschten Wahrscheinlichkeitsvertrieb, über einen Prozess genannt die Kette von Markov Monte Carlo (MCMC) genau zu widerspiegeln. In den letzten Jahren hat das die Durchführbarkeit von Interferenzmethoden von Bayesian revolutioniert, einer breiten Reihe des späteren Vertriebs erlaubend, vorgetäuscht zu werden, und ihre Rahmen numerisch gefunden.

Volkswirtschaft und Finanz

Ketten von Markov werden in der Finanz und Volkswirtschaft verwendet, um eine Vielfalt von verschiedenen Phänomenen, einschließlich Anlagenpreise und Marktunfälle zu modellieren. Das erste Finanzmodell, um eine Kette von Markov zu verwenden, war von Prasad u. a. 1974. Ein anderer war das regimeschaltende Modell von James D. Hamilton (1989), in dem eine Kette von Markov an Musterschalter zwischen Perioden der hohen Flüchtigkeit und niedrigen Flüchtigkeit des Anlagenumsatzes gewöhnt ist. Ein neueres Beispiel ist der Markov, der Multifractal Anlagenpreiskalkulationsmodell Schaltet, das auf die Bequemlichkeit von früheren regimeschaltenden Modellen baut. Es verwendet eine willkürlich große Kette von Markov, um das Niveau der Flüchtigkeit des Anlagenumsatzes zu steuern.

Dynamische Makrovolkswirtschaft verwendet schwer Ketten von Markov. Ein Beispiel verwendet Ketten von Markov an exogenously Musterpreisen der Billigkeit (Lager) in einer allgemeinen Gleichgewicht-Einstellung.

Das Eingangsproduktionsmodell von Leontief ist eine Kette von Markov.

Sozialwissenschaften

Ketten von Markov werden allgemein im Beschreiben vom Pfad abhängiger Argumente, wo aktuelle Strukturkonfigurationsbedingungszukunft-Ergebnisse verwendet. Ein Beispiel ist die allgemein diskutierte Verbindung zwischen der Wirtschaftsentwicklung und dem Anstieg des Kapitalismus. Sobald ein Land ein spezifisches Niveau der Wirtschaftsentwicklung, die Konfiguration von Strukturfaktoren, wie Größe des kommerziellen Bürgertums, das Verhältnis von städtischen zum ländlichen Wohnsitz erreicht, wird die Rate der politischen Mobilmachung usw. eine höhere Wahrscheinlichkeit des Wechselns vom autoritären bis Kapitalisten erzeugen.

Mathematische Biologie

Ketten von Markov haben auch viele Anwendungen im biologischen Modellieren, besonders den Bevölkerungsprozessen, die im Modellieren von Prozessen nützlich sind, die (mindestens) biologischen Bevölkerungen analog sind. Die Matrix von Leslie ist ein solches Beispiel, obwohl einige seiner Einträge

sind nicht Wahrscheinlichkeiten (sie können größer sein als 1). Ein anderes Beispiel ist das Modellieren der Zellgestalt in sich teilenden Platten von epithelischen Zellen. Und doch ist ein anderes Beispiel der Staat von Kanälen von Ion in Zellmembranen.

Ketten von Markov werden auch in Simulationen der Gehirnfunktion wie die Simulation des Säugetierneocortex verwendet.

Spiele

Ketten von Markov können verwendet werden, um viele Glücksspiele zu modellieren. Die Spielschlangen und Leitern der Kinder und "Hallo Ho! Cherry-O", zum Beispiel, wird genau durch Ketten von Markov vertreten. An jeder Umdrehung, den Spieler-Anfängen in einem gegebenen Staat (auf einem gegebenen Quadrat) und hat von dort Verschiedenheit des Bewegens zu bestimmten anderen Staaten (Quadrate) befestigt.

Musik

Ketten von Markov werden in der algorithmischen Musik-Zusammensetzung, besonders in Softwareprogrammen wie CSound, Max oder SuperCollider verwendet. In einer Kette der ersten Ordnung werden die Staaten des Systems Zeichen oder Wurf-Werte, und ein Wahrscheinlichkeitsvektor für jedes Zeichen wird gebaut, eine Übergangswahrscheinlichkeitsmatrix (sieh unten) vollendend. Ein Algorithmus wird gebaut, um zu erzeugen, und Produktionszeichen-Werte, die auf der Übergang-Matrix weightings gestützt sind, der MIDI-Zeichen-Werte, Frequenz (Hz) oder irgendwelcher anderes wünschenswertes metrisches sein konnte.

Eine zweite Ordnung Kette von Markov kann durch das Betrachten des aktuellen Staates und auch des vorherigen Staates, wie angezeigt, im zweiten Tisch eingeführt werden. Höher neigen Ketten der n-ten Ordnung dazu, besondere Zeichen zusammen "zu gruppieren", während sie in andere Muster und Folgen gelegentlich 'abbrechen'. Diese höherwertigen Ketten neigen dazu, Ergebnisse mit einem Sinn der phrasal Struktur, aber nicht das 'ziellose Wandern zu erzeugen, das' durch ein System der ersten Ordnung erzeugt ist.

Ketten von Markov können strukturell, als im Analogique von Xenakis A und B, wie beschrieben, in seinem Buch 'Formalisierte Musik verwendet werden: Mathematik und Gedacht in der Zusammensetzung'.

Ketten von Markov werden auch in Systemen wie Continuator und der Virtuose verwendet, die ein Modell von Markov verwenden, um interaktiv auf den Musik-Eingang zu reagieren.

Es sollte bemerkt werden, dass gewöhnlich musikalische Systeme Specic-Kontrolleinschränkungen auf die Nite-Länge-Folgen geltend machen müssen, die sie erzeugen, aber Einschränkungen kontrollieren, sind mit Modellen von Markov nicht vereinbar, da sie Langstreckenabhängigkeiten veranlassen, die die Hypothese von Markov des beschränkten Gedächtnisses verletzen. Um diese Beschränkung zu überwinden, ist eine neue Annäherung von Pachet und Roy vorgeschlagen worden.

Baseball

Kettenmodelle von Markov sind in der fortgeschrittenen Baseball-Analyse seit 1960 verwendet worden, obwohl ihr Gebrauch noch selten ist. Jedes Halbinning eines Baseball-Spiels passt den Kettenstaat von Markov, wenn die Zahl von Läufern und outs betrachtet wird. Während etwas an der Fledermaus gibt es 24 mögliche Kombinationen der Zahl von outs und Position der Läufer. Mark Pankin zeigt, dass Kettenmodelle von Markov verwendet werden können, um Läufe zu bewerten, die für beide individuellen Spieler sowie eine Mannschaft geschaffen sind.

Er bespricht auch verschiedene Arten von Strategien und Spiel-Bedingungen: Wie Kettenmodelle von Markov verwendet worden sind, um Statistik für Spielsituationen wie Flaggen und das Grunddiebstahl und die Unterschiede zu analysieren, wenn man auf dem Gras gegen astroturf spielt.

Textgeneratoren von Markov

Prozesse von Markov können auch verwendet werden, um oberflächlich "echt aussehenden" Text gegeben ein Beispieldokument zu erzeugen: Sie werden in einer Vielfalt der" Generators Parodie "Erholungssoftware verwendet (sieh abgesonderte Presse, Jeff Harrison http://www.fieralingue.it/modules.php?name=Content&pa=list_pages_categories&cid=111, V Zeichen Shaney

).

Diese Prozesse werden auch durch spammers verwendet, um echt aussehende verborgene Paragrafen in die freiwillige E-Mail in einem Versuch einzuspritzen, diese Nachrichten vorbei spam Filter zu bekommen.

Anprobe

Wenn

sie eine Kette von Markov an Daten passen, können Situationen, wo Rahmen schlecht die Situation beschreiben, interessante Tendenzen hervorheben.

Geschichte

Andrey Markov hat die ersten Ergebnisse (1906) für diese Prozesse rein theoretisch erzeugt.

Eine Generalisation zu zählbar unendlichen Zustandräumen wurde von Kolmogorov (1936) gegeben.

Ketten von Markov sind mit der Brownschen Bewegung und der ergodic Hypothese, den zwei Themen in der Physik verbunden, die in den frühen Jahren des zwanzigsten Jahrhunderts wichtig waren, aber Markov scheint, das aus einer mathematischen Motivation, nämlich die Erweiterung des Gesetzes der großen Anzahl zu abhängigen Ereignissen verfolgt zu haben. 1913 hat er seine Ergebnisse zum ersten Mal auf die ersten 20,000 Briefe von Eugene Onegin von Pushkin angewandt.

Seneta stellt eine Rechnung der Motivationen von Markov und der frühen Entwicklung der Theorie zur Verfügung. Der Begriff "Kette" wurde von Markov (1906) gebraucht.

Siehe auch

• Verborgenes Modell von Markov
• Kette von Telescoping Markov
• Kettenmischen-Zeit von Markov
• Kette von Markov geostatistics
• Quant Kette von Markov
• Prozess von Markov
• Informationsquelle von Markov
• Kette von Markov Monte Carlo
• Netz von Markov
• Decke von Markov
• Prozess von Semi-Markov
• Variable Ordnung Modell von Markov
• Entscheidung von Markov bearbeitet

Referenzen

• A.A. Markov. "Rasprostranenie zakona bol'shih Meißel na velichiny, zavisyaschie Rauschgift ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, Seiten 135-156, 1906.
• A.A. Markov. "Die Erweiterung der Grenzwertsätze der Wahrscheinlichkeitstheorie zu einer Summe von Variablen hat in einer Kette in Verbindung gestanden". nachgedruckt im Anhang B:R. Howard. Dynamische Probabilistic Systeme, Band 1: Ketten von Markov. John Wiley and Sons, 1971.
• Klassischer Text in der Übersetzung:A. A. Markov, Ein Beispiel der Statistischen Untersuchung des Textes Eugene Onegin Bezüglich der Verbindung von Proben in Ketten, trans. Verbindung von David. Wissenschaft im Zusammenhang 19.4 (2006): 591-600. Online:

http://journals.cambridge.org/production/action/cjoGetFulltext?fulltextid=637500

• Leo Breiman. Wahrscheinlichkeit. Ursprüngliche Ausgabe, die von Addison-Wesley, 1968 veröffentlicht ist; nachgedruckt von der Gesellschaft für die Industrielle und Angewandte Mathematik, 1992. Internationale Standardbuchnummer 0-89871-296-3. (Sieh Kapitel 7.)
• J.L. Doob. Stochastische Prozesse. New York: John Wiley and Sons, 1953. Internationale Standardbuchnummer 0-471-52369-0.
• S. P. Meyn und R. L. Tweedie. Ketten von Markov und Stochastische Stabilität. London: Springer-Verlag, 1993. Internationale Standardbuchnummer 0-387-19832-6. online: https://netfiles.uiuc.edu/meyn/www/spm_files/book.html. Die zweite Ausgabe, um, Universität von Cambridge Presse, 2009 zu erscheinen.
• S. P. Meyn. Kontrolltechniken für Komplizierte Netze. Universität von Cambridge Presse, 2007. Internationale Standardbuchnummer 978-0-521-88441-9. Anhang enthält hat Meyn & Tweedie gekürzt. online:

https://netfiles.uiuc.edu/meyn/www/spm_files/CTCN/CTCN.html

• Umfassendes, weiträumiges Buch, das für Fachmänner beabsichtigt ist, die für beide theoretischen Computerwissenschaftler sowie Elektroingenieure geschrieben sind. Mit ausführlichen Erklärungen von Zustandminimierungstechniken, FSMs, Maschinen von Turing, Prozessen von Markov und Unentscheidbarkeit. Die ausgezeichnete Behandlung von Markov bearbeitet Seiten 449ff. Bespricht Z-Transforms, D verwandelt sich in ihrem Zusammenhang.

• Klassischer Text. vgl Kapitel 6 Begrenzte Kettenseiten von Markov 384ff.
• E. Nummelin. "Allgemeine nicht zu vereinfachende Ketten von Markov und nichtnegative Maschinenbediener". Universität von Cambridge Presse, 1984, 2004. Internationale Standardbuchnummer 0 521 60494 X
• Seneta, E. Nichtnegativer matrices und Ketten von Markov. Die 2. Umdrehung. Hrsg., 1981, XVI, 288 p. Softcover Springer Series in der Statistik. (Ursprünglich veröffentlicht von Allen & Unwin Ltd., London, 1973) internationale Standardbuchnummer 978-0-387-29765-1
• Kishor S. Trivedi, Wahrscheinlichkeit und Statistik mit der Zuverlässigkeit, Queueing und den Informatik-Anwendungen, John Wiley & Sons, Inc New York, 2002. Internationale Standardbuchnummer 0-471-33341-7.
• K.S.Trivedi und R.A.Sahner, SHARPE im Alter von zweiundzwanzig Jahren, vol. 36, Nr. 4, pp.-52-57, ACM SIGMETRICS Leistungseinschätzungsrezension, 2009.
• R.A.Sahner, K.S.Trivedi und A. Puliafito, Leistung und Zuverlässigkeitsanalyse von Computersystemen: eine Beispiel-basierte Annäherung mit dem SHARPE Softwarepaket, Kluwer Akademische Herausgeber, 1996. Internationale Standardbuchnummer 0-7923-9650-2.
• G.Bolch, S.Greiner, H.de Meer und K.S.Trivedi, Queueing Networks und Ketten von Markov, John Wiley, 2. Ausgabe, 2006. Internationale Standardbuchnummer 978-0-7923-9650-5.

Links

• Techniken, um Computersimulationen zu verstehen: Kettenanalyse von Markov
• Kettenkapitel von Markov im einleitenden Wahrscheinlichkeitsbuch der amerikanischen Mathematischen Gesellschaft (pdf)
• Ketten von Markov
• Kapitel 5: Kettenmodelle von Markov
• JavaScript Markovian Textkompressor (in Portugiesisch).
• Anwendung auf Ketten von Markov
• Das Erzeugen von Text:Section 15.3, Perlen Zu programmieren
• Das Erzeugen des Textes Online: Markov Zufälliger Spaziergang v1.1
• eine Liste von Mitteln hat sich auf Ketten von Markov bezogen