Austauschprozesse

Themen auf dieser Seite

Eine typische Aufgabe in Klausuren ist das Thema Austauschprozesse. Hierbei gibt es einige Dinge, die ihr beachten müsst.

In der Regel ist ein Übergangsgraph gegeben, aus dem ihr eine Matrix erstellen sollt. Achtet immer auf den Zeitraum, der angegeben ist. Das ist wichtig für eure Antworten (z.B. monatlich, Woche zu Woche etc.)!

Es kann auch sein, dass die Matrix gegeben ist und ihr den Übergangsgraphen zeichnen sollt. Am sinnvollsten ist es, als Zwischenschritt eine Tabelle aufzustellen, damit das Fehlerrisiko reduziert wird.

Im Folgenden werden wir die einzelnen Komponenten zum Thema Austauschprozesse erläutern.

 

Übergangsgraph/-diagramm

Übergangsgraphen sind spezielle gerichtete Graphen mit sogenannten Kantengewichten, die eine Verbindung zwischen Stochastik und Graphentheorie schlagen. In der folgenden Abbildung ist ein Übergangsgraph bzw. ein Übergangsdiagramm dargestellt, der die wöchentliche Wahl des Lieblingsfaches darstellen soll. Wichtig ist die zeitliche Angabe – hier: wöchentlich! Aus diesem Graphen lässt sich eine Tabelle erstellen. Achte auf die Zuordnung: von – nach!

Austauschprozesse

Wichtig hierbei ist, dass die Spaltensumme immer 1 ergeben muss! Wenn nicht, kontrolliert dann nochmal, ob ihr alles richtig gemacht habt.

 

Übergangsmatrix ablesen

Aus der Tabellenform nun auf die Übergangsmatrix M kommen – die Matrix steht da quasi schon! Einfach die Zahlenwerte hinschreiben, Klammer drum und fertig!

Doch wie werden die Koeffizienten der Übergangsmatrix interpretiert? Wir betrachten die Koeffizienten m_{11} und m_{23} und versuchen diese zu interpretieren.

Übergangsmatrix ablesen - Austauschprozesse

  • m_{11} – von Mathe zu Mathe: Schüler, die Mathe als Lieblingsfach gewählt hat, werden in der nächsten Woche mit einer 50-prozentigen Wahrscheinlichkeit wieder Mathe als Lieblingsfach wählen.
  • m_{32} – von Englisch zu Sport: Schüler, die Englisch als Lieblingsfach gewählt hat, werden in der nächsten Woche mit einer 20-prozentigen Wahrscheinlichkeit Sport als Lieblingsfach wählen.

 

Zeitlich Vorwärtsrechnen

Wenn wir nun wissen wollen, was in der nächsten Woche passiert, stellen wir folgende Gleichung auf:

    \begin{align*} \left( \begin{array}{ccc} 0,5 & 0,4 & 0,1 \\ 0,3 & 0,4 & 0,6 \\ 0,2 & 0,2 & 0,3 \end{array} \right) \cdot \underbrace{\left( \begin{array}{c} m \\ s \\ e \end{array} \right)}_{\parbox{1.5cm}{\textrm{Verteilung JETZT}}} = \underbrace{\left( \begin{array}{c} m' \\ s' \\ e' \end{array} \right)}_{\parbox{3cm}{\textrm{Verteilung beim nächsten Mal}}} \quad (1) \end{align*}

Der Vektor (m,s,e)^T gibt die Verteilung der Lieblingsfächer Mathe, Sport und Englisch zum Zeitpunkt „jetzt“ an. Oft findet ihr in Büchern oder Aufgaben eine allgemeinere Form:

    \begin{align*} \left( \begin{array}{ccc} \cdots & & \\ \vdots & \ddots & \\ & & \end{array} \right) \cdot \left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} x' \\ y' \\ z' \end{array} \right) \notag \end{align*}

Wichtig ist, dass der Vektor (x,y,z)^T die gleiche Reihenfolge wie in der Tabelle hat!

Was passiert, wenn wir die Verteilung beim übernächsten Mal (x'' \ y'' \ z'')^T bestimmen wollen? Hier gibt es zwei Möglichkeiten:

  1. Möglichkeit

        \begin{align*}M \cdot\left( \begin{array}{c} x \\ y \\ z \end{array} \right) =\left( \begin{array}{c} x' \\ y' \\ z' \end{array} \right) \quad \textrm{und dann} \quadM \cdot\left( \begin{array}{c} x' \\ y' \\ z' \end{array} \right) =\left( \begin{array}{c} x'' \\ y'' \\ z'' \end{array} \right) \notag\end{align*}

  2. Möglichkeit – Übergangsmatrix M im Vorfeld multiplizieren (siehe Abschnitt Matrix mal Matrix).

        \begin{align*}M\cdot M = M^2 \quad \Rightarrow \quadM^2 \cdot\left( \begin{array}{c} x \\ y \\ z \end{array} \right) =\left( \begin{array}{c} x'' \\ y'' \\ z'' \end{array} \right), \notag\end{align*}

    wobei wir bei der Interpretation der Koeffizienten der Übergangsmatrix M^2 aufpassen müssen. Diese beschreibt nun nicht mehr die wöchentlichen Übergangswahrscheinlich-keiten zur Wahl des Lieblingsfaches, sondern die für 2 Wochen! Der Zeitraum hat sich geändert.

 

Daniel fasst alles zum Thema Austauschprozesse nochmals in diesem Lernvideo zusammen.

Austauschprozess, Übergangsmatrix, Übergangsgraph, Matrizen, Matrix | Mathe by Daniel Jung

 

Zeitlich Rückwärtsrechnen (mit LGS oder inverser Matrix)

Schau dir zur Wiederholung nochmal das Video zur inversen Matrix an.

Inverse Matrix zum "Rückwärts"-Rechnen bei Übergangsprozessen | Mathe by Daniel Jung

Oder das Lernvideo zu Linearen Gleichungssystemen

Übergangsmatrizen/-prozesse, "Rückwärtsrechnen", letzte Verteilung | Mathe by Daniel Jung

Wie war es beim letzten Mal? Diese Frage kann theoretisch auch vorkommen und sollte für euch kein Problem darstellen. Bleiben wir bei unserem Beispiel mit dem Lieblingsfach. Die Übergangsmatrix M entnehmen wir von oben, die Verteilung der Lieblingsfächer zum jetzigen Zeitpunkt sei 20 für Mathe, 10 für Sport, 3 bei Englisch. Wir betrachten nun Gl. (1) und tragen die gegebenen Werte wie folgt ein:

    \begin{align*} \left( \begin{array}{ccc} 0,5 & 0,4 & 0,1 \\ 0,3 & 0,4 & 0,6 \\ 0,2 & 0,2 & 0,3 \end{array} \right) \cdot \underbrace{\left( \begin{array}{c} m \\ s \\ e \end{array} \right)}_{\parbox{1.5cm}{\textrm{Verteilung letzte Woche}}} = \underbrace{\left( \begin{array}{c} 20 \\ 10 \\ 3 \end{array} \right)}_{\parbox{3cm}{\textrm{Verteilung in dieser Woche}}} \notag \end{align*}

Wir haben nun folgende Möglichkeiten:

  1.  LGS aufstellen und lösen – am einfachsten mit dem Taschenrechner!
  2. Gleichung M \cdot \vec{x}_{vor} = \vec{x} umstellen zu \vec{x}_{vor} = M^{-1} \cdot \vec{x}! Hierfür benötigen wir die Inverse der Matrix M. Anschließend können wir die Verteilung zum letzten Mal sehr einfach ausrechnen.

Einschub: Inverse Matrix bestimmen

Wenn man eine Matrix A mit ihrer inversen Matrix A^{−1} multipliziert, entsteht die Einheitsmatrix. Denkt an die Welt der normalen Zahlen: Multipliziert man eine Zahl mit ihrem Kehrwert, lautet das Ergebnis stets 1. Was für Zahlen funktioniert, geht auch ähnlich bei Matrizen. Es gilt: A \cdot A^{-1} = A^{-1} \cdot A=1.

Im Wesentlichen gibt es zwei Verfahren zur Bestimmung der Inversen Matrix:

  1. Inverse bestimmen mit Hilfe des Gauß-Jordan-Algorithmus
  2. Invers bestimmen mit Hilfe der Adjunkten – nur sinnvoll bei 2 \times 2 Matrizen!

        \begin{align*} A^{-1} = \frac{1}{|A|} \cdot Adj(A) \label{eq:InvAdj} \end{align*}

    Vorgehen:

(i) Berechne die Determinante von A = \begin{pmatrix} {{a}} & {{b}}\\ {{c}} & {{d}} \end{pmatrix}. Wenn die Determinante von A gleich Null ist, gibt es keine Inverse und du kannst mit dem Rechnen aufhören.

(ii) Ist die Determinante von A ungleich Null, berechne die Adjunkte.

    \begin{align*} \operatorname{adj} (A) = \begin{pmatrix} \,\,\,{{d}} & \!\!{{-b}}\\ {{-c}} & {{a}} \end{pmatrix} \notag \end{align*}

(iii) Setze die Zwischenergebnisse in die Formel zur Berechnung der inversen Matrix ein

Nur quadratische Matrizen können eine Inverse besitzen. Jedoch existiert nicht für jede quadratische Matrix eine Inverse. Falls für eine Matrix A die Inverse existiert, so heißt die Matrix regulär – andernfalls heißt sie singulär.

Rechenregeln:

  • \left(A \cdot B\right)^{-1} = B^{-1} \cdot A^{-1}
  • \left(A^{T}\right)^{-1} = \left(A^{-1}\right)^{T}
  • \left(A^{-1}\right)^{-1} = A
  • \left(k \cdot A\right)^{-1} = k^{-1} \cdot A^{-1}

Wenn wir eine 3 \times 3 Matrix vorliegen haben, sollte man entweder seinen Taschenrechner bedienen können, oder den guten Gauß-Jordan-Algorithmus beherrschen.
Hier ein Beispiel: Bestimme die Inverse zur reellen Matrix

    \begin{align*} A = \begin{pmatrix} 1 & 2 & 0 \\ 2 & 4 & 1 \\ 2 & 1 & 0 \end{pmatrix} \quad \Rightarrow \quad \begin{array}{c} \textrm{I} \\ \textrm{II} \\ \textrm{III} \end{array} \left(\begin{array}{ccc|ccc} 1 & 2 & 0 \, & \, 1 & 0 & 0 \\ { 2} & 4 & 1 \, & \, 0 & 1 & 0 \\ { 2} & 1 & 0 \, & \, 0 & 0 & 1 \end{array}\right) \notag \end{align*}

Die Idee ist es, die Einheitsmatrix von der rechten Seite auf die linke Seite zu bringen. Das schaffen wir, in dem wir die linke Seite mit dem Additionsverfahren so zu verändern, dass nur auf der Diagonalen 1en stehen und sonst 0en.
Zunächst werden hier die beiden 2-en in der ersten Spalte eliminiert, indem wir \textrm{II} - 2 \cdot \textrm{I} und \textrm{III} - 2 \cdot \textrm{I} rechnen. Nachdem in der zweiten Spalte nun eine 0 steht, wird zur Elimination der -3 die zweite mit der dritten Zeile vertauscht und man erhält die obere Dreiecksform:

    \begin{align*} \rightarrow \left(\begin{array}{ccc|ccc} 1 & 2 & 0 \, & \, 1 & 0 & 0 \\ 0 & 0 & 1 \, & \, -2 & 1 & 0 \\ 0 & { -3} & 0 \, & \, -2 & 0 & 1 \end{array}\right) \rightarrow \left(\begin{array}{ccc|ccc} 1 & 2 & 0 \, & \, 1 & 0 & 0 \\ 0 & -3 & 0 \, & \, -2 & 0 & 1 \\ 0 & 0 & 1 \, & \, -2 & 1 & 0 \end{array}\right). \notag \end{align*}

Nun muss lediglich die verbleibende 2 oberhalb der Diagonalen zu Null gesetzt werden, was durch Addition des Doppelten der zweiten Zeile zum Dreifachen der ersten Zeile geschieht. Schließlich muss noch die erste Zeile durch 3 und die zweite Zeile durch -3 dividiert werden und man erhält als Ergebnis:

    \begin{align*} \left(\begin{array}{ccc|ccc} 1 & 2& 0 \, & \, 1 & 0 & 0 \\ 0 & -3 & 0 \, & \, -2 & 0 & 1 \\ 0 & 0 & 1 \, & \, -2 & 1 & 0 \end{array}\right) \rightarrow \left(\begin{array}{ccc|ccc} { 3} & 0 & 0 \, & \, -1 & 0 & 2 \\ 0 & { -3} & 0 \, & \, -2 & 0 & 1 \\ 0 & 0 & 1 \, & \, -2 & 1 & 0 \end{array}\right) \rightarrow \left(\begin{array}{ccc|ccc} 1 & 0 & 0 \, & \, -\tfrac13 & 0 & \tfrac23 \\ 0 & 1 & 0 \, & \, \tfrac23 & 0 & -\tfrac13 \\ 0 & 0 & 1 \, & \, -2 & 1 & 0 \end{array}\right). \notag \end{align*}

Die Inverse von A ist demnach:

    \begin{align*} A^{-1} = \begin{pmatrix} -\tfrac13 & 0 & \tfrac23 \\ \tfrac23 & 0 & -\tfrac13 \\ -2 & 1 & 0 \end{pmatrix} = \frac{1}{3} \begin{pmatrix} -1 & 0 & 2 \\ 2 & 0 & -1 \\ -6 & 3 & 0 \end{pmatrix}. \notag \end{align*}

 

Begriff Fixvektor, stabiler Vektor

Ein Fixvektor beschreibt einen stabilen Zustand, also einen Zustand, der sich durch Anwenden der Übergangsmatrix nicht mehr ändert. Dieser Zustand wird auch „stationärer“ Zustand genannt. Häufig wird in Aufgaben verlangt, den Fixvektor zu einem gegebenem System zu bestimmen bzw. erst seine Existenz zu überprüfen.

Mathematisch betrachtet ist der Vektor \vec{v}=(a\ b\ c)^T gesucht, für den gilt M\cdot \vec{v} = \vec{v}. Dieser kann (wenn es ihn denn gibt) aus dem zugehörigen Gleichungssystem allgemein bestimmt werden. In einem zweiten Schritt kann dann der zu einem gegebenen Zustandsvektor \vec{v_0} = (150\ 240\ 120)^T gehörige Fixvektor bestimmt werden.

Beispiel  Gegeben sei folgende Übergangsmatrix M. Der Fixvektor ist gesucht.

    \begin{align*} M = \begin{pmatrix} 0,6 & 0,05 & 0,3 \\ 0,1 & 0,8 & 0,2 \\ 0,3 & 0,15 & 0,5 \end{pmatrix} \notag \end{align*}

Aus der Bedingung M\cdot \vec{v} = \vec{v} ergibt sich das folgende Gleichungssystem:

    \begin{align*} \begin{array}{rcrcrcll} 0,6 a &+& 0,05 b &+& 0,3 c &= &a & |-a \\ 0,1 a &+& 0,8 b &+& 0,2 c &=& b & |-b \\ 0,3 a &+& 0,15 b &+& 0,5 c &=& c & |-c \end{array} \Leftrightarrow \begin{array}{rcrcrcl} -0,4 a &+& 0,05 b &+& 0,3 c &= &0 \\ 0,1 a &-& 0,2 b &+& 0,2 c &=&0 \\ 0,3 a &+& 0,15 b &-& 0,5 c &=& 0 \end{array} \end{align*}

Wenn wir versuchen das LGS zu lösen, sei es per Hand oder mit dem TR, bekommen wir keine eindeutige Lösung heraus, sondern alles in Abhängigkeit einer Unbekannten.

Wichtig: Es gibt nur dann eine stationäre Verteilung, wenn die Lösung des Gleichungssystems eine wahre Aussage ist, z.B. 0=0!

Wir geben die Lösung also in Abhängigkeit eines Parameters, hier c, an und erhalten damit den allgemeinen Fixvektor:

    \begin{align*} \vec{v} = \begin{pmatrix} a \\ b \\ c \end{pmatrix} = \begin{pmatrix} \frac{14}{15}~c \\[0.2cm] \frac{22}{15}~c \\ c \end{pmatrix} \notag \end{align*}

Den zu unserem Zustandsvektor \vec{v}_0 gehörende Fixvektor bekommen wir, indem wir die Informationen aus \vec{v}_0 als weitere Gleichung dazu nehmen. Es gilt

    \begin{align*} a + b + c = 150 + 240 + 120 = 510 \quad \textrm{und damit auch} \quad \frac{14}{15}c + \frac{22}{15}c + c = 510 \notag \end{align*}

Wenn wir die Gleichung nach c auflösen erhalten wir für c=150 und damit den Fixvektor \vec{v}_F zum Zustandsvektor \vec{v}_0

    \begin{align*} \vec{v_{F}}= \begin{pmatrix} 140 \\ 220 \\ 150 \end{pmatrix}. \notag \end{align*}

Eine weitere Möglichkeit den Fixvektor zu bestimmen, ist die wiederholte Multiplikation der Übergangsmatrix mit sich selbst. Wenn sich die Werte der Matrix stabilisieren, kann man Spaltenweise den Fixvektor ablesen. Beispiel:

    \begin{align*} M^{100} = \begin{pmatrix} 0,5 & 0,5 & 0,5 \\ 0,2 & 0,2 & 0,2 \\ 0,3 & 0,3 & 0,3 \end{pmatrix} \quad \Rightarrow \vec{v}=\begin{pmatrix} 0,5 \\ 0,2 \\ 0,3 \end{pmatrix} \end{align*}