Markov-Ketten

Kurz: Eine Markov-Kette ist ein Zufallsprozess, bei dem der nächste Zustand nur vom aktuellen Zustand abhängt und nicht vom bisherigen Verlauf.

Genauer: Man beschreibt sie durch Übergangswahrscheinlichkeiten zwischen Zuständen. Beispiel: Wetter, das morgen mit 70 % so bleibt wie heute.

Im Detail

• Markov-Eigenschaft: „Gedächtnislosigkeit”. Die Zukunft hängt nur von der Gegenwart ab.
• Übergangsmatrix: Eine Matrix P, deren Zeile i die Wahrscheinlichkeiten von Zustand i zu allen anderen enthält. Jede Zeile summiert sich zu 1.
• Stationäre Verteilung: Auf lange Sicht stellt sich bei vielen Ketten ein fester Anteil pro Zustand ein. Darauf beruht das ursprüngliche PageRank-Verfahren (zufälliger Surfer).
• Einsatz: Textgenerierung einfacher Art (nächstes Wort aus dem aktuellen), Warteschlangenmodelle, Spracherkennung (Hidden-Markov-Modelle), MCMC-Sampling.
• Grenze: Hängt die Zukunft von weiter zurückliegenden Schritten ab, braucht man größere Zustände oder andere Modelle. Moderne Sprachmodelle gehen weit darüber hinaus.

Siehe auch: Monte-Carlo-Methoden