o-mathe | Grenzverhalten » Zusammenfassung - Grenzverhalten von Austauschprozessen

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

	von A	von B	von C
zu A	$0.8$	$0.1$	$0.3$
zu B	$0.1$	$0.7$	$0.1$
zu C	$0.1$	$0.2$	$0.6$

P = (\begin{matrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{matrix})

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 expliziten 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$ ( $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 vorgegebener 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}$ 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{matrix} 100 \\ 100 \\ 100 \end{matrix})$ folgende Veteilungsvektoren.

Schritte	Verteilungsvektor	rekursive Berechnung	explizite Berechnung
$0$	${\vec{v}}_{0} = (\begin{matrix} 100 \\ 100 \\ 100 \end{matrix})$		${\vec{v}}_{0} = P^{0} \cdot {\vec{v}}_{0} = E \cdot {\vec{v}}_{0} = {\vec{v}}_{0}$
$1$	${\vec{v}}_{1} = (\begin{matrix} 120 \\ 90 \\ 90 \end{matrix})$	${\vec{v}}_{1} = P \cdot {\vec{v}}_{0} = (\begin{matrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{matrix}) \cdot (\begin{matrix} 100 \\ 100 \\ 100 \end{matrix})$	${\vec{v}}_{1} = P^{1} \cdot {\vec{v}}_{0} = P \cdot {\vec{v}}_{0} = (\begin{matrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{matrix}) \cdot (\begin{matrix} 100 \\ 100 \\ 100 \end{matrix})$
$2$	${\vec{v}}_{2} = (\begin{matrix} 132 \\ 84 \\ 84 \end{matrix})$	${\vec{v}}_{2} = P \cdot {\vec{v}}_{1} = (\begin{matrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{matrix}) \cdot (\begin{matrix} 120 \\ 90 \\ 90 \end{matrix})$	${\vec{v}}_{2} = P^{2} \cdot {\vec{v}}_{0} = (\begin{matrix} 0.68 & 0.21 & 0.43 \\ 0.16 & 0.52 & 0.16 \\ 0.16 & 0.27 & 0.41 \end{matrix}) \cdot (\begin{matrix} 100 \\ 100 \\ 100 \end{matrix})$
...	...	...	...

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{matrix} a \\ b \\ c \end{matrix})$ mit $a + b + c = 1$
$↓$
$\infty$	${\vec{v}}_{\infty} = (\begin{matrix} 0.5 \\ 0.25 \\ 0.25 \end{matrix})$

Für absolute Verteilungsvektoren erhält man entsprechend diese Werte:.

Schritte	absolute Verteilungsvektoren
$0$	${\vec{v}}_{0} = (\begin{matrix} a \\ b \\ c \end{matrix})$
$↓$
$\infty$	${\vec{v}}_{\infty} = (\begin{matrix} 0.5 \cdot (a + b + c) \\ 0.25 \cdot (a + b + c) \\ 0.25 \cdot (a + b + c) \end{matrix}) = (a + b + c) \cdot (\begin{matrix} 0.5 \\ 0.25 \\ 0.25 \end{matrix})$

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 Potenzsen 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{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix})$	$\cdot$	${\vec{v}}_{0} = (\begin{matrix} a \\ b \\ c \end{matrix})$ mit $a + b + c = 1$	$=$	$\vec{v_{0}} = (\begin{matrix} a \\ b \\ c \end{matrix})$
$1$	$P^{1} = (\begin{matrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{matrix})$	$\cdot$	${\vec{v}}_{0} = (\begin{matrix} a \\ b \\ c \end{matrix})$ mit $a + b + c = 1$	$=$	$\vec{v_{1}} = (\begin{matrix} \dots \\ \dots \\ \dots \end{matrix})$
$↓$
$\infty$	$P_{\infty} = (\begin{matrix} 0.5 & 0.5 & 0.5 \\ 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 \end{matrix})$	$\cdot$	${\vec{v}}_{0} = (\begin{matrix} a \\ b \\ c \end{matrix})$ mit $a + b + c = 1$	$=$	${\vec{v}}_{\infty} = (\begin{matrix} 0.5 \\ 0.25 \\ 0.25 \end{matrix})$

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{matrix} 0.5 & 0.5 & 0.5 \\ 0.25 & 0.25 & 0.25 \\ 0.25 & 0.25 & 0.25 \end{matrix}) \cdot (\begin{matrix} a \\ b \\ c \end{matrix}) = (\begin{matrix} 0.5 a + 0.5 b + 0.5 c \\ 0.25 a + 0.25 b + 0.25 c \\ 0.25 a + 0.25 b + 0.25 c \end{matrix}) = (\begin{matrix} 0.5 \cdot (a + b + c) \\ 0.25 \cdot (a + b + c) \\ 0.25 \cdot (a + b + c) \end{matrix}) = (\begin{matrix} 0.5 \\ 0.25 \\ 0.25 \end{matrix})$

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}$ .

Zusammenfassung - Grenzverhalten von Austauschprozessen

Zur Orientierung

Zielsetzung

Sharing-System: Beschreibung des Austauschprozesses

Simulation eines Austauschprozesses

Matrixpotenzen

Simulation eines Austauschprozesses

Grenzverhalten eines Austauschprozesses

Konvergenz eines Austauschprozesses

Grenzverhalten eines Austauschprozesses

Konvergenz eines Austauschprozesses

Suche

Rückmeldung geben