1 Informationen

1.1 Abstract und Motivation

Markov-Ketten sind ein einfaches und anschauliches Modell um realweltliche Vorgänge mathematisch abzubilden. Bei bekannten und als konstant angenommenen Wahrscheinlichkeiten (siehe Abgrenzung) ist es möglich den wahrscheinlichen Zustand eines Systems in beliebiger Zukunft vorherzusagen. Markov-Ketten sind häufig die Grundlage für stochastische Prozesse, die

1. auf gedächtnislosem Zufall basieren [1, S.218-219] [9, S.1] [18, S.4] und 2. bei welchen Zustandsübergänge zu jeweils gegebenen Wahrscheinlichkeiten [9, S.2] [13, 14] möglich sind. Liegen realweltliche Modelle vor, die sich mit den beiden oben genannten Eigenschaften modellieren lassen so ist die Anwendung von Markov-Ketten möglich [3, S.9-16] [3, S.22] [6] [14] . Zudem sind Markov-Ketten geeignet um subjektive Bewertungen unter Objekten in einem System objektiv auszuwerten. Ein Beispiel

dafür ist Google’s ^TM PageRank ^TM Algorithmus. Ein Beispiel dazu folgt bei den Anwendungen für Markov-Ketten. [7, S.1-2]

Markov-Ketten sind eine Reihe von Zuständen. Das System beinhaltet mögliche Zustände, die mit gewissen Wahrscheinlichkeiten erreicht werden können. Dieses System lässt sich als (n × n)-Matrix darstellen. Die Zeile gibt den aktuellen Zustand an. Die Spalten alle erreichbaren. Die Einträge in der Matrix sind dabei die Wahrscheinlichkeiten gegeben einen bestimmten Zustand in einen anderen zu kommen oder in diesem zu verbleiben. Die Lösung der Markov-Kette zu einer Zeit t k gibt die Wahrscheinlichkeit an, mit welcher ich mich nach insgesamt k Schritten in einem anderen Zustand befinde. Für k → +∞ gibt sie die allgemeine Aufenthaltswahrscheinlichkeit in jedem Zustand an.

Anwendungsgebiete

Mit fortgeschrittenen Methoden ist es auch möglich Spamfilter, welche weitaus effektiver als der bekannte Bayesfilter sind, mittels Markov-Ketten zu implementieren. [19] Weiter kann man mit Markov-Ketten unter Anderem Warteschlangenprozesse, Geburts- und Todesprozesse sowie Wahrscheinlichkeitsverteilungen von Objekten in bewegten Systemen berechnen. [1, S.245-246] [21, S.7]

Zusätzlich ist es möglich anhand vieler subjektiver Empfehlungen ein objektives Ranking für das gesamte System anzulegen. Dafür reichen einige wenige fragmentierte und möglicherweise geclusterte Entscheidungen aus. Die Güte des gesamten Rankings steigt jedoch mit der Anzahl der Bewertungen. [2, 7, 8, 17]

1.2 Abgrenzung

Markov-Ketten können Systeme abbilden und mathematisch modellieren. Daraus lassen sich einfach Wahrscheinlichkeiten für das Eintreten von Zuständen errechnen. Das System muss sich hierfür modelliert immer in genau einem solchen Zustand befinden. Die Zeit der Übergänge zwischen Zuständen werden als infinitisimal klein angenommen. [12]

In diesem Paper wird die Thematik der zeitdiskreten und homogenen Markov-Ketten eingeführt. Der Begriff homogen wird in diesem Zusammenhang auch synonym mit “zeitinvariant” gesetzt: die Wahrscheinlichkeiten einen anderen Zustand zugelangen sind also nicht von der Zeit, sondern nur vom aktuellen Zustand, abhängig. Der Begriff zeit-diskret beschreibt eine Eigenschaft, dass ein endlicher Zustandsraum vorliegt. Es existieren diskrete, abzählbare Zeitpunkte und keine Intervalle. Diese Zustände t k können voneinander verschiedene Abstände zum jeweiligen Nachfolger t k+1 haben. Der Zustand zum Zeitpunkt t k ist im Allgemeinen verschieden vom Zustand zum Zeitpunkt t k+1 , für k ∈ N 0 . [1, S.236-237] [3, S.12-13]

1.3 Claim: Anspruch dieses Papers

Dieser Artikel soll ihnen einen adäquaten Einstieg in das Thema Markov-Ketten liefern. Auch ohne explizite Vorkenntnisse von Stochastik, Modellierung, etc. sollten Sie den Texten folgen können. Grundlegende Kenntnisse in Matrix-Vektor- und Matrix-Matrix-Multiplikation werden benötigt. Das letzte Drittel bietet traditionell einen weiteren Ausblick.

Seite 3 von 17

1.4 Konventionen

In diesem Paper verwenden wir folgende Variablen und Ausdrücke:

1. Anzahl aller erreichbaren von einander verschiedenen Systemzustände n 2. k sei der aktuelle Zustand im System oder zukünftige Zustände darin 3. Funktion a(t k ) gebe die Position an, in welchem sich das System zur Zeit t k befindet 4. Wahrscheinlichkeitsübergangsmatrix P ∈ R n×n 5. Schattenmatrix S ∈ R n×n liege “hinter” der Matrix P

6. Wahrscheinlichkeitsübergangsmatrix mit eingerechneter Schattenmatrix P S ∈ R n×n 7. mit jeweils den Einträgen p ij ∈ P bzw. p sij ∈ P S (a) die Zeilen i bezeichnen die Zustände im gesamten System, wobei (b) die Spalten j die Wahrscheinlichkeiten abtragen um von i nach j zu gelangen 8. Irrtumswahrscheinlichkeit ε, dass es eine andere, bessere Alternative gibt 9. n verscheidene Zeilenvektoren r i für i = 1, 2, . . . , n, aus der Matrix P 10. aktuelle Wahrscheinlichkeitsverteilung π k im Zustand k des Systems

Der Unterschied zwischen k und i ist wie folgt anzusehen: ist k = x so befinden wir uns im x-ten Schritt der Markov-Kette. Es gab also keinen oder (x − 1) Schritte davor. Ist i = x so befinden wir uns an der Position a(x) in der Markov-Kette. Die Wahrscheinlichkeiten jetzt in den nächsten Zustand j zu gelangen werden durch den die Wahrscheinlichkeitsverteilung π ij = π kj , j-tes Element im Vektor π i , oder den Wert in p ij aus P angegeben. [5, S.1-9] [6, S.1-10]

Die Wahrscheinlichkeit ε, dass eine andere Lösung trotz dieser Bewertungen die beste ist. ε ∈ R ist für ge- ∧ wöhnlich ein sehr kleiner Wert 0 < ε 1, kann allerdings im Fall des Google ^TM PageRank ^TM auch 0.15 = 15%

betragen. [8, S.1-7] [15, S.1-4]

Die Schattenmatrix S ist die vollverknüpfte Matrix mit den, für gegebenes ε und n, konstanten Einträgen [2, 8, 17]

ε

s ij =

n

Die Schattenmatrix S wird auf die Matrix P addiert. Um die Eigenschaft, die Zeilensumme muss Eins ergeben, zu erfüllen wird die Matrix P mit dem Faktor (1 − ε) gewichtet. So ergibt sich folgender Zusammenhang: die Schattenmatrix S wird zusammen mit der “einfachen” Wahrscheinlichkeitsübergangsmatrix P , gewichtet zu P S . Es gilt: [2, 7, 8, 17] P S = S + (1 − ε) ∗ P.

Die Verwendung von P und P S ist äquivalent. Der einzige Unterschied ist, dass in P S die Schattenmatrix einbezogen worden ist. Wird hierbei vereinfacht von P gesprochen so lässt sich das Vorgehen in der Regel eins zu eins auf die Matrix P S übertragen, sofern es nicht anders angezeigt worden ist. Der Umkehrschluss von P S zu P gilt im Allgemeinen aber nicht, da P S eine spezielle Ausprägung von P ist.

Zur Vereinfachung wird in den einführenden Beispielen ε := 0 angenommen. Die Schattenmatrix wird also nicht in das Modell eingerechnet um die Komplexität am Anfang zu minimieren. Näheres zu der Schattenmatrix

S und der aggregierten Matrix P S wird im Beispiel des PageRank ^TM -Algorithmus’ erklärt. Wir nehmen alle Wahrscheinlichkeiten innerhalb unserer Markov-Kette als positive, aber nicht notwendigerweise streng positive Werte an. Es gilt für gegebene Wahrscheinlichkeiten p ij : 0 ≤ p ij ≤ 1, p ij ∈ R. [20, S.5-10]

Seite 4 von 17

2 Markov-Ketten: Beispiele und Lösung

2.1 Grundlagen

Markov-Ketten können hauptsächlich zwei Arten von Systemen modellieren: generelle Stochastische Petrinetze und Rankings aufgrund von subjektiven Empfehlungen. [2, 17] [3, S.22]

2.1.1 Generelle Stochastische Petrinetze

Der Einsatz von Markov-Ketten bietet an, wenn Modelle vorliegen, die sich auch als Generelle Stochastische Petrinetze (GSPN) modellieren lassen. [3, S.22] Das System muss folglich aus einer festen Anzahl von Zuständen bestehen. Zusätzlich müssen für alle Zustände die jeweiligen Wahrscheinlichkeiten für den Übergang in alle anderen Zustände vorliegen. Sind diese Wahrscheinlichkeiten in jedem Punkt in der Summe eins so kann daraus eine Markov-Kette gebildet werden. Hierbei werden wir uns auf zeit-diskrete homogene Markov-Ketten beschränken. Das heißt, dass die Wahrscheinlichkeiten nicht mit der Zeit variieren.

Mittels der stochastischen Wahrscheinlichkeiten für den Übergang eines Zustandes in einen anderen können hierbei Verteilungen in naher bis weit entfernter Zukunft vorhergesagt werden. Die für weit entfernte Zeiten getroffenen Aussagen sind dabei die Verteilungen des Systems im Allgemeinen. [22, S.2-4]

Können die Markov-Ketten homogen oder inhomogen sein so spricht man hierbei kurz auch von DTMC für discrete time markov chains. [3, S.12-16]

2.1.2 Rankings und Empfehlungen

Eine zweite hauptsächliche Anwendung findet sich bei subjektiven Rankings. Gegeben einer Zahl von Bewertungen kann ein objektives Gesamtranking für ein System erstellt werden. Die Güte dieses Gesamtrankings nimmt mit der Anzahl der subjektiven Einzelentscheidungen zu.

Ein Beispiel hierzu: In einem sozialen Netzwerk bewertet jedes Mitglied unter einem bestimmten, gleichen Aspekt seine Freunde. Er vergibt hierbei die subjektiven Empfehlungen. Je stärker gewichtet man seine Empfehlungen einer anderen Person gibt, desto “wichtiger” wird sie im gesamten System. Vergibt sie wiederum Empfehlungen an eine dritte Person, so wird diese Empfehlung stärker durch das Gewicht und die “Wichtigkeit” der Person, die sie empfohlen hat. Dieses Verhalten setzt sich rekursiv durch die gesamte Markov-Kette fort. Somit müssen keine expliziten Gewichtungen der Empfehler verteilt werden. Sie ergeben sich implizit zur Laufzeit.

Stellt man hierzu eine Markov-Kette auf, so kann für den Aspekt ein Ranking des gesamten Netzwerkes gebildet werden. Je mehr Bewertungen vorliegen und je mehr Freunde alle Mitglieder im Schnitt haben, also je näher das Netzwerk am vollvermaschten Netzwerk ist, desto besser wird des als objektiv anzusehende Ranking.

Über die Güte des möglichen Ergebnisses kann aufgrund fehlender Erfahrung nur spekuliert werden. Der Clou ist, dass man nur transitiv alle Mitglieder als Freundes-Freunde kennen sollte. Somit bewertet man diese über Freunde von Freunden, oder Freunde von Freundes-Freunden, etc. Das einzige Problem sind abgeschlossene Cliquen ohne Kontakte zum Rest des Netzwerkes. [2, 17]

Seite 5 von 17

2.2 Markov-Eigenschaft

Gedächtnisloser Zufall bezieht sich auf eine Eigenschaft ähnlich dem Würfelwurf. Diese hängen, wie das Spielen eines Würfels, nicht vom vorhergehenden Zustand ab. Das ist die sogenannte Markov-Eigenschaft. Sie besagt, dass der nächste Zustand nur vom aktuellen abhängen darf. Alle früheren Zustände haben keinen Einfluss auf Änderungen und müssen folglich nicht betrachtet werden. [18, S.5]

2.3 Allgemeine Lösung von Markov-Ketten

Die Lösung für Markov-Ketten im Unendlichen lässt sich mittels dreier Verfahren ermitteln: die Matrix-Potenzierung, die rekursive Matrix-Vektor-Multiplikation und das direkte Lösen mit der Gauss’schen Eliminierung. Auf letztere soll allerdings hier nicht näher eingegangen werden. [9, 10] [22, S.2-32]

Matrix-Vektor-Multiplikation

Dieses Verfahren ist das Einfachste. Die Wahrscheinlichkeiten im k-ten Zustand werden ermittelt durch folgende rekursive Formel: π k = π (k−1) ∗ P

Das heißt, dass sich die nächste Verteilung π k aus der Verteilung davor, π k−1 und der Anfangsverteilung π 0 ergibt. Die Anfangsverteilung π 0 wird mit steigendem k immer weniger relevant für die Lösung π k . Für lim k→+∞ gilt ∗ P k . Der stochastische Vektor auf der linken Seite extrahiert hierbei einen der n 1 0 · · · 0

auch π k =

Zeilenvektoen aus P . Der Einfachheit halber nehmen wir den Obersten.

Es kann hierfür jeder beliebige stochastische Vektor genommen werden. Da alle Zeilen in P gleich sind muss nur die Summe der Einträge im extrahierenden Vektor eins ergeben.

Das Verfahren iteriert solange bis die Differenz aus π k und π (k−1) hinreichend klein geworden ist. Der Computer kann aufhören, wenn die Genauigkeit im Speicher nicht durch weitere Berechnungsschritte erhöht werden kann. Die Berechnung von π k wird solange für eine Genauigkeitsschwelle λ durchgeführt bis die Zeilenweise summierte Differenz hinreichend genau gegen null konvergiert ist: [18, S.6-10] Δ(π (k−1) , π k ) = | (π (k−1) − π k ) | < λ

λ muss kleiner sein als die Länge des Vektors π (k−1) − π k . Ob < oder ≤ ist in diesem Fall Definitionssache. [2, 6] Die Lösung nach Abbruch des Verfahrens ist gegeben durch π k . Üblicherweise sollte die Genauigkeitsschwelle λ im Bereich von 10 −6 oder kleiner liegen.

Die zueinander korrespondierenden Werte in π (k−1) und π k konvergieren gegen denselben Grenzwert. Dieser Grenzwert z in π k , also π kz , ist für k → +∞ die genaue mathematische Lösung für diesen Eintrag π kz - also den damit beschriebenen Zustand z nach k Iterationen.

Die Methode der Matrix-Vektor-Multiplikation wird für lim k→+∞ , solange der Lösungsvektor mittels der letzten Verteilung π (k−1) neu berechnet bis sich der Lösungsvektor π k verglichen mit seinem Vorgänger π ^(k−1) sich nicht mehr ändert. [2, 6, 17] [5, S.1-9]

Seite 6 von 17