o-mathe | Stabile Verteilungen » Zusammenfassung - Stabile Verteilungen bei Austauschprozessen

Zusammenfassung - Stabile Verteilungen bei Austauschprozessen

Zur Orientierung

Zielsetzung

Ziel ist es, stabile Verteilungen bei Austauschprozessen zu untersuchen.

Wir verdeutlichen das Vorgehen und 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})

Grenzverteilung als stabile Verteilung

Wenn man den Austauschprozess simuliert, erhält man (für beliebige Ausgangsverteilungen) immer eine feste Grenzverteilung. Die folgende Übersicht verdeutlicht das exemplarisch.

Schritte	Verteilungsvektor
$0$	${\vec{v}}_{0} = (\begin{matrix} 100 \\ 100 \\ 100 \end{matrix})$ (Ausgangsverteilung)
$1$	${\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}) = (\begin{matrix} 120 \\ 80 \\ 80 \end{matrix})$
$2$	${\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}) = (\begin{matrix} 132 \\ 84 \\ 84 \end{matrix})$
...	...
$n$	${\vec{v}}_{n} = P \cdot {\vec{v}}_{n - 1}$ für $n \geq 1$
...	...
$↓$
$\infty$	${\vec{v}}_{\infty} = (\begin{matrix} 150 \\ 75 \\ 75 \end{matrix})$ (Grenzverteilung)

Wenn man die Grenzverteilung als Ausgangsverteilung nimmt, dann ändert sich die Verteilung bei einem Simulationsschritt nicht.

$\underset{P}{\underset{⏟}{(\begin{matrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{matrix})}} \cdot \underset{{\vec{v}}_{\infty}}{\underset{⏟}{(\begin{matrix} 150 \\ 75 \\ 75 \end{matrix})}} = \underset{{\vec{v}}_{\infty}}{\underset{⏟}{(\begin{matrix} 150 \\ 75 \\ 75 \end{matrix})}}$

Bei der Grenzverteilung handelt es sich um eine stabile Verteilung, die im Simulationsprozess immer wieder reproduziert wird.

Stabile Verteilungen präzisieren

Zur Präzisierung des Begriffs stabile Verteilung verwenden wir das Konzept des Fixvektors.

Fixvektor

Ein Fixvektor zu einer quadratischen Matrix $A$ ist ein Vektor $\vec{v}$ mit der folgenden Eigenschaft:

$A \cdot \vec{v} = \vec{v}$

Mit den Rechengesetzen für Matrizen erhält man direkt:

Fixvektoren

Wenn $\vec{v}$ ein Fixvektor zu einer quadratischen Matrix $A$ ist, dann ist auch jedes Vielfache $r \cdot \vec{v}$ ein Fixvektor zur Matrix $A$ .

Es gilt nämlich:

$A \cdot (r \cdot \vec{v}) = (A \cdot r) \cdot \vec{v} = (r \cdot A) \cdot \vec{v} = r \cdot (A \cdot \vec{v}) = r \cdot \vec{v}$

Mit dem Fixvektor-Konzept lässt sich der Begriff stabile Verteilung wie folgt präzisieren.

Stabile Verteilung

Eine stabile Verteilung bei einem Austauschprozess mit der Prozessmatrix $P$ wird mit einem Verteilungsvektor $\vec{v}$ beschrieben, der ein Fixvektor zur Prozessmatrix $P$ ist. Wir bezeichnen dann $\vec{v}$ auch als stabilen Verteilungsvektor.

Aus den Eigenschaften von Fixvektoren ergibt sich direkt:

Stabile Verteilungen

Ist $\vec{v}$ eine stabile Verteilung bei einem Austauschprozess mit der Prozessmatrix $P$ , dann ist auch jedes Vielfache $r \cdot \vec{v}$ eine stabile Verteilung dieses Austauschprozesses.

Bestimmung stabiler Verteilungen bei Austauschprozessen

Bisher sind wir so vorgegangen, um stabile Verteilungen für einen Austauschprozess zu finden: Wir haben zunächst ausgehend von beliebigen Verteilungen die zugehörigen Grenzverteilungen bestimmt. Dabei sind wir experimentell vorgegangen, indem wir uns diesen Grenzverteilungen (mit einem geeigneten Simulationstool) schrittweise angenähert haben. Mit dem Fixvektor-Konzept eröffnet sich eine neue Möglichkeit, um die stabilen Verteilungen eines Austauschprozesses zu bestimmen. Wir verdeutlichen das Vorgehen am Beispiel des Sharing-Systems.

Folgende Problemsituation liegt vor:

Problem:

Geg.: die Prozessmatrix $P = (\begin{matrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{matrix})$

Ges.: die Fixvektoren $\vec{v} = (\begin{matrix} x \\ y \\ z \end{matrix})$ mit $P \cdot \vec{v} = \vec{v}$

Die Bedingung $P \cdot \vec{v} = \vec{v}$ führt zu einem linearen Gleichungssystem. Ergänze die fehlenden Gleichungen.

$\begin{array}{lrcrcrcr} [1] & 0.8 x & + & 0.1 y & + & 0.3 z & = & x \\ [2] & 0.1 x & + & 0.7 y & + & 0.1 z & = & y \\ [3] & 0.1 x & + & 0.2 y & + & 0.6 z & = & z \end{array}$

Wir verwenden das GeoGebra-CAS zum Lösen dieses Gleichungssystems.

Das von GeoGebra gelieferte Ergebnis lässt sich so deuten:

Das Ergebnis $z = z$ bedeutet, dass man für $z$ eine beliebige reelle Zahl $r$ wählen kann.
Das Ergebnis $y = z$ bedeutet, dass dann $y = r$ gilt.
Das Ergebnis $x = 2 z$ bedeutet, dass dann $x = 2 r$ gilt.

Insgesamt erhält man $\vec{v} = (\begin{matrix} 2 r \\ r \\ r \end{matrix})$ mit einer beliebigen reellen Zahl $r$ .

Es gibt also unendlich viele Fixvektoren zur Prozessmatrix $P$ . Hierzu zählen z.B. die Vektoren $\vec{v} = (\begin{matrix} 150 \\ 75 \\ 75 \end{matrix})$ , $\vec{v} = (\begin{matrix} 200 \\ 100 \\ 100 \end{matrix})$ und $\vec{v} = (\begin{matrix} 0.5 \\ 0.25 \\ 0.25 \end{matrix})$ . Alle diese Vektoren beschreiben stabile Verteilungen zum betrachteten Sharing-System.

Existenz stabiler Verteilungen

Mit dem Satz über die Konvergenz von Austauschprozessen aus dem letzten Kapitel erhält man folgenden Zusammenhang:

Stabile Verteilungen eines Austauschprozesses

Wenn in irgendeiner Potenz der Prozessmatrix $P$ alle Elemente von Null verschieden sind, dann gibt es einen (bis auf Vielfache) eindeutigen Vektor $\vec{v}$ , der (mit seinen Vielfachen) die stabilen Verteilungen des Austauschprozesses beschreibt.