Austauschprozesse

Übergangsgraph

Wie bereits erwähnt, findet bei einem Austauschprozess ein Austausch zwischen verschiedenen Zuständen statt. Mithilfe eines Übergangsgraphen kann dies veranschaulicht werden. Dabei werden die jeweiligen Umverteilungen der Zustände in einem gewissen zeitlichen Verlauf dargestellt. Wir betrachten dafür ein Beispiel.

Beispiel

Anhand eines Übergangsgraphen soll das Einkaufsverhalten verschiedener Personen in einer Kleinstadt verdeutlicht werden. In der Kleinstadt leben Menschen, die in der Nähe in den Supermärkten A, B und C einkaufen können. Nicht alle Personen kaufen die Lebensmittel immer in den gleichen Läden ein, sondern wechseln ständig. Die nachfolgende Tabelle zeigt das monatliche Wechselverhalten der Kunden in den Supermärkten.

	von A	von B	von C
zu A	60%	20%	10%
zu B	30%	70%	20%
zu C	10%	10%	70%
	100%	100%	100%

Es zeigt sich daraus beispielsweise, dass Personen, die in den Supermarkt A gegangen sind, im nächsten Monat wieder zu 60% in den Supermarkt A gehen werden. Der Rest wechselt zu den Supermärkten B und C.Dieser Austausch zwischen den einzelnen Supermärkten kann mithilfe eines sogenannten Übergangsgraphen dargestellt werden. Wichtig dabei ist die angegebene Zeitangabe und die richtige Zuordnung (von - zu). Wir beginnen dabei zunächst mit der ersten Spalte (von A). In der folgenden Abbildung ist der monatliche Austausch vom Supermarkt A zu den Supermärkten A, B und C zu sehen.

Übergangsgraph

Mit den übrigen Spalten kann ebenso verfahren werden, woraus der nachfolgende komplette Übergangsgraph dargestellt werden kann.

Übergangsgraph komplett

Dieser Übergangsgraph bzw. das Übergangsdiagramm dienen dazu eine sogenannte Übergangsmatrix M zu erstellen.

Übergangsmatrix

Falls bereits eine Tabelle mit dem Austausch zwischen den verschiedenen Zuständen angegeben ist, lässt sich die Übergangsmatrix einfach ablesen. Es kann jedoch vorkommen, dass zunächst nur der Übergangsgraph angegeben ist und daraus die Übergangsmatix M hergeleitet werden soll. Dafür werden die jeweiligen Zustände mithilfe einer Tabelle ausgedrückt. In unserem Beispiel können die Werte entweder direkt aus der Tabelle übernommen (nicht als Prozentwert!) oder aus dem Übergangsgraphen abgeleitet werden.

Achtung: In Summe müssen die jeweiligen Spalten immer 1 ergeben. Wenn dies nicht der Fall ist, kontrolliere deine Werte in der Tabelle.

Aus dieser Form lässt sich nun die Übergangsmatrix M ablesen, indem die Tabellenwerte als Koeffizienten übernommen werden.

Diese Übergangsmatrix M dient jetzt zur Berechnung, wie viele Personen entweder in den Monaten zuvor oder auch in den folgenden Monaten in den jeweiligen Supermärkten einkaufen gehen.

Zukünftiger und vergangener Austausch

Grundsätzlich kann dabei unterschieden werden, ob berechnet werden soll was in Zukunft passiert (vorwärts) oder was in der Vergangenheit passiert ist (rückwärts.) Wir werden uns nachfolgend beide Fälle ansehen.

Zukünftiger Austausch (vorwärts)

Soll beispielsweise die Verteilung im nächsten Monat berechnet werden, so wird das Produkt aus dem aktuellen Anteil und der Wechselwahrscheinlichkeit gebildet. Allgemein lässt sich dieser Zustand wie folgt als Gleichung darstellen.

Wollen wir also wissen, was in unserem Beispiel im nächsten Monat passiert, dann müssen wir die aktuelle Verteilung mit der Übergangsmatrix M multiplizieren.

Beispiel Fortsetzung

Im Monat Mai kaufen von 1000 Personen 350 Personen im Supermarkt A und 400 Personen im Supermarkt B ein. Die restlichen Personen gehen in den Supermarkt C. Dies ist die aktuelle Verteilung und kann als Vektor wie folgt ausgedrückt werden:

Interessiert uns jetzt die Verteilung des darauffolgenden Monats Juni, so bilden wir das Produkt des Vektors mit der Übergangsmatrix. Für Juni:

Die Verteilung im Monat Juni erhalten wir durch die Multiplikation. Falls dir die Regeln der Matrizenrechnung nicht (mehr) klar sind, lies einfach im entsprechenden Kapitel noch einmal nach. Nach der Berechnung erhalten wir:

Wollen wir jetzt zudem noch die Verteilung im Monat Juli wissen, so muss die Übergangsmatrix mit der neuen Verteilung multipliziert werden. Dies bedeutet allgemein und für unser Beispiel:

Es fällt auf, dass sich der Wert von A bei der zukünftigen Verteilung jeweils reduziert, sich der Wert von B erhöht und der Wert von C gleich bleibt. Damit stellt sich die Frage, ob der Austausch unbegrenzt fortgesetzt werden kann. Der Antwort dieser Frage widmen wir uns später. Zunächst erklären wir noch die Berechnung von vergangenen Verteilungen.

Vergangener Austausch (rückwärts)

Neben den Verteilungen in den zukünftigen Monaten können ebenfalls auch die Verteilungen in den vergangenen Monaten berechnet werden. Anders als zuvor wird der aktuelle Zustand als Ergebnis des Produkts verwendet. Allgemein lässt sich dies wie folgt formulieren:

Um die vergangene Verteilung berechnen zu können gibt es hierbei zwei Möglichkeiten, auf die wir nachfolgend eingehen werden.

1. Lineares Gleichungssystem

Aus der Matrizengleichung des Austauschprozesses lässt sich ein lineares Gleichungssystem ablesen, das anschließend gelöst werden kann. Zur Veranschaulichung verwenden wir wieder unser Beispiel von oben.

Beispiel Fortsetzung

Im Monat Mai gab es folgende aktuelle Verteilung:

Um die vergangene Verteilung des Monats April ermitteln zu können, wird zunächst die Matrizengleichung aufgestellt.

Das Gleichungssystem lautet damit wie folgt:

Durch Lösen des linearen Gleichungssystem kann der Austauschprozess für den Monat April berechnet werden und wir erhalten als Lösung:

2. Inverse Matrix

Die Verteilung des Monat April aus dem Austauschprozess kann ebenfalls mithilfe der inversen Matrix berechnet werden. Dafür muss zunächst die Matrizengleichung umgestellt werden. Kurz zur Erinnerung der Inversen:

Wir erhalten damit:

Beispiel Fortsetzung

Durch Berechnung der inversen Übergangsmatrix erhalten wir:

Achtung: Gerundete Werte bei der inversen Matrix!

Die vergangene Verteilung des Monats April ergibt sich dann aus der Multiplikation.

Beide Möglichkeiten zur Berechnung des Austauschprozesses sind möglich. Jedoch sind lineare Gleichungssysteme weniger fehleranfällig und einfacher zu berechnen.

Stationäre Verteilung und Grenzmatrix

Wir haben damit bereits einige zukünftige und vergangene Verteilungen berechnet. Jedoch ist immer noch die Frage offen, ob dieser Prozess der Berechnung unbegrenzt weiter geführt werden kann.

Gibt es eine Verteilung, für die gilt, dann wird diese als stationäre oder auch stabile Verteilung bezeichnet. In diesem Fall ändert sich der Zustand durch die Multiplikation der Übergangsmatrix M nicht mehr.

Wird der Vorgang für das Vorwärtsrechnen immer weiter wiederholt, so kann sich unabhängig vom Startvektor eine stabile Verteilung, die sogenannte Grenzverteilung, einstellen, ab dem sich die Werte durch die Multiplikation nicht mehr ändern und es gilt:

Die Grenzverteilung ist damit also ebenfalls eine stationäre Verteilung. Sie exisitiert aber nicht für jeden Ausgangszustand.

In diesem Zuge ist auch die sogenannte Grenzmatrix zu nennen. Durch wiederholte Multiplikation der Übergangsmatrix mit sich selbst, kann sich diese ebenfalls einer Grenze annähern. Es gilt damit:

Somit kann durch Multiplikation eines beliebigen Startvektors mit der Grenzmatrix auch direkt die Grenzverteilung ermittelt werden.

Häufig wird in typischen Aufgaben zum Austauschprozess direkt nach dem stationären Vektor oder Fixvektor gefragt. Berechnen lässt sich dieser wieder mithilfe des linearen Gleichungssystems.

Beispiel Fortsetzung

Für die Berechnung des stationären Vektors muss die Bedingung erfüllt sein. In unserem Beispiel gilt also:

Daraus lässt sich wieder das lineare Gleichungssystem aufstellen.

Bei der Lösung dieses Gleichungssystems müssen wir leider feststellen, das dieses keine eindeutige Lösung liefert. Den Fixvektor erhalten wir jedoch nur, falls eine korrekte Lösung existiert. Daher wird das Gleichungssystem umgewandelt:

Anschließend wird der Vektor anhand einer bestimmten Variable (zum Beispiel C) dargestellt. Die notwendigen Umformungen dafür sind:

Nach Einsetzen von B in Gleichung I und Einsetzen von A in Gleichung II, sowie Einsetzen von A und B in Gleichung III erhalten wir:

Da wir wissen, dass es sich in unserem Beispiel um ingesamt 1000 Personen handelt, gilt:

Nach Auflösen dieser Gleichung nach C erhalten wir:

Nun wird nur noch das Ergebnis für die Berechnung des gesuchten stationären Vektors eingesetzt.

Somit haben wir alle wichtigen Grundlagen zu den Austauschprozessen und deren Berechnung gelernt. Nachfolgend findest du noch eine kurze Übersicht mit den wichtigsten Informationen

Austauschprozesse - Alles Wichtige auf einen Blick

• Ein Austauschprozess ist ein System mit verschiedenen Zuständen, zwischen denen ein Austausch stattfindet.
• Mithilfe eines Übergangsgraphen können die Umverteilungen der Zustände in einem festgelegten Zeitraum betrachtet werden.
• Aus dem Übergangsgraphen lässt sich die Übergangsmatrix M ableiten, die für Berechnungen zum Austauschprozess notwendig ist.
• Bei der Berechnungen ist zwischen zeitlich vorwärts und zeitlich rückwärts zu unterscheiden.
• Der zukünftige Zustand wird durch Multiplikationmit dem aktuellen Zustand zeitlich vorwärts gerechnet:
  • 
• Der vergangeneZustand wird durch zeitlichen rückwärts rechnen ermittelt.
  • 
• Zeitlich rückwärtsrechnen erfolgt durch:
  • Lineares Gleichungssystem oder
  • Inverse Übergangsmatrix
• Gibt es einen Zustand für den gilt , so wird dieser stationärer Zustand bezeichnet.
• Der zugehörige stationäre Vektor oder auch Fixvektor kann durch Umformungen eines linearen Gleichungssystems ermittelt werden.