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 | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
$P = \begin{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix}$ |
Grenzverteilung als stabile Verteilung
Wenn man den Austauschprozess simuliert, erhält man (für beliebige Ausgangsverteilungen) immer eine feste Grenzverteilung. Die folgende Übersicht verdeutlich das exemplarisch.
| Schritte | Verteilungsvektor |
|---|---|
| $0$ | $\vec{v}_{0} = \begin{pmatrix} 100 \\ 100 \\ 100 \end{pmatrix}\quad$ (Ausgangsverteilung) |
| $1$ | $\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} = \begin{pmatrix} 120 \\ 80 \\ 80 \end{pmatrix}$ |
| $2$ | $\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} = \begin{pmatrix} 132 \\ 84 \\ 84 \end{pmatrix}$ |
| ... | ... |
| $n$ | $\vec{v}_n = P \cdot \vec{v}_{n-1} \quad$ für $n \geq 1$ |
| ... | ... |
| $\downarrow$ | |
| $\infty$ | $\vec{v}_{\infty} = \begin{pmatrix} 150 \\ 75 \\ 75 \end{pmatrix} \quad$ (Grenzverteilung) |
Wenn man die Grenzverteilung als Ausgangsverteilung nimmt, dann ändert sich die Verteilung bei einem Simulationsschritt nicht.
$\underbrace{\begin{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix}}_{P} \cdot \underbrace{ \begin{pmatrix} 150 \\ 75 \\ 75 \end{pmatrix}}_{\vec{v}_{\infty}} = \underbrace{ \begin{pmatrix} 150 \\ 75 \\ 75 \end{pmatrix}}_{\vec{v}_{\infty}}$
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{pmatrix} 0.8 & 0.1 & 0.3 \\ 0.1 & 0.7 & 0.1 \\ 0.1 & 0.2 & 0.6 \end{pmatrix}$
Ges.: die Fixvektoren $\vec{v} = \begin{pmatrix} x \\ y \\ z \end{pmatrix}$ 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] &\quad 0.8 x & + & 0.1 y & + & 0.3 z & = & x \\ [2] &\quad 0.1 x & + & 0.7 y & + & 0.1 z & = & x \\ [3] &\quad 0.1 x & + & 0.2 y & + & 0.6 z & = & x \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 = 2z$ bedeutet, dass dann $x = 2r$ gilt.
Insgesamt erhält man $\vec{v} = \begin{pmatrix} 2r \\ r \\ r \end{pmatrix}$ 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{pmatrix} 150 \\ 75 \\ 75 \end{pmatrix}$, $\vec{v} = \begin{pmatrix} 200 \\ 100 \\ 100 \end{pmatrix}$ und $\vec{v} = \begin{pmatrix} 0.5 \\ 0.25 \\ 0.25 \end{pmatrix}$. 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.
