Suche

Drucken Drucken

Übergangsmatrizen

Mit Übergangsmatrizen bezeichnet man die Darstellung von beispielsweise Wanderungsbewegungen oder Entwicklungen von Tierpopulationen. In der Regel sind diese Matrizen quadratisch.

Abbildung 1: Ein Übergangsgraph

Nehmen wir ein Beispiel mit Wanderungsbewegungen zwischen drei Baumärkten A, B und C. Dabei werden die Entscheidungen der Käufer im Vergleich von einer Woche zur nächsten betrachtet. Die Wanderungsbewegungen werden durch den Übergangsgraphen in Abbildung 1 dargestellt. Dieser Graph ist so zu lesen, dass beispielsweise 60% der Besucher von Baumarkt A in der folgenden Woche wieder im Baumarkt A kaufen, 30% im Baumarkt B und 10% im Baumarkt C. In dieser Darstellung gibt es weder die Möglichkeit, dass Käufer hinzu kommen, noch dass Käufer in der nächsten Woche nicht mehr kaufen. Dieser Wanderungsbewegung kann man als Übergangsmatrix darstellen. Dabei stehen in der oberen Zeile die Baumärkte, in denen die Kunden in dieser Woche sind und in der linken Spalte die Baumärkte, in die sie in der nächsten Woche sind.

Die Tabelle, die zum Übergangsgraphen in Abbildung 1 gehört, hat folgende Form:

 
   A
   B
   C
 A
0,6
0,2
0,1
 B
0,3
0,4
0,2
 C
0,1
0,4
0,7

Die zugehörige Übergangsmatrix sieht wie folgt aus:

\begin{pmatrix}0,6&0,2&0,1\\0,3&0,4&0,2\\0,1&0,4&0,7\end{pmatrix}

In diesem Beispiel addieren sich die einzelnen Elemente einer Spalte immer zu 1, weil weder Käufer dazu kommen, noch welche aus dem System fallen. Eine solche Übergangsmatrix, bei der sich die Spaltenelemente zu 1 addieren, nennt man stochastische Matrix. Dies ist aber nicht zwangsläufig in allen Beispielen so. Sollten Käufer in den Markt eintreten, könnten Spaltensummen von größer 1 entstehen, sollten Käufer den Markt verlassen, könnten die Spaltensummen unter 1 sinken.

Die Verteilungen in zukünftigen Wochen

Ausgehend von einer Situation, in der von 1500 Kunden je 500 einen der drei Baumärkte besuchen, soll die Verteilung in der nächsten Woche ermittelt werden. Die aktuelle Verteilung der Kunden kann durch den Vektor

    \[ \vec{v}=\begin{pmatrix}500\\500\\500\end{pmatrix}\]

dargestellt werden. Um die Verteilung der folgenden Woche zu errechnen, wird die Matrix

    \[M \begin{pmatrix}0,6&0,2&0,1\\0,3&0,4&0,2\\0,1&0,4&0,7\end{pmatrix}\]

mit dem Ausgangsvektor multipliziert:

 
\begin{pmatrix}500\\500\\500\end{pmatrix}
\begin{pmatrix}0,6&0,2&0,1\\0,3&0,4&0,2\\0,1&0,4&0,7\end{pmatrix}
\begin{pmatrix}450\\450\\600\end{pmatrix}

Nach einer Woche sind je 450 Kunden bei den Baumärkten A und B und 600 beim Baumarkt C. Das Ergebnis, das sich eine weitere Woche später ergibt, kann man auf zwei Wegen errechnen. Entweder multipliziert man die Übergangsmatrix mit dem Vektor der Käuferverteilung, die sich nach einer Woche ergeben hat. Oder man multipliziert die Übergangsmatrix mit sich selbst und erhält so M^2. Diese Matrix hat in diesem Beispiel die Form:

 
 
\begin{pmatrix}0,6&0,2&0,1\\0,3&0,4&0,2\\0,1&0,4&0,7\end{pmatrix}
\begin{pmatrix}0,6&0,2&0,1\\0,3&0,4&0,2\\0,1&0,4&0,7\end{pmatrix}
\begin{pmatrix}0,43&0,24&0,17\\0,32&0,3&0,25\\0,25&0,46&0,58\end{pmatrix}

 

M^2 beschreibt das Wechselverhalten der Käufer von der einen zur übernächsten Woche. So sind von 100 Käufern, die am Anfang in den Baumarkt A gegangen sind, nach zwei Wochen 32 beim Baumarkt B gelandet und 43 sind im Baumarkt A geblieben. Egal welchen der beiden beschriebenen Wege man einschlägt, im gewählten Beispiel ist die Verteilung der Käufer auf die Baumärkte nach zwei Wochen (420/435/645).

Verteilungen in der Vergangenheit

Die nächste Frage, die wir behandeln wollen, ist die, ob es eine Verteilung gibt, die nach einer Woche die Verteilung (500/500/500) ergibt. Es wird jetzt also nach der Lösung des folgenden Problems gesucht:

    \[M*\begin{pmatrix}A\\B\\C\end{pmatrix}=\begin{pmatrix}500\\500\\500\end{pmatrix}.\]

Um den Vektor (A/B/C) zu bestimmen, multipliziert man den Vektor (500/500/500) mit der inversen Matrix von M  – M^{-1}. Zur Übung bestimmen wir die Inverse der Übergangsmatrix. Dabei wird das gesamte System im ersten Schritt mit 10 multipliziert, um mit ganzen Zahlen arbeiten zu können.

 
\text{I}_a=10*\text{I} 6 2 1 10 0 0
\text{II}_a=10*\text{II} 3 4 2 0 10 0
\text{III}_a=10*\text{III} 1 4 7 0 0 10
 

Als nächstes schaffen wir in der zweiten Spalte zwei Nullen:

 
\text{I}_a 6 2 1 10 0 0
\text{II}_b=\text{II}_a-\frac{1}{2}*\text{I}_a 0 3 \frac{3}{2} -5 10 0
\text{III}_b=\text{III}_a-\frac{1}{6}\text{I}_a 0 \frac{11}{3} \frac{41}{6} -\frac{5}{3} 0 10
 

Nun entstehen in der dritten Spalte zwei Nullen:

 
\text{I}_b=\text{I}_a-\frac{2}{3}\text{II}_b 6 0 0 \frac{40}{3} -\frac{20}{3} 0
\text{II}_b 0 3 \frac{3}{2} -5 10 0
\text{III}_c=\text{III}_b-\frac{11}{9}\text{II}_b 0 0 5 \frac{40}{9} -\frac{110}{9} 10
 

Und nun in der vierten Spalte:

 
\text{I}_b 6 0 0 \frac{40}{3} -\frac{20}{3} 0
\text{II}_c=\text{II}_b-\frac{3}{10}\text{III}_c 0 3 0 -\frac{19}{3} \frac{41}{3} -3
\text{III}_c 0 0 5 \frac{40}{9} -\frac{110}{9} 10
 

Abschließend werden die Zeilen dividiert:

 
\text{I}_c=\frac{1}{6}\text{I}_b 1 0 0 \frac{20}{9} -\frac{10}{9} 0
\text{II}_d=\frac{1}{3}\text{II}_c 0 1 0 -\frac{19}{9} \frac{41}{9} -1
\text{III}_d=\frac{1}{5}\text{III}_c 0 0 1 \frac{8}{9} -\frac{22}{9} 2
 

Multipliziert man diese Inverse mit dem Vektor (500/500/500), so erhält man mit (556/722/22) die Verteilung, die zu der Verteilung (500/500/500) geführt hat.

Stabile Verteilung

Wir können uns fragen, ob die Wanderungsbewegung der Käufer gegen eine stabile Verteilung tendiert. In diesem Fall gibt es eine solche stabile Verteilung, da wir eine stochastische Matrix betrachten. Die stabile Verteilung wird berechnet, wenn man die Urspungsmatrix oft mit sich selbst multipliziert. In diesem Beispiel gilt:

    \[A^{10}=\begin{pmatrix}0.2574702258&0.2563473926&0.2558598013\\0.2823722049&0.2820322642&0.2818846136\\0.4601575693&0.4616203432&0.4622555851\end{pmatrix}.\]

Die stabile Verteilung kann man ablesen, wenn sich die Werte in den einzelnen Zeilen nicht mehr stark voneinander unterscheiden. Somit dürfte eine stabile Verteilung hier so aussehen, dass etwas mehr als 25% der Käufer zu Baumarkt A gehen, etwas mehr als 28% zu Baumarkt B und etwas mehr als 46% zu Baumarkt C. Ein genaueres Ergebnis erhält man, wenn man die Matrix A noch öfter mit sich selbst multipliziert.

Bei Entwicklungen von Populationen, ist es sinnvoll die Matrix so oft mit sich selbst zu multiplizieren, wie es Entwicklungsschritte in einer Population gibt. Beispiel: später

Sich reproduzierende Verteilung

Eine sich reproduzierende Verteilung ist eine Verteilung von Käufern, die sich nicht mehr ändert. Diese Lösung nennt man auch ein (stabiles) Gleichgewicht oder einen Fixvektor. Gesucht ist der Vektor, der nach Multiplikation mit der Matrix sich selbst als Ergebnis hat:

    \[M*\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}.\]

Zusätzlich benötigen wir eine Bedingung, die die Lösung (0/0/0) als einzige Lösung verhindert. Hier ist dies, dass sich 1500 Kunden auf die Baumärkte verteilen.{{1}}[[1]]Bei Berechnungen mit Anteilen hat man oft die Bedingung, dass sich alle Anteile zu 1 addieren. Ansonsten kann man auch eine Lösung mit einer Formvariable erstelln.[[1]] Schreibt man das Mulitplikationsproblem als Gleichungssystem, so erhält man:

    \begin{eqnarray*}0,6x_1+0,2x_2+0,1x_3&=&x_1\\0,3x_1+0,4x_2+0,2x_3&=&x_2\\0,1x_1+0,4x_2+0,7x_3&=&x_3\\x_1+x_2+x_3&=&1500.\end{eqnarray*}

Umformen der vierten Gleichung nach x_1 und Einsetzen auf der rechten Seite der ersten Gleichung ergibt:{{2}}[[2]]Die vierte Gleichung kann auch nach jeder anderen der drei Variablen umgeformt werden und an einer anderen Stelle im Gleichungssystem eingesetzt werden.[[2]]

    \begin{eqnarray*}0,6x_1+1,2x_2+1,1x_3&=&1500\\0,3x_1-0,6x_2+0,2x_3&=&0\\0,1x_1+0,4x_2-0,3x_3&=&0.\end{eqnarray*}

Das Lösen dieses Gleichungssystems führt zu dem Gleichgewicht (385/423/692).

Ist die Anzahl der Käufer nicht vorgegeben, dann sucht man eine Lösung mit einer Formvariablen. Das Gleichungssystem wird aufgestellt

    \begin{eqnarray*}0,6x_1+0,2x_2+0,1x_3&=&x_1\\0,3x_1+0,4x_2+0,2x_3&=&x_2\\0,1x_1+0,4x_2+0,7x_3&=&x_3\end{eqnarray*}

und alle Variablen auf die linke Seite geholt:

    \begin{eqnarray*}-0,4x_1+0,2x_2+0,1x_3&=&0\\0,3x_1-0,6x_2+0,2x_3&=&0\\0,1x_1+0,4x_2-0,3x_3&=&0.\end{eqnarray*}

Eine Addition dieser drei Gleichungen führt zu 0=0; es gibt also unendlich viele Lösungen. Im nächsten Schritt werden zwei Gleichungen so addiert, dass im Ergebnis eine Variable weniger vorkommt. So können wir hier die zweite Gleichung vom Dreifachen der dritten Gleichung subtrahieren, um x_1 zu eliminieren. Es ergibt sich

(1)   \begin{eqnarray*}&&1,8x_2-1,1x_3=0\\&\Longleftrightarrow&1,8x_2=1,1x_3.\end{eqnarray**}

Dabei ist es an dieser Stelle für die Lösung unerheblich welche Gleichungen verrechnet und welche Variable eliminiert wird. An dieser Stelle wird die Formvariable t eingeführt. Diese kann beliebig gewählt werden. Wir wählen an dieser Stelle x_3=18t, damit es im ersten Schritt keine Brüche gibt. Damit ergibt sich x_2=11t und nach Einsetzen in eine der ursprünglichen Gleichungen x_1=10t. Der Lösungsvektor hat damit folgendes Aussehen:

    \[\vector{x}= \begin{pmatrix}10\\11\\18\end{pmatrix} t.\]

Wählt man nun t=\frac{1500}{10+11+18}, dann ergibt sich – bis auf Rundungsfehler – die Lösung von oben. Die Wahl eines anderen Weges – sei es, dass zwei andere Gleichungen benutzt werden, um eine Variable zu eliminieren, sei es, dass eine andere Variable eliminiert wird, sei es, dass t anders definiert wird – führt zu einem Ergebnis, dass inhaltlich dem hier gefundenen entspricht: Der andere Lösungsvektor und der hier gefundene werden linear abhängig sein.

Drucken Drucken

Schreibe einen Kommentar