Biorąc pod uwagę dwa absorbujące łańcuchy Markowa, jakie jest prawdopodobieństwo, że jeden zakończy się przed drugim?

9

Mam dwa różne łańcuchy Markowa, każdy z jednym stanem pochłaniania i znaną pozycją początkową. Chcę określić prawdopodobieństwo, że łańcuch 1 osiągnie stan pochłaniania w mniejszej liczbie kroków niż łańcuch 2.

Myślę, że mogę obliczyć prawdopodobieństwo osiągnięcia stanu pochłaniania w danym łańcuchu po n krokach: biorąc pod uwagę macierz przejściową prawdopodobieństwo pochłonięcia po krokach wynosi gdzie jest stanem początkowym, a jest stan pochłaniający.PnPijnij

Nie jestem jednak pewien, dokąd się udać. Analogiczne problemy, które widziałem, dotyczą kości (np. Rzucenie sumą 7 przed sumą 8), ale jest to łatwiejsze do rozwiązania, ponieważ prawdopodobieństwo wyrzucenia określonej sumy jest stałe i niezależne od liczby wykonanych do tej pory kroków.

Jeff
źródło

Odpowiedzi:

13

Prowadź łańcuchy równolegle. Zdefiniuj trzy stany pochłaniania w powstałym łańcuchu produktów:

  1. Pierwszy łańcuch osiąga stan pochłaniania, a drugi nie.

  2. Drugi łańcuch osiąga stan pochłaniania, ale pierwszy nie.

  3. Oba łańcuchy jednocześnie osiągają stan pochłaniania.

Ograniczające prawdopodobieństwa tych trzech stanów w łańcuchu produktów dają szanse na zainteresowanie.


To rozwiązanie obejmuje niektóre (proste) konstrukcje. Podobnie jak w pytaniu pozwolić jest macierzą transformacji dla łańcucha . Gdy łańcuch znajduje się w stanie , podaje prawdopodobieństwo przejścia do stanu . Stan pochłaniający powoduje przejście do siebie z prawdopodobieństwem .P=Pij,1i,jnPiPijj1

  1. Dowolny stan może zostać pochłonięty po zastąpieniu wiersza przez wektor wskaźnika z w pozycji .iPi=(Pij,j=1,2,,n)(0,0,,0,1,0,,0)1i
  2. Każdy zestaw stanów pochłaniających mogą być połączone , tworząc nowy łańcuch , którego stany są . Macierz przejścia podano przezAP/A{ja|jaZA}{ZA}

    (P./ZA)jajot={P.jajotjaZA,jotZAkZAP.jakjaZA,jot=ZA0ja=ZA,jotZA1ja=jot=ZA.

    Sprowadza się to do zsumowania kolumn odpowiadających i zastąpienia wierszy odpowiadających pojedynczym wierszem, który tworzy przejście do siebie.P.ZAZA

  3. Produkt z dwóch łańcuchów na stany i na stany z przejściem matryce i odpowiednio, jest łańcuchem Markowa na stwierdza z macierzą przejściaP.S.P.QS.QP.QS.P.×S.Q={(p,q)|pS.P.,qS.Q}

    (P.Q)(ja,jot),(k,l)=P.jakQjotl.

    W efekcie łańcuch produktów prowadzi równolegle dwa łańcuchy, osobno śledząc, gdzie każdy z nich, i wykonując przejścia niezależnie.


Prosty przykład może wyjaśnić te konstrukcje. Załóżmy, że Polly rzuca monetą z szansą lądowania głów. Planuje to zrobić, dopóki nie zobaczy głowy. Stany procesu monetą to reprezentujący wyniki ostatniego rzutu: dla ogonów, dla głów. Planując zatrzymać się przy głowach, Polly zastosuje pierwszą konstrukcję, czyniąc stanem absorbującym. Wynikowa macierz przejścia topS.P.={T.,H.}T.H.H.

P.=(1-pp01).

Zaczyna się w losowym stanie podanym przy pierwszym rzucie.(1-p,p)

Z czasem z Polly Quincy rzuci uczciwą monetą. Planuje się zatrzymać, gdy zobaczy dwie głowy z rzędu. Jego łańcuch Markowa musi zatem śledzić zarówno poprzedni, jak i bieżący wynik. Istnieją cztery takie kombinacje dwóch głów i dwóch ogonów, które będę skracać jako „ ”, na przykład, gdzie pierwsza litera to poprzedni wynik, a druga litera to obecny wynik. Quincy stosuje konstrukcję (1), aby był stanem absorbującym. Po zrobieniu tego zdaje sobie sprawę, że tak naprawdę nie potrzebuje czterech stanów: może uprościć swój łańcuch do trzech stanów: oznacza, że ​​obecny wynik to reszka, oznacza, że ​​bieżącym wynikiem jest szef, iTHHHT.H.X oznacza, że ​​ostatnie dwa wyniki były główami - to jest stan pochłaniania. Macierz przejścia to

Q=(12)12)012)012)001).

Łańcuch produktów działa w sześciu stanach: . Macierz transformacji jest produkt napinacz z i i równie łatwo obliczona. Na przykład to szansa, że ​​Polly przejdzie z do i, w w tym samym czasie (i niezależnie) Quincy dokonuje przejścia ze do . Pierwszy ma szansę a drugi . Ponieważ łańcuchy są uruchamiane niezależnie, szanse te się mnożą, dając(T.,T.),(T.,H.),(T.,X);(H.,T.),(H.,H.),(H.,X)P.Q(P.Q)(T.,T.),(T.,H.)T.T.T.H.1-p1/2)(1-p)/2) . Pełna macierz przejścia to

P.Q=(1-p2)1-p2)0p2)p2)01-p2)01-p2)p2)0p2)001-p00p00012)12)000012)012)000001).

Ma postać macierzy bloków, a bloki odpowiadają drugiej macierzy :Q

P.Q=(P.11QP.12QP.21QP.22Q)=((1-p)QpQ0Q).

Polly i Quincy rywalizują ze sobą, aby zobaczyć, kto osiągnie swój cel jako pierwszy. Zwycięzcą zostanie Polly za każdym razem, gdy nastąpi przejście do gdzie nie jest ; zwycięzcą zostanie Quincy za każdym razem, gdy nastąpi przejście do ; i jeśli zanim którekolwiek z nich się zdarzy, nastąpi przejście do , wynikiem będzie remis. Aby to śledzić, stworzymy stany i absorbujące (poprzez konstrukcję (1)), a następnie scalimy je ( poprzez budowę (2)). Powstała macierz przejścia uporządkowana według stanów(H.,*)*X(T.,X)(H.,X)(H.,T.)(H.,H.)(T,T.),(T.,H.),(T.,X),{(H.,T.),(H.,H.)},(H.,X) jest

R=(1-p2)1-p2)0p01-p2)01-p2)p2)p2)001000001000001).

Wyniki jednoczesnego pierwszego rzutu przez Polly i Quincy będą stany z prawdopodobieństwami , odpowiednio: jest to stan początkowy, w którym należy rozpocząć łańcuch.(T.,T.),(T.,H.),(T.,X),{(H.,T.),(H.,H.)},(H.,X)μ=((1-p)/2),(1-p)/2),0,p,0)

W limicie od ,n

μRn11+4p-p2)(0,0,(1-p)2),p(5-p),p(1-p)).

Tak więc względne szanse trzech stanów absorpcji (reprezentujących wygrane Quincy, wygrane Polly, losują) wynoszą .(T.,X),{(H.,T.),(H.,H.)},(H.,X)(1-p)2):p(5-p):p(1-p)

Postać

W zależności od (szansa, że ​​którykolwiek z rzutów Polly zostanie głową), czerwona krzywa przedstawia szansę na wygraną Polly, niebieska krzywa przedstawia szansę wygranej Quincy, a złota krzywa przedstawia losowanie.p

Whuber
źródło
1
Bardzo fajny przykład, dzięki za to. Nadal pracuję nad szczegółami, aby je zobaczyć na własne oczy. Tylko pytanie: tutaj założyliśmy, że dwa wydarzenia (rzuty Polly i Quincy) miały miejsce jednocześnie, ile by to zmieniło, gdybyśmy zrobili je sekwencyjnie, a nawet wybraliśmy losowo za każdym razem, kto rzuciłby następny?
user929304
1
@ user929304 Otrzymasz różne odpowiedzi, prawdopodobnie w znacznym stopniu. Załóżmy na przykład, że P i Q działają w łańcuchu, w którym stany są podzielone na podzbiory A i B, w których wszystkie przejścia z A idą do B, a wszystkie z B idą do A. Niech P i Q zaczynają się od stanów w A. oba łańcuchy produktu naprzemiennie zmieniają się między A i B, ale łańcuchy sekwencyjny i losowy wybierają ten niezmienny wzór.
whuber