Markov-Kette (Absorption)
Ich habe gerade angefangen, Markov-Kette zu lernen, und ich habe keine Ahnung, wie ich dieses Problem lösen soll
Ein Mann rollt einen Felsbrocken einen 40 Meter hohen Hügel hinauf. Jede Minute schafft er es mit einer Wahrscheinlichkeit von 1/3, den Felsbrocken 1 Meter nach oben zu rollen, während der Felsbrocken mit einer Wahrscheinlichkeit von 2/3 1 Meter nach unten rollt. Wenn sich der Mann derzeit auf halbem Weg zum Gipfel befindet, wie hoch ist die Wahrscheinlichkeit, dass er den Gipfel erreicht, bevor er in die Ausläufer absteigt?
Antworten
Es wäre übertrieben, dieses Problem mithilfe der Markov-Ketten-Theorie zu lösen. Die zugrunde liegenden Konzepte helfen Ihnen jedoch dabei, es so zu gestalten, dass eine einfache Lösung möglich ist.
Das Problem formulieren
Das grundlegendste Konzept ist das eines Staates: Wir können diese Situation anhand von 41 verschiedenen Positionen oder "Zuständen" modellieren, die sich in Abständen von einem Meter Höhe von unten (Höhe -40) bis oben (Höhe 0) von befinden der Hügel. Der aktuelle Zustand auf halber Höhe des Hügels ist eine Höhe von -20.
Das zweite grundlegende Konzept ist das der Unabhängigkeit von vergangenen Ereignissen: Die Chance, was als nächstes passiert, hängt nur vom Staat ab, nicht von Einzelheiten darüber, wie der Mann dorthin gekommen ist. Folglich hängt die Chance, den Gipfel zu erreichen, nur vom Staat ab. Dementsprechend, wenn wir schreiben$s$ Für einen Staat kann die Chance, den Gipfel zu erreichen, einfach geschrieben werden $p(s).$ Wir werden gebeten zu finden $p(-20).$
Aus jedem Staat $s$ zwischen $-40$ und $0$ da ist ein $1/3$ Chance das $s+1$ wird der nächste Staat sein und a $2/3$ Chance das $s-1$wird der nächste Staat sein. Die grundlegendsten Gesetze der bedingten Wahrscheinlichkeit implizieren dann
$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$
Der letzte Schritt der Formulierung des Problems behandelt die Endpunkte oder "absorbierende Zustände". $s=0$ und $s=-40.$ Es sollte klar sein, dass
$$p(0)=1;\ p(-40)=0.\tag{**}$$
Analyse
An diesem Punkt mag die Arbeit beeindruckend aussehen: Wer möchte eine Folge von 40 Gleichungen lösen? Eine schöne Lösungsmethode kombiniert alle Gleichungen zu einem einzigen mathematischen Objekt. Bevor wir fortfahren, möchte ich jedoch darauf hinweisen, dass Sie dieser Analyse nicht folgen müssen: Es reicht aus, zu überprüfen, ob die endgültige Formel (unten hervorgehoben) alle durch das Problem festgelegten Bedingungen erfüllt - und dies ist nur eine Frage von einfache Algebra.
An dieser Stelle ist es hilfreich, das allgemeine Problem zu lösen. Nehmen wir an, es gibt eine Folge von Zuständen$s=0,1,2,\ldots, n$ und dass jeder Staat $s$ zwischen $1$ und $n-1$ Übergänge zu $s-1$ mit Wahrscheinlichkeit $p$ und zu $s+1$ mit Wahrscheinlichkeit $1-p.$ Für alle $s$ Lassen $a_s$ die Chance sein, zum Staat zu gelangen $0$ vor dem Schlagen Zustand $n.$ (Ich habe die vorherige fallen gelassen "$p(-s)$"Notation, weil es zu zu vielen ps führt und ich von Indizierungszuständen mit negativen Zahlen zu Indizierungszuständen mit positiven Zahlen gewechselt bin.)
Wie wir gesehen haben, $a_0=1,$ $a_n=0,$ und ansonsten $a_{s} = pa_{s-1} + (1-p)a_{s+1}$(die "Wiederholungsrelation"). Dieser Satz von Gleichungen wird sauber durch ein Polynom codiert
$$P(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_n t^n = a_0 + \sum_{s=1}^{n} a_s t^s.$$
Einstecken der Wiederholungsrelation und anschließendes Sammeln gemeinsamer Kräfte von $t$ (Schreiben $a_{n+1}=0$ der Einfachheit halber) gibt
$$\begin{aligned} P(t) &= a_0 + \sum_{s=1}^n \left[pa_{s-1} + (1-p)a_{s+1}\right]t^s \\ &= a_0 + p\sum_{s=1}^n a_{s-1} t^s + (1-p)\sum_{s=1}^n a_{s+1}t^s\\ &= a_0 + pt\sum_{s=1}^n a_{s-1} t^{s-1} + \frac{1-p}{t}\sum_{s=1}^n a_{s+1}t^{s+1}\\ &= a_0 + pt\sum_{s=0}^{n-1} a_{s} t^{s} + \frac{1-p}{t}\sum_{s=2}^{n+1} a_{s}t^{s}\\ &= a_0 + pt(P(t) - a_nt^n) + \frac{1-p}{t}(P(t) - a_0 - a_1t) \end{aligned}$$
Dies ist eine einzelne Gleichung für das Polynom$P$ (zumindest bis zu $t^n;$ Ich werde alle Koeffizienten von ignorieren $t^n$oder höhere Potenzen, die erforderlich sein könnten, damit die Gleichung genau funktioniert.) Vereinfachen Sie diese Gleichung ein wenig unter Verwendung der Anfangsbedingung $a_0=1$ und lösen für $P$ bekommen
$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$
Nun jeder Koeffizient von$P$ kann in Form der (noch unbekannten) Zahl ausgedrückt werden $a_1.$ Der Wert von $a_1$ wird durch die Endbedingung bestimmt $a_n=0.$
Eine geschlossene Formel ist möglich, indem die rechte Seite als Teilbruch erweitert wird. Es kommt darauf an zu beobachten
$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$
und Erweitern der Brüche als Summen geometrischer Reihen, die beide in der Form vorliegen
$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$
und multiplizieren Sie das mit dem Zähler $(1-p) + (-1 + (1-p)a_1)t$ erhalten $P(t).$ Dies ergibt eine geschlossene Formel für jeden Begriff in $P(t)$ als Funktion von $a_1.$
Zum $p\ne 1/2$ und schreiben $\lambda = p/(1-p)$ Dieser Ansatz liefert das allgemeine Ergebnis
$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$
zum $s=1, 2, \ldots, n$ (und das funktioniert zufällig für $s=0,$zu). (Wann$p=1/2,$ $\lambda=1$macht diese Formel undefiniert. Sie können jedoch leicht eine einfache Formel herausfinden, indem Sie die Grenze von nehmen$a_s$ wie $\lambda\to 1$ unter Verwendung einer einzigen Anwendung der L'Hopital-Regel.)
Zur Kontrolle ist klar, dass diese Formel gibt $a_0=1$ und $a_n=0.$ Es bleibt zu überprüfen, ob es die Wiederholungsrelation erfüllt, aber das ist eine Frage des Zeigens
$$\frac{\lambda^s - \lambda^n}{1 - \lambda^n} = a_s = pa_{s-1} + (1-p)a_{s+1} = p\frac{\lambda^{s-1} - \lambda^n}{1 - \lambda^n} + (1-p)\frac{\lambda^{s+1} - \lambda^n}{1 - \lambda^n},$$
das ist unkompliziert.
Anwendung
In dem gegebenen Problem $n=40,$ $p=1/3,$ und wir werden gebeten zu finden $a_{20}.$ Folglich $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ und
$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$
Die Erweiterung auf der rechten Seite kann nach den ersten beiden Termen beendet werden, wenn ein Gleitkomma mit doppelter Genauigkeit (mit einer Genauigkeit von) berechnet wird $52$ binäre Orte), geben
$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$
etwas weniger als einer von einer Million.
Stellen Sie sich vor, dass die Bergsteigerreise aus 41 Staaten besteht, einer für jeden möglichen Meter 0, 1, 3, ...., 40. Die Übergangswahrscheinlichkeitsmatrix wird dann zu einer 41 × 41-Matrix, die die unterschiedlichen Wahrscheinlichkeiten für den Übergang von einem Zustand in einen anderen darstellt. Es sieht folgendermaßen aus:
0 1 2 -- 40
0 0 1 0 -- 0
1 2/3 0 1/3 -- 0
2 0 2/3 0 -- 0
| | | | -- |
| | | | -- |
40 0 0 0 -- 0
Nennen wir diese Matrix P. Wenn wir bei 20 Metern beginnen, mit anderen Worten bei Zustand 20, können wir dies als einen Vektor (41 Elemente lang) mit den Wahrscheinlichkeiten des Starts in jedem Zustand darstellen, der aufgerufen uwird u=[0,0, ... , 0, 1, 0 ... 0, 0], wobei die 1eine 100% ige Wahrscheinlichkeit darstellen, bei 20 Metern zu beginnen .
Die Matrixmultiplikation wird u*Pdann zu der Wahrscheinlichkeit, im Zeitschritt t + 1 in allen anderen Zuständen zu landen . Wenn wir diese Matrixmultiplikation immer wieder durchführen, u*P^twobei t gegen unendlich geht, erreichen wir eine stationäre Matrix P *. Diese stationäre Matrix repräsentiert die Wahrscheinlichkeiten, in allen anderen Zuständen zu landen.
In Ihrem Fall würden Sie diese Matrixmultiplikation also viele Male in einer Programmiersprache Ihrer Wahl durchführen (z. B. 100+), und Sie würden einfach nachschlagen P[20,40], was Ihnen die Wahrscheinlichkeit geben würde, bei 20 Metern zu beginnen und alles zu machen Weg auf dem Hügel!