Zusammenfassung - Grenzverhalten von Austauschprozessen
Zur Orientierung
Zielsetzung
Ziel ist es, das Grenzverhalten von Austauschprozessen möglichst genau zu beschreiben.
Wir verdeutlichen die Zusammenhänge exemplarisch anhand des folgenden Sharing-Systems.
Sharing-System: Beschreibung des Austauschprozesses
| Übergangsgraph | Übergangstabelle | Prozessmatrix | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
$P = \begin{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix}$ |
Simulation eines Austauschprozesses
Die folgende Übersicht zeigt, wie man Veteilungsvektoren ausgehend von einer vorgegebenen Prozessmatrix $P$ und einer Ausgangsverteilung $\vec{v}_{0}$ berechnen kann.
| Schritte | Verteilungsvektor | rekursive Darstellung | Umformung | Potenzschreibweise |
|---|---|---|---|---|
| $0$ | $\vec{v}_{0}$ | $= E \cdot \vec{v}_{0}$ | $= P^0 \cdot \vec{v}_{0}$ | |
| $1$ | $\vec{v}_{1}$ | $= P \cdot \vec{v}_{0}$ | $= P \cdot \vec{v}_{0}$ | $= P^1 \cdot \vec{v}_{0}$ |
| $2$ | $\vec{v}_{2}$ | $= P \cdot \vec{v}_{1}$ | $= P \cdot (P \cdot \vec{v}_{0}) = (P \cdot P) \cdot \vec{v}_{0}$ | $= P^2 \cdot \vec{v}_{0}$ |
| $3$ | $\vec{v}_{3}$ | $= P \cdot \vec{v}_{2}$ | $= P \cdot ((P \cdot P) \cdot \vec{v}_{0}) = (P \cdot P \cdot P) \cdot \vec{v}_{0}$ | $= P^3 \cdot \vec{v}_{0}$ |
| ... | ... | ... | ... | ... |
Die explizite Berechnungen verwenden Matrixpotenzen, die man so bildet.
Matrixpotenzen
Für eine quadratische Matrix $M$ legt man die Matrixpotenzen $M^{i}$ für natürliche Zahlen $i$ so fest.
$M^{0} = E\quad$ ($E$: Einheitsmatrix)
$M^{1} = M$
$M^{2} = M \cdot M$
$M^{3} = M \cdot M \cdot M$
...
Beachte, dass man bei der Berechnung der Matrixpotenzen keine Reihenfolge der Rechenschritte angeben muss, da das Assoziativgesetz für das Matrixprodukt gilt.
Simulation eines Austauschprozesses
Die Entwicklung des Austauschprozesses mit vorgegebene Prozessmatrix $P$ und einer Ausgangsverteilung $\vec{v}_{0}$ kann man mit Hilfe der folgenden Formeln beschreiben.
Rekursive Darstellung
$\vec{v}_n = P \cdot \vec{v}_{n-1} \quad$ für $n \geq 1$
Explizite Darstellung
$\vec{v}_{n} = P^{n} \cdot \vec{v}_{0}$
Für das oben gezeigte Sharingsystem erhält man für $\vec{v}_{0} = \begin{pmatrix} 100 \\ 100 \\ 100 \end{pmatrix}$ folgende Veteilungsvektoren.
| Schritte | Verteilungsvektor | rekursive Berechnung | explizite Berechnung |
|---|---|---|---|
| $0$ | $\vec{v}_0 = \begin{pmatrix} 100 \\ 100 \\ 100 \end{pmatrix}$ | $\vec{v}_0 = P^{0} \cdot \vec{v}_{0} = E \cdot \vec{v}_{0} = \vec{v}_{0}$ | |
| $1$ | $\vec{v}_1 = \begin{pmatrix} 120 \\ 80 \\ 80 \end{pmatrix}$ | $\vec{v}_1 = P \cdot \vec{v}_0 = \begin{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix} \cdot \begin{pmatrix} 100 \\ 100 \\ 100 \end{pmatrix}$ | $\vec{v}_1 = P^{1} \cdot \vec{v}_{0} = P \cdot \vec{v}_{0} = \begin{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix} \cdot \begin{pmatrix} 100 \\ 100 \\ 100 \end{pmatrix}$ |
| $2$ | $\vec{v}_2 = \begin{pmatrix} 132 \\ 84 \\ 84 \end{pmatrix}$ | $\vec{v}_2 = P \cdot \vec{v}_1 = \begin{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix} \cdot \begin{pmatrix} 120 \\ 90 \\ 90 \end{pmatrix}$ | $\vec{v}_2 = P^{2} \cdot \vec{v}_{0} = \begin{pmatrix} 0.68 & 0.21 & 0.43 \\ 0.16 & 0.52 & 0.16 \\ 0.16 & 0.27 & 0.41 \end{pmatrix} \cdot \begin{pmatrix} 100 \\ 100 \\ 100 \end{pmatrix}$ |
| ... | ... | ... | ... |
Grenzverhalten eines Austauschprozesses
Experimente zeigen, dass man beim Sharing-System für jede (relative oder absolute) Ausgangsverteilung eine stabile Grenzverteilung $\vec{v}_{\infty}$ erhält. Im Applet muss man nur genügend viele Schritte durchführen, um diese Grenzverteilung (annähernd) zu erhalten.
Zum Herunterladen: matrixpotenzen1.ggb
Für die Grenzverteilung $\vec{v}_{\infty}$ des Sharing-Systems erhält man dabei folgende Werte.
| Schritte | relative Verteilungsvektoren |
|---|---|
| $0$ | $\vec{v}_{0} = \begin{pmatrix} a \\ b \\ c \end{pmatrix}\quad$ mit $a+b+c = 1$ |
| $\downarrow$ | |
| $\infty$ | $\vec{v}_{\infty} = \begin{pmatrix} 0.5 \\ 0.25 \\ 0.25 \end{pmatrix}$ |
Für absolute Verteilungsvektoren erhält man entsprechend diese Werte:.
| Schritte | absolute Verteilungsvektoren |
|---|---|
| $0$ | $\vec{v}_{0} = \begin{pmatrix} a \\ b \\ c \end{pmatrix}\quad$ |
| $\downarrow$ | |
| $\infty$ | $\vec{v}_{\infty} = \begin{pmatrix} 0.5 \cdot (a+b+c) \\ 0.25 \cdot (a+b+c) \\ 0.25 \cdot (a+b+c) \end{pmatrix} = (a+b+c) \cdot \begin{pmatrix} 0.5 \\ 0.25 \\ 0.25 \end{pmatrix}$ |
Bei vielen in der Praxis auftretenden Austauschprozessen erhält man stabile Grenzverteilungen für beliebige Ausgangsverteilungen. Es gibt aber auch Austauschprozesse, die nicht zu stabilen Grenzverteilungen führen. Das Applet zeigt ein Beispiel.
Zum Herunterladen: matrixpotenzen3.ggb
In diesem speziellen Fall wechselt der Verteilungsvektor ständig zwischen zwei Werten hin und her. Es fällt auch auf, dass die Potenzen der Prozessmatrix zwischen zwei Werten hin und her pendeln. Es gibt demnach Austauschprozesse mit instabilem Grenzverhalten.
Konvergenz eines Austauschprozesses
Im folgenden Applet ist ein Austauschprozess mit stabilen Grenzverteilungen dargestellt. Den Stabilisierungseffekt sieht man, wenn man wiederholt Schritte ausführt. Das Applet verdeutlicht, dass sich nicht nur die Verteilungen stabilisieren, es stabilisieren sich auch die Potenden der Prozessmatrix.
Zum Herunterladen: matrixpotenzen1.ggb
Wir bezeichnen die erreichte Grenzmatrix mit $P_{\infty}$. Die folgende Tabelle zeigt die Ergebnisse der Experimente mit dem Applet zum Sharing-System.
| Schritte | Potenzen der Prozessmatrix | rel. Ausgangsverteilung | erzielte Verteilungen | ||
|---|---|---|---|---|---|
| $0$ | $P^{0} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ | $\cdot$ | $\vec{v}_{0} = \begin{pmatrix} a \\ b \\ c \end{pmatrix}\;\;$ mit $a+b+c = 1$ | $=$ | $\vec{v_0} = \begin{pmatrix} a \\ b \\ c \end{pmatrix}$ |
| $1$ | $P^{1} = \begin{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix}$ | $\cdot$ | $\vec{v}_{0} = \begin{pmatrix} a \\ b \\ c \end{pmatrix}\;\;$ mit $a+b+c = 1$ | $=$ | $\vec{v_1} = \begin{pmatrix} \cdots \\ \cdots \\ \cdots \end{pmatrix}$ |
| $\downarrow$ | |||||
| $\infty$ | $P_{\infty} = \begin{pmatrix} 0.5 & 0.5 & 0.5 \\ 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 \end{pmatrix}$ | $\cdot$ | $\vec{v}_{0} = \begin{pmatrix} a \\ b \\ c \end{pmatrix}\;\;$ mit $a+b+c = 1$ | $=$ | $\vec{v}_{\infty} = \begin{pmatrix} 0.5 \\ 0.25 \\ 0.25 \end{pmatrix}$ |
Es fällt auf, dass die Spaltenvektoren der Grenzmatrix $P_{\infty}$ mit der Grenzverteilung $\vec{v}_{\infty}$ hier übereinstimmen.
Eine Rechnung zeigt, dass für alle relativen Verteilungsvektoren mit $a+b+c = 1$ tatsächlich folgende Beziehung gilt:
$\begin{pmatrix} 0.5 & 0.5 & 0.5 \\ 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 \end{pmatrix} \cdot \begin{pmatrix} a \\ b \\ c \end{pmatrix} = \begin{pmatrix} 0.5a + 0.5b + 0.5c \\ 0.25a + 0.25b + 0.25c \\ 0.25a + 0.25b + 0.25c \end{pmatrix} = \begin{pmatrix} 0.5 \cdot (a+b+c)\\ 0.25 \cdot (a+b+c)\\ 0.25 \cdot (a+b+c) \end{pmatrix} = \begin{pmatrix} 0.5 \\ 0.25 \\ 0.25 \end{pmatrix}$
Wir fassen die Zusammenhänge im folgenden Satz zusammen.
Grenzverhalten eines Austauschprozesses
Wenn die Potenzen $P^{n}$ der Prozessmatix $P$ zu einem Austauschprozess mit wachsenden Exponenten $n$ zu einer stabilen Grenzmatrix $P_{\infty}$ führen, dann gilt für jede Ausgangsverteilung $\vec{v}_0$:
$\vec{v}_{\infty} = P_{\infty} \cdot \vec{v}_{0}$
Die Spaltenvektoren der Grenzmatrix $P_{\infty}$ stimmen mit der Grenzverteilung $\vec{v}_{\infty}$ überein.
Man kann zeigen, dass ein Austauschprozess unter folgender Bedingung ein stabiles Grenzverhalten hat.
Konvergenz eines Austauschprozesses
Wenn in irgendeiner Potenz der Prozessmatrix $P$ alle Elemente von Null verschieden sind, dann existiert die Grenzmatrix $P_{\infty}$.
Zu jeder Ausgangsverteilung $\vec{v}_{0}$ gibt es dann eine eindeutig bestimmte Grenzverteilung $\vec{v}_{\infty}$ mit
$\vec{v}_{\infty} = P_{\infty} \cdot \vec{v}_{0}$.
Die Summe der Elemente der Grenzverteilung $\vec{v}_{\infty}$ entspricht dabei der Summe der Elemente der Ausgangsverteilung $\vec{v}_{0}$.
