imported>Leonry am 26. April 2026 um 20:04 Uhr

2026-04-26T20:04:28Z

Neue Seite

{{Überarbeiten|Grund=Der Artikel stellt irreführende Behauptungen auf (z.B. Markow-Kette und -Prozess seien synonym gebraucht (EDIT:teilweise gelöst)), gibt keine Einzelnachweise an und stellt insgesamt Markow-Ketten sehr eingeschränkt dar. --[[Benutzer:Leonry|Leon]] ([[Benutzer Diskussion:Leonry|Diskussion]]) 12:43, 19. Apr. 2026 (CEST)}}

Eine '''Markow-Kette''' ({{enS|Markov chain}}; nach [[Andrei Andrejewitsch Markow (Mathematiker, 1856)|Andrei Andrejewitsch Markow]]; andere Schreibweisen ''Markov-Kette'', ''Markoff-Kette'', ''Markof-Kette'') ist ein [[stochastischer Prozess]]. Ziel bei der Anwendung von Markow-Ketten ist es, Wahrscheinlichkeiten für das Eintreten nachfolgender Ereignisse anzugeben. Eine Markow-Kette ist darüber definiert, dass durch Kenntnis einer nur begrenzten Vorgeschichte ebenso gute Prognosen über die zukünftige Entwicklung möglich sind wie bei Kenntnis der gesamten Vorgeschichte des Prozesses. Diese sogenannte [[Markow-Eigenschaft]] (Gedächtnislosigkeit) erlaubte erstmals die mathematisch präzise Modellierung vieler realer Prozesse, etwa in Physik, Informatik, Biologie oder Finanzwesen. Dabei verbindet die Theorie Konzepte der Wahrscheinlichkeit mit Methoden der linearen Algebra, was weitreichende Analysemöglichkeiten eröffnet, etwa zur Bestimmung stationärer Verteilungen.

== Einführende Beispiele ==
Markow-Ketten eignen sich sehr gut, um zufällige Zustandsänderungen eines Systems zu modellieren, falls man Grund zu der Annahme hat, dass die Zustandsänderungen nur über einen begrenzten Zeitraum hinweg Einfluss aufeinander haben oder sogar [[Gedächtnislosigkeit|gedächtnislos]] sind. Ein Beispiel sind Auslastungen von [[Wartesystem|Bediensystemen]] mit gedächtnislosen Ankunfts- und Bedienzeiten.

=== Diskrete, endliche Markow-Kette ===
Ein populäres Beispiel für eine zeitdiskrete Markow-Kette mit endlichem Zustandsraum ist die [[Zufallsbewegung|zufällige Irrfahrt]] auf einem diskreten Kreis, modelliert durch den [[Restklassenring]] <math>\mathbb Z/n\mathbb Z</math>. Der Zustandsraum ist durch <math>S = \left\{ 0,1,2, \dots ,(n-1) \right\} </math> gegeben. Ausgangspunkt ist die [[Äquivalenzklasse]] <math> [0] </math>, wobei der Prozess in jedem Schritt aus dem aktuellen Zustand <math> [i] </math> mit Wahrscheinlichkeit <math> 1/2 </math> entweder in den Zustand <math> [i+1] </math> oder <math> [i-1] </math> übergeht. Die Addition und Subtraktion erfolgt dabei modulo <math> n </math>, wodurch die zyklische Struktur des Zustandsraums gewährleistet ist. Dieser stochastische Prozess erfüllt die Markow-Eigenschaft, da der nächste Zustand ausschließlich vom aktuellen Zustand <math> [i] </math> abhängt und nicht von den vorherigen Zuständen.

=== Diskrete, unendliche Markow-Kette ===
Als Beispiel für einen abzählbar unendlichen Zustandsraum wirft man eine Münze immer wieder und notiert bei jedem Wurf, wie oft bislang ‚Kopf‘ erschienen ist. Die Abfolge der so gebildeten Zahlen bildet eine (zeitdiskrete) Markow-Kette, diesmal mit Zustandsraum <math>S = \{0,1,2, \dots \}</math> mit jeweils der [[Übergangswahrscheinlichkeit]] <math> 1/2 </math> für den Übergang von <math> [i] </math> nach <math> [i+1] </math> und für das Verbleiben in <math> [i] </math>.

Ein weiteres Beispiel für eine Markow-Kette mit unendlichem Zustandsraum ist der [[Galton-Watson-Prozess]], der oftmals zur Modellierung von Populationen genutzt wird.

== Definition ==
=== Diskrete Zeit und höchstens abzählbar unendliche Zustandsmenge ===
Gegeben sei eine Familie von Zufallsvariablen <math> Y=(X_t)_{t \in \mathbb{N}} </math>, wobei alle <math>X_t</math> nur Werte aus dem [[Abzählbare Menge|höchstens abzählbaren]] Zustandsraum <math> S=\{s_1,s_2,s_3, \dots\} </math> annehmen. Dann heißt <math> Y </math> eine (diskrete) Markow-Kette genau dann, wenn
:<math>\begin{align}
&\ P(X_{t+1}=s_{j_{t+1}}\mid X_t=s_{j_t}, X_{t-1}=s_{j_{t-1}},\dots,X_0=s_{j_0})\\
=&\ P(X_{t+1}=s_{j_{t+1}}\mid X_t=s_{j_{t}}).
\end{align}</math>
gilt. Die [[Übergangswahrscheinlichkeit]]en hängen also nur von dem aktuellen Zustand ab und nicht von der gesamten Vergangenheit. Dies bezeichnet man als ''Markow-Eigenschaft'' oder auch als [[Gedächtnislosigkeit]].
Seien
:<math>p_{ij}(t):=P(X_{t+1}=s_j \mid X_t=s_i),\quad i,j=1,\dots,m</math>
die Übergangswahrscheinlichkeiten. Diese lassen sich dann in eine quadratische [[Übergangsmatrix]] zusammenfassen:
:<math>\mathbf{M}(t)= (p_{ij}(t))_{s_i,s_j \in S}</math>

Sind die Übergangswahrscheinlichkeiten unabhängig vom Zeitpunkt <math>t</math>, gilt also <math> p_{ij}(t)=p_{ij} </math> für alle <math> t </math>, so heißt die Markow-Kette '''homogen''' oder Kette mit '''stationären Übergangswahrscheinlichkeiten'''. Bei Homogenität einer Kette definiert man <math> p_{ij}^n=P(X_{n}=s_j \mid X_0=s_i) </math> als die <math>n</math>-Schritt-Übergangswahrscheinlichkeit.

==== Markow-Kette ''n''-ter Ordnung ====
Gelegentlich werden auch Markow-Ketten <math>n</math>-ter Ordnung untersucht. Bei diesen hängt der zukünftige Zustand von den <math>n</math> vorherigen Zuständen ab:
:<math>\begin{align}
&\ P(X_{t+1}=s_{j_{t+1}}\mid X_t=s_{j_t}, X_{t-1}=s_{j_{t-1}},\dots,X_0=s_{j_0})\\
=&\ P(X_{t+1}=s_{j_{t+1}}\mid X_t=s_{j_t},\dots,X_{t-n+1}=s_{j_{t-n+1}}).
\end{align}</math>
In diesem Sinn sind die oben betrachteten Markow-Ketten Ketten erster Ordnung. Ketten höherer Ordnung werden hier aber nicht weiter betrachtet.

=== Diskrete Zeit und allgemeiner Zustandsraum ===
Markow-Ketten können auch auf allgemeinen messbaren Zustandsräumen definiert werden. Ist der Zustandsraum nicht abzählbar, so benötigt man hierzu den [[Stochastischer Kern|stochastischen Kern]] als Verallgemeinerung zur Übergangsmatrix. Dabei ist eine Markow-Kette durch die Startverteilung auf dem Zustandsraum und den stochastischen Kern schon eindeutig bestimmt. Auf dem Gebiet der Markow-Ketten gibt es noch viele offene Probleme. Gut erforscht sind lediglich [[Harris-Kette]]n.

== Anmerkungen ==
* Die Verteilung von <math> X_0 </math> wird manchmal auch als Startverteilung oder Anfangsverteilung bezeichnet. Bei Vorgabe einer Startverteilung sind alle weiteren Verteilungen <math> X_t </math> eindeutig bestimmt. Daher hat sich teilweise die verkürzte Notation eingebürgert, nur die Startverteilung <math> \alpha </math> und den Zeitschritt von Interesse anzugeben:
::<math> P^\alpha(X_t=i):=P(X_t=i|X_0 \ \text{ hat Verteilung } \ \alpha) </math>
: Startet man in einem eindeutigen Zustand <math> j </math>, so wird meist <math> P^j(X_t=i) </math> geschrieben.
* Bei einem endlichen Zustandsraum lassen sich Markow-Ketten mittels der Übergangsmatrix und von Wahrscheinlichkeitsvektoren beschreiben. Wählt man einen stochastischen Startvektor <math> v_0 </math> (als Zeilenvektor) als Startverteilung, so ergibt sich die Verteilung zum Zeitpunkt 1 durch <math> v_1=v_0M </math>. Damit folgt induktiv <math> v_n=v_0M^n </math>. Dabei ist dann genau der <math>i</math>-te Eintrag von <math> v_n </math> die Wahrscheinlichkeit zum Zeitpunkt <math>n</math> im Zustand <math>i</math> zu sein, wenn mit der Startverteilung <math> v_0 </math> gestartet wurde. Demgemäß lassen sich im Falle der Homogenität und der Endlichkeit des Zustandsraumes leicht die <math>n</math>-Schritt-Übergangswahrscheinlichkeiten berechnen. Diese sind dann genau
::<math> p_{ij}^n=\left[ M^n\right]_{i,j} </math>,
: also der Eintrag, der in der <math>i</math>-ten Zeile und der <math>j</math>-ten Spalte der <math>n</math>-ten Potenz der Übergangsmatrix steht.
* Allgemein gilt die [[Chapman-Kolmogorow-Gleichung]]. Im Falle eines endlichen Zustandsraumes ist sie genau das komponentenweise Ausschreiben der Matrixmultiplikation.
* Markow-Ketten sind diskrete [[Dynamisches System|dynamische Systeme]] mit Zeitraum <math> \mathbb{N} </math>, der Indexmenge. Den Zustandsraum im Sinne des dynamischen Systems bilden dann alle Verteilungen auf dem Zustandsraum im Sinne der Markow-Kette. Die Operation <math> \Phi </math> ordnet dann der Verteilung im <math>t</math>-ten Zeitschritt die Verteilung im <math>(t+1)</math>-ten Zeitschritt zu. Im Falle eines endlichen Zustandsraumes der Markow-Kette ist dies dann genau die iterierte Anwendung der Übergangsmatrix wie oben beschrieben. Einige Begriffe aus der Theorie der dynamischen Systeme haben ein Pendant in der Theorie der Markow-Ketten wie z. B. [[Kritischer Punkt (Dynamik)|kritische Punkte]] und stationäre Verteilungen.
* Die oben definierte Übergangsmatrix ist [[Matrix (Mathematik)#Unendlichdimensionale Räume|unendlichdimensional]], wenn der Zustandsraum abzählbar unendlich ist. Nur im Falle der Endlichkeit des Zustandsraumes handelt es sich um eine Matrix im Sinne der [[Lineare Algebra|Linearen Algebra]].

== Beispiele ==
=== Endlicher Zustandsraum ===
[[Datei:Elementarymarkow.png|mini|Übergangsgraph für die beschriebene Markow-Kette]]

Wir versuchen, mithilfe einer Markow-Kette eine einfache Wettervorhersage zu bilden. Dazu kodieren wir 1 = „die Sonne scheint“, 2 = „es ist bewölkt“ und 3 = „es regnet“. Als Zeitschritt wählen wir einen Tag. Aus Erfahrung wissen wir, dass wenn heute die Sonne scheint, die Wahrscheinlichkeit, dass es morgen regnet, ungefähr 80 % ist und die Wahrscheinlichkeit, dass es bewölkt ist, ca. 20 % beträgt. Außerdem treffen wir die Annahme, dass sich diese Wahrscheinlichkeiten nicht ändern, die Markow-Kette also homogen ist. Somit wissen wir nun
:<math> P(X_{t+1}=i|X_t=1)=
\begin{cases}
0 & \text{ falls }\quad i=1 \\
0{,}2 & \text{ falls }\quad i=2, \\
0{,}8 & \text{ falls }\quad i=3
\end{cases}
</math>
Ist es aber bewölkt, so regnet es mit Wahrscheinlichkeit 0,5 am folgenden Tag und mit Wahrscheinlichkeit von 0,5 scheint die Sonne. Es gilt also
:<math> P(X_{t+1}=i|X_t=2)=
\begin{cases}
0{,}5 & \text{ falls }\quad i=1 \\
0 & \text{ falls }\quad i=2, \\
0{,}5 & \text{ falls }\quad i=3
\end{cases}
</math>
Regnet es heute, so scheint danach nur mit Wahrscheinlichkeit von 0,1 die Sonne und mit Wahrscheinlichkeit von 0,9 ist es bewölkt. Damit folgt für die Übergangswahrscheinlichkeiten
:<math> P(X_{t+1}=i|X_t=3)=
\begin{cases}
0{,}1 & \text{ falls }\quad i=1 \\
0{,}9 & \text{ falls }\quad i=2, \\
0 & \text{ falls }\quad i=3
\end{cases}
</math>
Damit ist die Markow-Kette vollständig beschrieben. Anschaulich lassen sich solche Markow-Ketten gut durch [[Übergangsgraph]]en darstellen, wie oben abgebildet. Ordnet man nun die Übergangswahrscheinlichkeiten zu einer Übergangsmatrix an, so erhält man
:<math>M = \begin{bmatrix}
0 & 0{,}2 & 0{,}8 \\
0 {,}5 & 0 & 0{,}5 \\
0{,}1 & 0{,}9 & 0
\end{bmatrix}</math>

Wir wollen nun wissen, wie sich das Wetter entwickeln wird, wenn heute die Sonne scheint. Dazu geben wir die Anfangsverteilung <math> X_0 </math> vor in Form des stochastischen Startvektors <math> v_0=(1;0;0) </math>. Wir starten also im Zustand 1. Multiplikation von rechts mit der Übergangsmatrix liefert <math> v_1=v_0M=(0;0{,}2;0{,}8) </math>. Mit achtzigprozentiger Wahrscheinlichkeit regnet es also. Am dritten Tag gilt <math> v_3=v_0M^3\approx (0{,}3700; 0{,}1260; 0{,}5040) </math>. Somit ist die Regenwahrscheinlichkeit am dritten Tag knapp über 50 % und die Sonnenwahrscheinlichkeit knapp unter 40 %. Somit lässt sich für jedes vorgegebene Wetter am Starttag die Regen- und Sonnenwahrscheinlichkeit an einem beliebigen Tag angeben. Auch Fragestellungen wie: „Heute scheint die Sonne. Wie groß ist die Wahrscheinlichkeit, dass es vor drei Tagen geregnet hat?“ lassen sich mit dem [[Satz von Bayes]] beantworten.

=== Abzählbar unendlicher Zustandsraum ===
Definieren wir nun eine Markow-Kette auf dem Zustandsraum <math> \mathbb{Z} </math> und mit Übergangswahrscheinlichkeiten
:<math> P(X_{t+1}=i|X_t=j)=
\begin{cases}
p & \text{ falls }\quad i=j+1 \\
q & \text{ falls }\quad i=j-1, \\
0 & \text{sonst}
\end{cases}
</math>
wobei <math> p+q=1</math>, <math>p,q \geq 0 </math> gelten. Dies lässt sich so veranschaulichen: Startet man an einem beliebigen Punkt, so bewegt man sich entweder mit einer Wahrscheinlichkeit von <math> p </math> nach „rechts“, sprich, begibt sich zur Nachfolgerzahl. Mit Wahrscheinlichkeit <math> q </math> wandert man nach „links“ zur Vorgängerzahl. Entsprechend diesem Vorgehen irrt man dann über die Zahlengerade. Daher wird diese Markow-Kette auch ''Irrfahrt auf <math> \mathbb{Z} </math>'' genannt. Gelegentlich wird für solche Markow-Ketten auch der Begriff des [[Random Walk]] verwendet. Starten wir im Zustand 0, so ist mit den obigen Übergangswahrscheinlichkeiten
:<math> P^0(X_1=i)= \begin{cases}
p & \text{ falls }\quad i=1, \\
q & \text{ falls }\quad i=-1, \\
0 & \text{ sonst.}
\end{cases}
</math>
Daraus folgen dann <math> P^0(X_2=-2)=q^2</math>, <math>P^0(X_2=0)=2pq</math>, <math>P^0(X_2=2)=p^2 </math>. Hier zeigt sich ein gewisser Zusammenhang zur [[Binomialverteilung]]. Außerdem gilt aber auch <math> P^0(X_2=-1)=P^0(X_2=1)=0</math>. Gewisse Zustände können also nur zu bestimmten Zeiten besucht werden; diese Eigenschaft wird [[Periodische Markow-Kette|Periodizität]] genannt.

Ist allgemeiner <math>(Z_n)_{n \in \N}</math> eine Folge [[Unabhängig und identisch verteilt|unabhängiger und identisch verteilter]] Zufallsvariablen mit Werten in <math>\Z</math>, dann ist durch
:<math>X_t = \sum_{n=1}^t Z_n</math>
eine Markow-Kette <math>(X_t)_{t \in \N}</math> mit Übergangswahrscheinlichkeiten <math>p_{ij} = P(Z_1 = j-i)</math> gegeben.

=== Klassische Beispiele ===
Einige der bekanntesten Markow-Ketten sind
* Die [[Random Walk|Irrfahrt]] auf <math> \mathbb{Z}^D </math> sowie Verallgemeinerungen auf Graphen.
* Der [[Galton-Watson-Prozess]], welcher die Fortpflanzung einer sich eingeschlechtlich fortpflanzenden Spezies modelliert.
* Das [[Ehrenfest-Modell]] zur Modellierung der Diffusion von Molekülen durch Membrane.
* Das [[Wright-Fisher-Modell]] zur Modellierung der Genhäufigkeit in einer Population.<ref>{{Literatur |Autor=Nicole Bäuerle et al. |Titel=Ausbreitung von Gerüchten – mit Markov-Ketten modellieren |Sammelwerk=Stochastik in der Schule |Band=40 |Nummer=3 |Datum=2020 |Online=[https://www.stochastik-in-der-schule.de/sisonline/Jahrgang40-2020/Heft%203/Stochastik_3_2020_2_7.pdf Online] |Format=PDF |Abruf=2026-04-24 |Sprache=de}}</ref>

== Eigenschaften ==
Markow-Ketten können gewisse Eigenschaften zukommen, welche insbesondere das Langzeitverhalten beeinflussen. Dazu gehören beispielsweise die folgenden:

=== Irreduzibilität ===
{{Hauptartikel|Irreduzible Markow-Kette}}

Irreduzibilität ist wichtig für die Konvergenz gegen einen stationären Zustand. Vereinfacht gesagt ist eine Markow-Kette irreduzibel, wenn für alle Zustände <math> i </math> und <math> j </math> gilt, dass die Wahrscheinlichkeit, in endlicher Zeit von <math> i </math> nach <math> j </math> zu kommen, echt positiv ist. Gilt dies für fixierte <math> i </math> und <math> j </math>, so sagt man auch, dass <math> i </math> und <math> j </math> miteinander [[Kommunizierende Zustände|kommunizieren]].

=== Periodizität ===
{{Hauptartikel|Periodische Markow-Kette}}

Periodische Markow-Ketten erhalten trotz aller Zufälligkeit des Systems gewisse deterministische Strukturen. Ist eine Markow-Kette periodisch mit Periode <math> d </math>, so kann sie höchstens alle <math> d </math> Zeitschritte wieder zu ihrem Startpunkt zurückkehren (dies ist aber nicht zwingend).

=== Rekurrenz und Transienz ===
{{Hauptartikel|Rekurrente Markow-Kette}}

Die Rekurrenz und die Transienz beschreiben das Langzeitverhalten einer Markow-Kette. Wird ein Zustand fast sicher unendlich oft besucht, so heißt er rekurrent, ansonsten transient. Sind alle Zustände rekurrent (transient), so heißt die Markow-Kette rekurrent (transient). Wichtiges Hilfsmittel zur Bestimmung von Rekurrenz ist die [[Green-Funktion (Stochastik)|Green-Funktion]].

[[Datei:Drunkard’s walk.svg|mini|500px|Eine (endliche) zufällige Irrfahrt mit zwei absorbierenden Zuständen (ganz links und ganz rechts). Die Zustände „–1“, „0“ und „1“ haben jeweils die gleiche [[Übergangswahrscheinlichkeit]] (0,5) zu den Zuständen links und rechts von ihnen.]]
=== Absorbierende Zustände ===
{{Hauptartikel|Absorbierender Zustand}}

Absorbierende Zustände sind Zustände, welche nach dem Betreten nicht wieder verlassen werden können. Hier interessiert man sich insbesondere für die Absorptionswahrscheinlichkeit, also die Wahrscheinlichkeit, einen solchen Zustand zu betreten.

=== Stationäre Verteilungen ===
{{Hauptartikel|Stationäre Verteilung}}

In der Anwendung sind oftmals besonders stationäre Verteilungen interessant. Gibt man diese Verteilungen als Startverteilung von <math> X_0 </math> vor, so sind alle darauf folgenden Verteilungen der Zustände <math>X_n</math> für beliebiges <math> n </math> gleich der Startverteilung. Interessant ist hier die Frage, wann solche Verteilungen existieren und wann eine beliebige Verteilung gegen solch eine stationäre Verteilung konvergiert.

Homogene Markow-Ketten mit einer stationären Verteilung als Startverteilung sind [[Stark stationärer Prozess|stark stationäre]] stochastische Prozesse. Somit sind zeitdiskrete Markow-Ketten mit abzählbarem Zustandsraum [[Maßerhaltendes dynamisches System|maßerhaltende dynamische Systeme]], wenn sie in ihrer [[Invariante Verteilung|invarianten Verteilung]] starten. Sind sie zusätzlich [[Positiv rekurrente Markow-Kette|positiv rekurrent]] sowie [[Irreduzible Markow-Kette|irreduzibel]], so sind sie sogar [[Ergodischer stochastischer Prozess|ergodische stochastische Prozesse]] und erlauben die Anwendung von Aussagen der [[Ergodentheorie]] wie zum Beispiel des [[Individueller Ergodensatz|individuellen Ergodensatzes]].

=== Reversibilität ===
{{Hauptartikel|Reversible Markow-Kette}}
Bei reversiblen Markow-Ketten lässt sich nicht unterscheiden, ob sie in der Zeit vorwärts oder rückwärts laufen, sie sind also invariant unter Zeitumkehr. Insbesondere folgt aus Reversibilität die Existenz eines stationären Zustandes.

== Modellierung ==
Oft hat man in Anwendungen eine Modellierung vorliegen, in welcher die Zustandsänderungen der Markow-Kette durch eine Folge von zu zufälligen Zeiten stattfindenden Ereignissen bestimmt wird (man denke an obiges Beispiel von Bediensystemen mit zufälligen Ankunfts- und Bedienzeiten). Hier muss bei der Modellierung entschieden werden, wie das gleichzeitige Auftreten von Ereignissen (Ankunft [[Liste lateinischer Phrasen/V#vs.|vs.]] Erledigung) behandelt wird. Meist entscheidet man sich dafür, künstlich eine Abfolge der gleichzeitigen Ereignisse einzuführen. Üblicherweise unterscheidet man dabei zwischen den Möglichkeiten ''Arrival First'' und ''Departure First''.

=== Arrival First (AF) ===
Bei dieser Disziplin wird zu Beginn eines Zeitschrittes das Bedienen gestartet. Danach treffen neue Forderungen ein, und erst am Ende eines Zeitschrittes tritt das Bedien-Ende auf.

[[Datei:Arrival First.svg|300px|zentriert]]

Der Vorteil dieser Disziplin ist, dass Forderungsankünfte immer vor einem möglichen Bedien-Ende eintreffen und damit die [[PASTA-Eigenschaft]] (Poisson Arrivals See Time Averages) gilt. Mit Hilfe dieser Eigenschaft lassen sich für Ankünfte, die als [[Bernoulli-Prozess]] modelliert sind, unter anderem sehr einfach für Bediensysteme wichtige Eigenschaften wie die Verlustwahrscheinlichkeit <math>P_V</math> berechnen.

Als Nachteil kann eine Forderung, die im Zeitschlitz <math>z_t</math> eintrifft, frühestens in <math>z_{t+1}</math> fertig bedient werden. Dies führt unter Umständen zu einer höheren Anzahl von benötigten Warteplätzen im modellierten System.

=== Departure First (DF) ===
Im Fall von ''Departure First'' kommen zu Beginn eines Zeitschrittes Forderungen im System an. Darauf folgt der Start von Bedienzeiten und am Ende eines Zeitschrittes das Ende von Bedienzeiten.

[[Datei:Departure First.svg|300px|zentriert]]

Bei diesem Ansatz gilt die ''PASTA'' Eigenschaft nicht mehr, was im Allgemeinen zu komplizierteren Berechnungen als im Falle von ''Arrival First'' führt. Eine Forderung kann im selben Zeitschritt eintreffen und fertig bedient werden.

=== Simulation ===
Diskrete Markow-Ketten mit endlichem Zustandsraum <math> S=\{1, \dots, m\} </math> können leicht simuliert werden, wenn [[Standardzufallszahl]]en <math> u_t </math> verfügbar sind. Dazu definiert man
<math> r_i(j)=
\begin{cases}
0 & \text{falls }\quad j=0 \\
\sum_{l=1}^j p_{il} & \text{sonst}
\end{cases}
</math>

für alle <math> i,j \in S </math>. Ist nun <math> X_t=i </math>, dann setze <math> X_{t+1}=j </math> genau dann, wenn <math> u_t \in [r_i(j-1),r_i(j)] </math> ist. Dieses Verfahren ist insbesondere dann effizient, wenn wenige <math> p_{ij} </math> ungleich null sind. Es entspricht der [[Inversionsmethode]] mit der Wahrscheinlichkeitsfunktion <math> p_i(\{j\}):=p_{ij} </math>. Die Möglichkeit, auch große Markow-Ketten zu simulieren, macht man sich beim [[MCMC-Verfahren]] zunutze, um Verteilungen zu simulieren, die nicht durch klassische Verfahren simuliert werden können.

== Anwendungen ==
Markow-Ketten werden in unterschiedlichen Bereichen verwendet.
* In den Wirtschaftswissenschaften bei der [[Warteschlangentheorie]]. Hier unterstellt man eine homogene Markow-Kette. Dort wird die zu einer Periode wartende Anzahl an Kunden betrachtet. Die Wahrscheinlichkeiten für Ankunft oder Abfertigung eines Kunden sind zeitinvariant (unabhängig von der Periode).
* Markow-Ketten werden in der [[Bioinformatik]] dazu verwendet, Sequenzabschnitte auf bestimmte Eigenschaften zu untersuchen. Hierzu zählt z. B. das Vorhandensein von [[CpG-Insel]]n, da in diesen die Übergangswahrscheinlichkeiten zwischen [[Cytosin|C]]-[[Guanin|G]] und G-C erhöht sind.
* In der [[Gesundheitsökonomie]] zur [[Wahrscheinlichkeitstheorie|probabilistischen]] Modellierung im Zuge einer [[Kosten-Nutzen-Analyse]] von Gesundheitstechnologien wie zum Beispiel Medikamenten.
* In der [[Versicherungsmathematik]] werden diskrete Markow-Ketten verwendet zur Einrechnung [[Biometrisches Risiko|biometrischer Risiken]] (Invalidisierungswahrscheinlichkeiten, Sterbewahrscheinlichkeiten, …).
* In der Musik zur [[Algorithmische Komposition|Komposition algorithmischer Werke]], zum Beispiel bei [[Iannis Xenakis]].
* Im [[Qualitätsmanagement]] zur Bestimmung der [[Zuverlässigkeit (Technik)|Zuverlässigkeit]] eines Systems und dessen Teilkomponenten
* In der Physik zur Modellierung des Zerfalls eines [[Compoundkern]]s und zur Herleitung von [[Mastergleichung|Master-Gleichungen]] in der [[Markow-Näherung]]
* Im [[Spam|automatisierten Onlinemarketing]] zur Generierung von Texten, welche von automatischen [[Spamfilter]]n nur schwer von durch Menschen verfassten Texten zu unterscheiden sind.
* Ebenso zum Erkennen von Spam-Mails mittels eines [[Markow-Spamfilter]]s
* Bestimmte Brettspiele wie [[Monopoly]] und das [[Leiterspiel]] lassen sich als Markow-Kette auffassen.
* Der [[PageRank]] einer Homepage lässt sich als Markow-Kette interpretieren. Insbesondere ist diese Markow-Kette durch die [[Übergangsmatrix|stochastische]] [[Google-Matrix]] beschrieben.<ref>{{Literatur |Autor=Noemi Kurt |Titel=Markov-Ketten |Sammelwerk=Stochastik für das Informatikstudium |Band=31 |Nummer=3 |Verlag=Springer Berlin Heidelberg |Ort=Berlin, Heidelberg |Datum=2025 |ISBN=978-3-662-71047-0 |Seiten=195–215 |DOI=10.1007/978-3-662-71048-7_11 |Online=[https://link.springer.com/10.1007/978-3-662-71048-7_11 Online] |Abruf=2026-04-24 |Sprache=de}}</ref>
Markow selbst nutzte sie 1913 zur statistischen Untersuchung des Versepos [[Eugen Onegin]]<ref>{{Literatur |Autor=А. А. Марковъ |Titel=Versuche einer statistischen Untersuchung über den Text des Romans »Eugen Onegin« zur Beleuchtung des Zusammenhangs der Kettenversuche |Sammelwerk=Извѣстія Императорской Академіи Наукъ |WerkErg=VI серiя |Band=7 |Nummer=3 |Ort=Sankt-Petersburg |Datum=1913 |Seiten=153–162 |Online=[https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=6612&option_lang=rus Online] |Originaltitel=Примѣръ статистическаго изслѣдованiя надъ текстомъ “Евгенiя Онѣгина”, иллюстрирующiй связь испытанiй въ цѣпь |Originalsprache=ru |Sprache=de}}</ref><ref>{{Literatur |Autor=Andrej A. Markow |Titel=Beispiel einer statistischen Untersuchung am Text »Evgenij Onegin« zur Veranschaulichung der Zusammenhänge von Proben in Ketten |Hrsg=Philipp von Hilgers, Sven Spieker, Wladimir Velminski |Sammelwerk=Andrej A. Markov: Berechenbare Künste |Verlag=Diaphanes |Ort=Berlin |Datum=2018 |Reihe=sequenzia |ISBN=978-3-935300-69-8 |Online=[https://www.diaphanes.net/titel/beispiel-einer-statistischen-untersuchung-am-text-270 Online] |Sprache=de}}</ref> und 1924 des Textes ''Kinderjahre Bagrows des Enkels'' von [[Sergei Timofejewitsch Aksakow]].<ref>{{Literatur |Titel=Die Entwicklung der Wahrscheinlichkeitstheorie von den Anfängen bis 1933: Einführungen und Texte |Auflage=Reprint 2024 |Verlag=De Gruyter |Ort=Berlin Boston |Datum=1989 |ISBN=978-3-11-273210-6 |Seiten=444 |Sprache=de}}</ref><ref>{{Literatur |Autor=Peter Grzybek, Emmerich Kelih |Titel=Zur Vorgeschichte quantitativer Ansätze in der russischen Sprach-und Literaturwissenschaft |Hrsg=Reinhard Köhler, Gabriel Altmann, Rajmund G. Piotrowski |Sammelwerk=Quantitative Linguistik / Quantitative Linguistics - Ein internationales Handbuch / An International Handbook |Verlag=De Gruyter |Ort=Berlin |Datum=2005 |ISBN=978-3-11-015578-5 |Sprache=de}}</ref>

== Siehe auch ==
* [[Markov Random Field]]
* [[Endlicher Automat]]
* [[Hidden Markov Model]]
* [[Semi-Markow-Prozess]]

== Literatur ==
* Pierre Brémaud: ''Markov Chains''. Springer Verlag, 1999, ISBN 0-387-98509-3.
* Ehrhard Behrends: ''Introduction to Markov Chains''. Vieweg, 2000, ISBN 3-528-06986-4.
* {{Literatur |Autor=Kai Lai Chung |Titel=Markov Chains: With Stationary Transition Probabilities |Auflage=2nd ed |Verlag=Springer Berlin / Heidelberg |Ort=Berlin, Heidelberg |Datum=1967 |Reihe=Grundlehren der Mathematischen Wissenschaften Ser |NummerReihe=v.104 |ISBN=978-3-540-03822-1 |Sprache=en}}
* {{Literatur |Autor=Franz Ferschl |Titel=Markovketten |Verlag=Springer Berlin / Heidelberg |Ort=Berlin, Heidelberg |Datum=1970 |Reihe=Lecture Notes in Economics and Mathematical Systems Ser |NummerReihe=v.35 |ISBN=978-3-540-04958-6 |Sprache=de}}
* Olle Häggström: ''Finite Markov Chains and Algorithmic Applications''. Cambridge University Press, 2002.
* [[Thorsten Imkamp]], Sabrina Proß: ''Einstieg in stochastische Prozesse'', Springer 2023, ISBN 978-3-662-66669-2
* Daniel W. Stroock: ''An introduction to Markov processes.'' (= Graduate Texts in Mathematics. 230). 2. Auflage. Springer/Heidelberg 2014, ISBN 978-3-642-40522-8.

== Weblinks ==
{{Commonscat|Markov chains|Markow-Kette}}
* [https://www.mathematik.uni-ulm.de/stochastik/lehre/ss03/markov/skript/node3.html HTML-Vorlesung] zu Markow-Ketten der Universität Ulm
* [https://a-herzog.github.io/MarkovChains/index_de.html Simulation von Markow-Ketten] des [https://www.simzentrum.de/lehre/oer Simulationswissenschaftlichen Zentrums Clausthal – Göttingen]
* [https://team.inria.fr/neo/marmote/ marmote] – eine vom [[Inria]] entwickelte C++-Bibliothek für Markow-Ketten
* Michael Schilli: ''[https://www.linux-magazin.de/ausgaben/2017/09/snapshot/ KI-System mit Markow-Ketten entwickeln]'' aus [[Linux-Magazin]] 09/2017

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4037612-6}}
[[Kategorie:Markow-Prozesse]]
[[Kategorie:Andrei Andrejewitsch Markow (Mathematiker, 1856) als Namensgeber]]

Markow-Kette - Versionsgeschichte

imported>Leonry am 26. April 2026 um 20:04 Uhr