Zufallsprozesse

Autor: Timo Kötzing

In dieser Lerneinheit wollen wir Zufallsprozesse einführen.

1. Grundlagen: Am Anfang war die Definition
2. Beispiele: Zufallsprozesse
3. Zustandsraum: Wo laufen sie denn?
4. Definition: Markow-Prozess

Wir setzen fest, dass die natürlichen Zahlen \(\mathbb{N} = \{0,1,2,\ldots\}\) die \(0\) enthalten.

---

Grundlagen

Ein Zufallsprozess ist eine Sequenz \((X_t)_{t \in \mathbb{N}}\) von Zufallsvariablen. Üblicherweise stehen diese Zufallsvariablen in einer bestimmten Beziehung, zum Beispiel könnte, für jedes \(t\), \(X_t\) die Menge an Geld sein, die ein Glücksspieler nach \(t\) spielen hat. In der Informatik formalisieren Zufallsprozesse auch häufig den Zustand eines Algorithmus nach \(t\) Iterationen. Häufig weiß man viel über \(X_{t+1}\) sobald \(X_t\) bekannt ist, weil dann nur ein einzelner Schritt des Prozesses zu betrachten ist. Schwerer ist meist, das globale Verhalten des Prozesses zu bestimmen.

---

Beispiele

Nehmen wir nun als Beispiel den folgenden Prozess. Initial werfen wir eine Münze, diese landet entweder auf Kopf oder Zahl. In jeder Runde drehen wir die Münze mit einer bestimmten Wahrscheinlichkeit um: mit Wahrscheinlichkeit \(1/3\), falls Kopf oben liegt, und mit Wahrscheinlichkeit \(3/4\) falls Zahl oben liegt. Damit ist das lokale Verhalten des Prozesses sehr klar. Was die Wahrscheinlickeit ist, dass in Runde \(t\) (für \(t \rightarrow \infty\)) Zahl oben liegt, ist eine globale Eigenschaft des Prozesses.

Schauen wir uns nun noch den Glücksspieler an. Nehmen wir an er fängt an mit 100 Euro und setzt bei einem fairen Spiel immer einen Euro. Er verliert diesen Euro mit Wahrscheinlichkeit \(1/2\), ansonsten gewinnt er seinen Einsatz und einen weiteren Euro. Dann ist also \(X_0 = 100\) deterministisch (im Gegensatz zum vorigen Beispiel, bei dem schon der Initialwert zufällig war). Für alle \(t\) haben wir nun \(X_{t+1} \in \{X_t-1,X_t+1\}\), und zwar jeweils mit Wahrscheinlichkeit \(1/2\). Damit sind die lokalen Eigenschaften klar, globale Eigenschaften aber schwerer zu bestimmen. Man nennt so einen Prozess auch gerne einen random walk. Ähnlich lassen sich auch viele Prozesse der Natur modellieren (zum Beispiel Molekülbewegungen) oder aus der Wirtschaft (zum Beispiel Aktienpreise).

---

Zustandsraum

Wichtigste Eigenschaft eines Zufallsprozess ist der Zustandsraum. Dieser kann endlich oder unendlich sein und wird entsprechend unterschiedlich analysiert. Die wichtigsten Typen sind wie folgt.

1. Endlicher Zustandsraum;
2. Zustandsraum \(\mathbb{R}^n\), mit wichtigem Spezialfall \(n=1\);
3. Zustandsraum \(\mathbb{Z}^n\), wieder mit wichtigem Spezialfall \(n=1\);
4. Beschränkte Intervalle \([a,b]\) oder \([a,b] \cap \mathbb{Z}\).

Das Beispiel mit den Münzen ist ein Beispiel für einen endlichen Zustandsraum, der Spieler ist ein Beispiel für \(\mathbb{Z}\) als Zustandsraum.

---

Markow-Prozess

Wenn der Zustand \(X_{t+1}\) nur von dem Zustand \(X_t\) abhängt und nicht von noch früheren Zuständen (wie in beiden obigen Beispielen), dann nennt man den Zufallsprozess einen Markow-Prozess. Formal ist das definiert als \[ \forall s, r_0, \ldots r_t: P(X_{t+1} = s \mid X_0 = r_0 \wedge \ldots \wedge X_t = r_t) = P(X_{t+1} = s \mid X_t = r_t). \] Viele Prozesse kann man dadurch als Markow-Kette formalisieren, indem man in den Zustandsraum alle diejenigen Elemente mit einbezieht, die zukünftige Verteilungen beinflussen. Wenn also zum Beispiel der Glücksspieler im obigem Beispiel eine höhere Wahrscheinlichkeit zu gewinnen hat, wenn er das erste Spiel des Abends gewonnen hat. Dann ist dieser Prozess zunächst kein Markow-Prozess; allerdings kann das Bit, welches anzeigt, ob das erste Spiel gewonnen wurde, mit in den Zustandsraum übernommen werden, um so einen Markow-Prozess zu erhalten.

Bei Markow-Prozessen kann man endliche Zustandsräume so verstehen, dass die Wahrscheinlichkeitsverteilung über die möglichen nächsten Zustände determiniert sind in Abhängigkeit von dem momentanen Zustand. Diese Verteilungen können zum Beispiel gegeben sein als gerichteter, kantengewichteter Graph (die Summe über alle ausgehenden Kanten eines Knotens addieren sich zu \(1\)).

---

Was haben wir gelernt?

1. Kernbegriffe: Zufallsprozess, Markov-Prozess.
2. Verschiedene Zustandsräume erlauben das formalisieren sehr unterschiedlicher Prozesse.