Übergangsmatrix bei Computerspiel

16.02.2022, 09:04

MMchen60

Übergangsmatrix bei Computerspiel

Liebe Forumsgemeinde,
nachfolgend mal eine Aufgabe in der Stochastik mit Matrizenrechnung.

https://www.fit-in-mathe-online.de/images/technikerforum/webinarloesung-hannah-gysbers.png
Ich habe da schon mal die Übergangsmatrix nach meiner Vorstellung aufgestellt, weiß aber nicht ob das richtig ist.
Zur Frage b) bin ich der Meinung, dass das 0,6 * 0,4 * 0,2 = 0,048 sein müsste, oder?
Bei Frage c) und d) hapert es jetzt doch bei mir.
Muss ich da den Startvektor bilden mit etwa $\begin{eqnarray*} \vec {v_0}= \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{eqnarray*}$ und dann mit der Matrix merhrmals multiplizieren oder so? Nur, der Startvektor kann doch da nicht immer derselbe sien. Oder muss ich bei c) die Übergangsmatrix einfach hoch 6 nehmen?
Und wie überhaupt mache ich das bei d) ?
Danke für Hilfe.

16.02.2022, 09:13

HAL 9000

Auf diesen Beitrag antworten »

Die Ü-Matrix ist falsch: "Falls der Aufstieg nicht gelingt, bleibt der Spieler im erreichten Level" bedeutet, man bleibt auf der Spielstufe oder geht nach oben - aber es geht keinesfalls nach unten. D.h., die Dreiecksmatrix unterhalb der Hauptdiagonale ist komplett 0.

Das Spielende kann man so modellieren, dass man in Zustand 4 verbleibt, d.h. Wahrscheinlichkeit 1 für den Übergang 4->4.

Außerdem: Eine Ü-Matrix ist eine stochastische Matrix, d.h., sämtliche Einträge sind $\begin{eqnarray*} \geq 0 \end{eqnarray*}$ und alle Zeilensummen sind jeweils gleich 1.

Zitat:

Original von MMchen60
Zur Frage b) bin ich der Meinung, dass das 0,6 * 0,4 * 0,2 = 0,048 sein müsste, oder?

Nein, das ist die Wahrscheinlichkeit nach 3 Spielrunden, wenn jeweils immer der Aufstieg gelingt. Bei 4 Spielrunden darf man sich auch eine Pause gönnen, gleich auf welcher Stufe - sowas lässt sich sehr gut mit Potenzen der Ü-Matrix $\begin{eqnarray*} U \end{eqnarray*}$ ausdrücken.

16.02.2022, 09:23

MMchen60

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Die Ü-Matrix ist falsch:

OK, und wäre die richtig?
Falls ja, wie geht das dann weiter?

https://www.fit-in-mathe-online.de/images/technikerforum/hannah-gysbers-2.png

16.02.2022, 09:34

HAL 9000

Auf diesen Beitrag antworten »

$\begin{eqnarray*} v_0^T U^n =: v_n^T \end{eqnarray*}$ gibt den Wahrscheinlichkeitsvektor der Aufenthaltswahrscheinlichkeiten in den Zuständen 1-4 nach genau $\begin{eqnarray*} n \end{eqnarray*}$ Spielrunden an. Startvektor ist bei b),c) dann $\begin{eqnarray*} v_0^T=(1,0,0,0) \end{eqnarray*}$ .

Besonderes Augenmerk liegt dann natürlich auf der letzten Komponente von $\begin{eqnarray*} v_n^T \end{eqnarray*}$ , denn die gibt die Wahrscheinlichkeit von Endzustand 4 dann an. Das ist dann aber wohlgemerkt nicht die Wahrscheinlichkeit, erst in diesem letzten $\begin{eqnarray*} n \end{eqnarray*}$ -ten Schritt den Zustand 4 erreicht zu haben, sondern die Wahrscheinlichkeit, dass das bis dahin geschehen ist (also ggfs. bereits in einer früheren Spielrunde).

16.02.2022, 09:48

MMchen60

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
$\begin{eqnarray*} v_0^T U^n =: v_n^T \end{eqnarray*}$ gibt den Wahrscheinlichkeitsvektor der Aufenthaltswahrscheinlichkeiten in den Zuständen 1-4 nach genau $\begin{eqnarray*} n \end{eqnarray*}$ Spielrunden an. Startvektor ist bei b),c) dann $\begin{eqnarray*} v_0^T=(1,0,0,0) \end{eqnarray*}$ .

Verstehe ich das richtig: Wenn ich $\begin{eqnarray*} v_0^T \cdot U^1 \end{eqnarray*}$ bilde erhalte ich $\begin{eqnarray*} v_1^T \end{eqnarray*}$ mit zugehöriger Übergangsmatrix U^1 ?

16.02.2022, 10:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MMchen60
Wenn ich $\begin{eqnarray*} v_0^T \cdot U^1 \end{eqnarray*}$ bilde erhalte ich $\begin{eqnarray*} v_1^T \end{eqnarray*}$ ~~mit zugehöriger Übergangsmatrix U^1~~ ?

Das Ergebnis ist der Wkt-Vektor, nichts anderes.

--------------------------------------------------------------------------------

Für einen klaren Überblick, was bei großen $\begin{eqnarray*} n \end{eqnarray*}$ passiert, kann man auch eine Diagonalisierung der Ü-Matrix in Betracht ziehen. Die kann hier z.B.so aussehen

$\begin{eqnarray*} U = T\Lambda T^{-1} \end{eqnarray*}$ mit $\begin{eqnarray*} \Lambda = \begin{pmatrix} 0.4 & 0 & 0 & 0\\ 0 & 0.6 & 0 & 0\\ 0 & 0 & 0.8 & 0\\ 0 & 0 & 0 & 1\end{pmatrix} \end{eqnarray*}$ sowie $\begin{eqnarray*} T = \begin{pmatrix} 1 & 3 & 3 & 1\\ 0 & 1 & 2 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\end{pmatrix} \end{eqnarray*}$ , für die gilt dann übrigens $\begin{eqnarray*} T^{-1} = \begin{pmatrix} 1 & -3 & 3 & 1\\ 0 & 1 & -2 & 1\\ 0 & 0 & 1 & -1\\ 0 & 0 & 0 & 1\end{pmatrix} \end{eqnarray*}$ .

Das bedeutet schlussendlich

$\begin{eqnarray*} U^n &=& T \Lambda^n T^{-1} = \begin{pmatrix} 1 & 3 & 3 & 1\\ 0 & 1 & 2 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1\end{pmatrix} \begin{pmatrix} 0.4^n & 0 & 0 & 0\\ 0 & 0.6^n & 0 & 0\\ 0 & 0 & 0.8^n & 0\\ 0 & 0 & 0 & 1\end{pmatrix} \begin{pmatrix} 1 & -3 & 3 & 1\\ 0 & 1 & -2 & 1\\ 0 & 0 & 1 & -1\\ 0 & 0 & 0 & 1\end{pmatrix}\\ &=& \begin{pmatrix} 0.4^n & 3\cdot 0.6^n-3\cdot 0.4^n & 3\cdot 0.8^n-6\cdot 0.6^n+3\cdot 0.4^n & 1-3\cdot 0.8^n+3\cdot 0.6^n-0.4^n\\ 0 & 0.6^n & 2\cdot 0.8^n-2\cdot 0.6^n & 1-2\cdot 0.8^n+0.6^n\\ 0 & 0 & 0.8^n & 1-0.8^n\\ 0 & 0 & 0 & 1\end{pmatrix} \end{eqnarray*}$

Bezogen auf die Anschlussfrage in d) bekommt man somit Wkt $\begin{eqnarray*} 1-2\cdot 0.8^n+0.6^n =: f(n) \end{eqnarray*}$ .

17.02.2022, 09:37

MMchen60

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Für einen klaren Überblick, was bei großen $\begin{eqnarray*} n \end{eqnarray*}$ passiert, kann man auch eine Diagonalisierung der Ü-Matrix in Betracht ziehen.

Sorry, wenn ich jetzt blöd nachfrage, was ist $\begin{eqnarray*} \Lambda \end{eqnarray*}$ und wie kommt man dahin? Und wie kommt man zu deinem T ? (Klar Diagonalisierung, habe ich versucht mit meiner Übergangsmatrix, komme aber da nicht weiter).
Grüße
Meinolf

17.02.2022, 10:10

MMchen60

Auf diesen Beitrag antworten »

Zitat:

Original von MMchen60
Sorry, wenn ich jetzt blöd nachfrage,

Hallo, habe mir das mit der Diagonalisierung nochmal per Video angeschaut, Eigenvektor usw. usw. Bei der fraglichen Aufgabe geht es um eine Abituraufgabe. Ich kenne aber kein Bundesland, in dem die Diagonalisierung im Lehrplan steht. Ist denn diese Aufgabe nicht einfacher zu lösen?
Viele Grüße
Meinolf

17.02.2022, 10:12

HAL 9000

Auf diesen Beitrag antworten »

Wenn dir der aus der linearen Algebra kommende Begriff "Diagonalisierung einer Matrix" nichts sagt, dann vergiss das ganze - selbstverständlich sind diese Rechnungen nur Zugabe, d.h., waren nicht wirklich in dieser Aufgabe gefordert. Natürlich kann man die in b),c),d) benötigten Matrizen $\begin{eqnarray*} U^n \end{eqnarray*}$ für $\begin{eqnarray*} n=4,6,10 \end{eqnarray*}$ auch zu Fuß berechnen, durch sukzessive Matrixmultiplikationen (ein diesbezüglich intelligentes Vorgehen wäre die sukzessive Berechnung von $\begin{eqnarray*} U^2=U\cdot U \end{eqnarray*}$ , dann $\begin{eqnarray*} U^4 = U^2\cdot U^2 \end{eqnarray*}$ , $\begin{eqnarray*} U^6 = U^4\cdot U^2 \end{eqnarray*}$ und schließlich $\begin{eqnarray*} U^{10} = U^6\cdot U^4 \end{eqnarray*}$ , d.h. insgesamt vier solche Matrixmultiplikationen).

Bei der Zusatzfrage "auf lange Sicht" in d) wollen die Aufgabensteller vermutlich nur hören, dass diese Wahrscheinlichkeit dann gegen 1 konvergiert. Das genauere approximative Verhalten $\begin{eqnarray*} \approx 1-2\cdot 0.8^n \end{eqnarray*}$ dieser Wahrscheinlichkeit kann man dem entsprechenden Matrixeintrag in den Potenzen $\begin{eqnarray*} U^2,U^4,U^6,U^{10} \end{eqnarray*}$ vermutlich noch nicht ansehen. Augenzwinkern

Falls du dich doch reinvertiefen willst: $\begin{eqnarray*} \Lambda \end{eqnarray*}$ ist die zugehörige Diagonalmatrix der Eigenwerte von $\begin{eqnarray*} U \end{eqnarray*}$ . Wie man oben sieht, ist eine solche Diagonalisierung $\begin{eqnarray*} U = T\Lambda T^{-1} \end{eqnarray*}$ vorteilhaft, wenn man höhere bzw. überhaupt allgemein die Potenz $\begin{eqnarray*} U^n \end{eqnarray*}$ bestimmen will:

Denn dann gilt $\begin{eqnarray*} U^n = T \Lambda^n T^{-1} \end{eqnarray*}$ , wobei $\begin{eqnarray*} \Lambda^n \end{eqnarray*}$ besonders einfach zu berechnen ist, weil man einfach nur alle Diagonalenelemente mit $\begin{eqnarray*} n \end{eqnarray*}$ potenzieren muss, und an den restlichen Positionen die Nullen bleiben, d.h. auch $\begin{eqnarray*} \Lambda^n \end{eqnarray*}$ eine Diagonalmatrix ist.

Neue Frage »

Antworten »

Übergangsmatrix bei Computerspiel

Verwandte Themen