Łańcuch Markowa (Absorpcja)

Question

Właśnie zacząłem uczyć się łańcucha Markowa i nie mam pojęcia, jak rozwiązać ten problem

Mężczyzna stacza głaz na 40-metrowe wzgórze. Co minutę z prawdopodobieństwem 1/3 udaje mu się stoczyć głaz o 1 metr w górę, natomiast z prawdopodobieństwem 2/3 głaz stacza się o 1 metr w dół. Jeśli mężczyzna jest obecnie w połowie drogi do szczytu, jakie jest prawdopodobieństwo, że dotrze na szczyt przed zejściem do podnóża?

Answer 1

Byłoby przesadą rozwiązywanie tego problemu za pomocą teorii Łańcucha Markowa: ale podstawowe pojęcia pomogą ci sformułować to w sposób, który dopuszcza proste rozwiązanie.

Sformułowanie problemu

Najbardziej fundamentalną koncepcją jest stan: możemy modelować tę sytuację w kategoriach 41 odrębnych pozycji lub „stanów” usytuowanych w odstępach co 1 metr od dołu (wysokość -40) do szczytu (wysokość 0) Wzgórze. Obecny stan, w połowie drogi pod górę, to wysokość -20.

Drugą podstawową koncepcją jest niezależność od wydarzeń z przeszłości: szansa na to, co stanie się później, zależy tylko od państwa, a nie od szczegółów dotyczących tego, jak człowiek się tam dostał. W konsekwencji szansa zdobycia szczytu zależy tylko od państwa. W związku z tym, jeśli napiszemy$s$ dla państwa szansę zdobycia szczytu można po prostu napisać $p(s).$ Jesteśmy proszeni o znalezienie $p(-20).$

Z dowolnego stanu $s$ pomiędzy $-40$ i $0$ tam jest $1/3$ szansa na to $s+1$ będzie następnym stanem i $2/3$ szansa na to $s-1$będzie następnym stanem. Implikują zatem najbardziej podstawowe prawa prawdopodobieństwa warunkowego

$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$

Ostatni etap formułowania problemu dotyczy punktów końcowych lub „stanów wchłaniania” $s=0$ i $s=-40.$ To powinno być jasne

$$p(0)=1;\ p(-40)=0.\tag{**}$$

Analiza

W tym momencie praca może wyglądać groźnie: kto chce rozwiązać sekwencję 40 równań? Ładna metoda rozwiązania łączy wszystkie równania w jeden obiekt matematyczny. Ale zanim przejdziemy dalej, pozwólcie, że zauważę, że nie trzeba postępować zgodnie z tą analizą: wystarczy sprawdzić, czy ostateczna formuła (zaznaczona poniżej) spełnia wszystkie warunki postawione przez problem - i to tylko kwestia prosta algebra.

W tym momencie pomocne jest rozwiązanie ogólnego problemu. Załóżmy, że istnieje sekwencja stanów$s=0,1,2,\ldots, n$ i że każdy stan $s$ pomiędzy $1$ i $n-1$ przejścia do $s-1$ z prawdopodobieństwem $p$ i do $s+1$ z prawdopodobieństwem $1-p.$ Dla wszystkich $s$ pozwolić $a_s$ być szansą na dotarcie do stanu $0$ przed uderzeniem w stan $n.$ (Porzuciłem poprzednią "$p(-s)$"notacja, ponieważ prowadzi do zbyt wielu p i przeszedłem ze stanów indeksowania z liczbami ujemnymi na indeksowanie ich liczbami dodatnimi).

Jak widzieliśmy, $a_0=1,$ $a_n=0,$ i w innym znaczeniu $a_{s} = pa_{s-1} + (1-p)a_{s+1}$(„relacja nawrotu”). Ten zestaw równań jest starannie zakodowany przez wielomian

$$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.$$

Podłączenie relacji rekurencji, a następnie zebranie wspólnych uprawnień $t$ (pisanie $a_{n+1}=0$ dla wygody) daje

$$\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}$$

To jest pojedyncze równanie wielomianu$P$ (przynajmniej do $t^n;$ Zignoruję wszelkie współczynniki $t^n$lub wyższe potęgi, które mogą być potrzebne, aby równanie działało dokładnie). Uprość nieco to równanie, używając warunku początkowego $a_0=1$ i rozwiąż $P$ dostać

$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$

Teraz każdy współczynnik$P$ można wyrazić w postaci (wciąż nieznanej) liczby $a_1.$ Wartość $a_1$ zależy od końcowego warunku $a_n=0.$

Formuła zamknięta jest możliwa poprzez rozszerzenie prawej strony jako częściowego ułamka. Sprowadza się do obserwacji

$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$

i rozszerzanie ułamków jako sumy szeregów geometrycznych, z których oba mają postać

$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$

i pomnożenie tego przez licznik $(1-p) + (-1 + (1-p)a_1)t$ pozyskać $P(t).$ Daje to zamkniętą formułę dla każdego terminu w $P(t)$ jako funkcja $a_1.$

Dla $p\ne 1/2$ i pisanie $\lambda = p/(1-p)$ takie podejście daje ogólny rezultat

$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$

dla $s=1, 2, \ldots, n$ (i to działa $s=0,$też). (Gdy$p=1/2,$ $\lambda=1$sprawia, że ​​ta formuła jest niezdefiniowana. Możesz jednak łatwo zrozumieć prostą formułę, przyjmując granicę$a_s$ tak jak $\lambda\to 1$ za pomocą jednej aplikacji L'Hopital's Rule.)

Dla sprawdzenia jest jasne, że ta formuła daje $a_0=1$ i $a_n=0.$ Pozostaje zweryfikować, czy spełnia relację powtarzania, ale to kwestia pokazania

$$\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},$$

co jest proste.

Podanie

W zadanym problemie $n=40,$ $p=1/3,$ i jesteśmy proszeni o znalezienie $a_{20}.$ w konsekwencji $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ i

$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$

Rozwinięcie po prawej stronie może zostać zakończone po pierwszych dwóch wyrazach podczas obliczania w podwójnej precyzji zmiennoprzecinkowej (która ma dokładność $52$ miejsca binarne), dając

$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$

trochę mniej niż jeden na milion.

Answer 2

Wyobraź sobie, że podróż wspinaczkowa składa się z 41 stanów, po jednym na każdy możliwy metr, więc stwierdza 0, 1, 3, ...., 40. Macierz prawdopodobieństwa przejścia staje się wówczas macierzą 41x41, reprezentującą różne prawdopodobieństwa przejścia z jednego stanu do drugiego. Wygląda to następująco:

   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

Nazwijmy tę macierz P. Jeśli uruchomić na 20 metrów, innymi słowami w stanie 20 można reprezentowania jako wektor (41 elementów długości) z prawdopodobieństw wychodząc w każdym stanie, nazywanych u, u=[0,0, ... , 0, 1, 0 ... 0, 0]w przypadku gdy 1stanowią 100% prawdopodobieństwo zaczynając od 20 metrów .

Mnożenie macierzy u*Pstaje się następnie prawdopodobieństwem znalezienia się we wszystkich innych stanach w kroku czasowym t +1. Jeśli będziemy kontynuować mnożenie macierzy w kółko, u*P^tgdzie t zmierza w kierunku nieskończoności, osiągniemy macierz stanu ustalonego P *. Ta macierz stanu ustalonego przedstawia prawdopodobieństwo znalezienia się we wszystkich innych stanach.

Więc w twoim przypadku wykonałbyś to mnożenie macierzy wiele razy w wybranym przez siebie języku programowania (np. 100+) i po prostu spojrzałbyś w górę P[20,40], co dałoby prawdopodobieństwo rozpoczęcia od 20 metrów i zrobienia wszystkiego na szczycie wzgórza!