Kurs:Stochastik/Stochastische Netze

SIR Model - Animation - Zustandsübergänge in der Epidemiologie - Suceptible-Infected-Removed/Recovered - SIRD-Erweiterung mit "D" Deceased

Einleitung

Der Lerneinheit gliedert sich in die folgenden Teile

• Stochastische Matrix
• Stationäre Verteilung:
• Potenzen der Übergangsmatrix:

Markov-Ketten

Stochastische Netze, auch als Markov-Ketten oder stochastische Prozesse bekannt, sind mathematische Modelle, die verwendet werden, um zufällige Prozesse zu beschreiben, bei denen der Zustand $x^{(t)}$ eines Systems zu einem bestimmten Zeitpunkt $t$ nur vom Zustand $x^{(t-1)}$ des Systems zu einem vorherigen Zeitpunkt $t-1$ abhängt. Diese Modelle sind besonders nützlich in der Wahrscheinlichkeitstheorie, der Statistik und der Operations Research.

Definition eines stochastischen Netzes

Ein stochastisches Netz besteht aus einer Menge von Zuständen und den Übergangswahrscheinlichkeiten zwischen diesen Zuständen. Ein einfaches Beispiel ist eine Markov-Kette, bei der die Zustände diskret sind und die Übergänge zwischen den Zuständen durch eine Übergangsmatrix beschrieben werden.

Darstellung über Matrizen

Ein stochastisches Netz kann durch eine Übergangsmatrix $P$ dargestellt werden. Diese Matrix gibt die Wahrscheinlichkeiten an, mit denen das System von einem Zustand in einen anderen übergeht.

Beispiel: Markov-Kette

Sei $\{X_{n}\}$ eine Markov-Kette mit endlich vielen Zuständen $\{1,2,\ldots ,N\}$. Die Übergangsmatrix $P$ ist eine $N\times N$-Matrix, deren Elemente $p_{ij}$ die Wahrscheinlichkeit angeben, dass das System vom Zustand $i$ in den Zustand $j$ übergeht:

$P={\begin{pmatrix}p_{_{(1,1)}}&p_{_{(1,2)}}&\cdots &p_{_{(1,N)}}\\p_{_{(2,1)}}&p_{_{(2,2)}}&\cdots &p_{_{(2,N)}}\\\vdots &\vdots &\ddots &\vdots \\p_{_{(N,1)}}&p_{_{(N,2)}}&\cdots &p_{_{(N,N)}}\end{pmatrix}}$

Eigenschaften der Matrix

Für die Matrix $P\in Mat(N\times N,\mathbb {R} )$ gilt:

• (SN1) $p_{_{(i,j)}}\geq 0$ für alle $i,j$.
• (SN2) $\sum _{j=1}^{N}p_{_{(i,j)}}=1$ für alle $i$.

Teil 1 - Monte-Carlo oder Aufteilung des Masseflusses

Eine Übergangsmatrix ist eine stochastische Matrix, da die Summe der Elemente jeder Spalte gleich 1 ist. Jede Spalte beschreibt eine diskrete Wahrscheinlichkeitsverteilung für einen bestimmten Knoten mit dem Index $i\in \{1,\ldots ,N\}$ zu $N$ möglichen anderen Knoten im Netz. Die Netzwerkverbindung von dem i-ten Knoten zu sich selbst, beschreibt die Wahrscheinlichkeit im Zustand $i$ zu bleiben.

Teil 2 - Stationäre Verteilung

Eine stationäre Verteilung $x\in \mathbb {R} ^{n}$ ist ein Vektor, der ein Fixpunkt der Matrix als Abbildung ist. Ein Fixpunkt erfüllt also die Gleichung $P\cdot x=x$. Dies bedeutet, dass die Verteilung der Massen zwischen den Zustände im Gleichgewicht bleibt. Es bedeutet aber nicht, dass kein Fluß von Massen in dem stochastischen Netz mehr existiert.

Teil 3 - Konvergenz einer Verteilung bei Iteration

Betrachtet man $x^{(0)}\in V:=\mathbb {R} ^{n}$ als Startpunkt für eine Matrix $P$, dann kann man die Veränderung der Zustände als eine Folge $(x^{(n)})_{n\in \mathbb {N} }V^{\mathbb {N} }$. Die Folgenglieder werden ausgehend vom Startpunkt induktiv berechnet, d.h.:

$x^{(n+1)}:=P\cdot x^{(n)}$

Man man nun untersuchen, ob die Folgen von Vektoren in $V$ konvergiert oder ein wiederkehrendes Muster generiert.

Aufgabe für Studierende

Welche mathematischen Aussagen existieren für diese Folgen im $\mathbb {R} ^{n}$ und deren Konvergenz in Bezug auf die Matrix $P$?

Teil 3 - Potenzen der Übergangsmatrix

Die $n$-te Potenz der Übergangsmatrix $P^{n}$ gibt die Übergangswahrscheinlichkeiten nach $n$ Schritten an.

Beispiel

Betrachten wir eine einfache Markov-Kette mit drei Zuständen $\{1,2,3\}$ und der folgenden Übergangsmatrix:

$P={\begin{pmatrix}0.5&0.3&0.2\\0.2&0.6&0.3\\0.3&0.1&0.5\end{pmatrix}}$

Hierbei bedeutet $p_{12}=0.3$, dass die Wahrscheinlichkeit, vom Zustand 2 in den Zustand 1 überzugehen, 0.3 beträgt.

Anwendungen

Stochastische Netze und Markov-Ketten haben viele Anwendungen in verschiedenen Bereichen, darunter:

Warteschlangentheorie

Modellierung von Warteschlangen in Telekommunikationssystemen, Verkehrsnetzen und Computersystemen. Modellieren Sie mit einer stochastischen Matrix eine elementare Warteschlage mit 3 Knoten im Graph:

• in der Warteschlange im Callcenter,
• im Gespräch mit Mitarbeiter:in im Callcenter,
• Callcenter verlassen (weder in der Warteschlange noch im Mitarbeitergespräch

Finanzmathematik

Modellierung von Aktienkursen und anderen finanziellen Prozessen. Betrachten 3 verschiedene Aktien, die von Anleger:innen erworben werden können. Die stochastische Matrix $S_{t}$ beschreibt zu einem Zeitpunkt $t$, die Übergangswahrscheinlichkeiten, eine bestimmte Aktien zu verkaufen und dafür andere Aktien dafür zu kaufen.

• Versuchen Sie, den Fluss von Geld für An- und Verkauf von Matrizen zwischen Aktien zu modellieren!
• Wie kann man in die Modelle aufnehmen, dass Aktien unterschiedliche Ankaufs- und Verkaufspreise besitzen?

Biologie

Modellierung von

• genetischen Prozessen und
• Populationsdynamik.

Genetische Prozesse

Welche stochastischen Prozesse findet man in der Genetik im Kontext von Genotypen? Verwenden Sie eine Markov-Kette, um die Veränderung der Genotypenfrequenzen zu modellieren. Die Zustände der Markov-Kette sind die möglichen Genotypen und die Übergangswahrscheinlichkeiten zwischen diesen Zuständen hängen von den Kreuzungswahrscheinlichkeiten ab. Erzeugen Sie dazu eine elementare stochastische Matrix.

Genetische Algorithmen

Genetische Algorithmen modellieren Mutations- und Selektionprozesse und diese können dann in Optimierungsverfahren verwendet werden. Wie kann man stochastische Matrizen für Mutation verwenden? Was sind die Zustände der Matrix und wie kann man die Übergangswahrscheinlichkeiten zwischen Zuständen festlegen?

Bemerkung - Genetische Algorithmen

In der biologischen Evolution sind die Gene von Organismen natürlich vorkommenden Mutationen ausgesetzt, wodurch genetische Variabilität entsteht. Mutationen können sich positiv, negativ oder gar nicht auf die Erben auswirken. Da es zwischen erfolgreichen Individuen zur Fortpflanzung (Rekombination) kommt, können sich Arten über mehrere Generationen an einen vorliegenden Selektionsdruck anpassen (z.B. Klimaveränderungen oder die Erschließung einer ökologischen Nische). Diese vereinfachte Vorstellung wird in der Informatik idealisiert und künstlich im Computer nachgebildet. Dabei wird die Güte eines Lösungskandidaten explizit mit einer Fitnessfunktion oder Gütefunktion berechnet, sodass verschiedene Kandidaten vergleichbar sind.

Bemerkung - Mutation und Selektion mit Gütefunktion

Entsprechend dem natürlichen Vorbild gibt es bei den evolutionären Algorithmen Individuen, die aus einem Genom bestehen, welches die zu bestimmenden Eigenschaften der gesuchten Lösung in geeigneter Weise enthält. Ein Individuum entspricht einem Lösungskandidaten. Die durch die genetischen Operatoren erzeugten Individuen werden Nachkommen oder Kinder genannt. Zustandsübergangswahrscheinlichkeiten können dabei durch stochastische Matrix beschrieben werden, die aus einem Ausgangszustand die Veränderungen (Mutationen) erzeugt. Eine Iteration des Verfahrens heißt entsprechend dem biologischen Vorbild "Generation". Aus der jeweiligen Population wählt entsprechend der Fitnessfunktion die besten Kandidaten aus (Selektion) und führt weitere Mutations- und Selektionszyklen durch, um bessere Lösungskandidaten für eine Problem stochastisch zu generieren. Weitere Begriffsdefinitionen können in der VDI-Richtlinie VDI/VDE 3550 gefunden werden.

Operations Research

Optimierung von Produktionsprozessen und Logistik.

• Betrachten Sie ein Wegenetz mit 5 Knoten, die Übergangswahrscheinlichkeiten $p_{(i,k)}$ beschreiben in den Spalten die Wahrscheinlichkeiten, dass ein Objekt über den Weg zwischen Knoten $k$ von einem Knoten $i$ transportiert wird.
• die Übergangswahrscheinlichkeiten $p_{(k,k)}$ beschreiben die Wahrscheinlichkeit, dass ein zu transpierendes Objekt am dem Ort $k$ verbleibt.
• Die stochastische Matrix kann damit Transportprozesse modellieren! Zeichnen Sie einen Graph mit Übergangswahrscheinlichkeiten und stellen Sie einen zeitdiskreten Transportprozess als Matrixmultiplikation mit Maxima CAS dar!

Zusammenfassung

Stochastische Netze sind Werkzeuge zur Modellierung zufälliger Prozesse, wobei der Folgezustand im Sinne der Gedächnislosigkeit einer Markov-Kette nur von dem vorherigen Zustand und nicht von der gesamten Vergangheit abhängt. Diese Modelle können durch Übergangsmatrizen dargestellt werden, die die Wahrscheinlichkeiten der Übergänge zwischen den Zuständen beschreiben. Diese Matrizen haben spezielle Eigenschaften, die die als Transportprozesse anteilige Stoffströme beschreiben können oder im Sinne eine Zufallsexperimentes an den Knoten in einer Monte-Carlo-Simulation jeweils ein Zufallsexperiment ausführt, das entsprechend der spaltenweisen Wahrscheinlichkeitsverteilung den nächsten Zustand auswählt.

Siehe auch

• COVID-19/Mathematische Modellbildung
• genetische/evolutionäre Algorithmen
• Kurs:Stochastik
• Maxima CAS/Matrixmultiplikation
• Markov-Kette
• Textanalyse und Textgenerierung

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Stochastik' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Stochastik/Stochastische%20Netze
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.