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

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. $P$ $n$ $P^n_{ij}$ $i$ $j$

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.

probability markov-chain transition-matrix

— Jeff
źródło

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

Pierwszy łańcuch osiąga stan pochłaniania, a drugi nie.
Drugi łańcuch osiąga stan pochłaniania, ale pierwszy nie.
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 . $\mathbb{P} = P_{ij}, 1 \le i,j\le n$ $\mathcal P$ $i$ $P_{ij}$ $j$ $1$

Dowolny stan może zostać pochłonięty po zastąpieniu wiersza przez wektor wskaźnika z w pozycji . $i$ $\mathbb{P}_{i} = (P_{ij}, j=1, 2, \ldots,n)$ $(0,0,\ldots,0,1,0,\ldots,0)$ $1$ $i$
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 przez $A$ $\mathcal{P}/A$ $\{i\,|\, i\notin A\}\cup \{A\}$

$(P. / ZA)_{ja jot} = \begin{array}{ll} {\begin{cases} {P.}_{ja jot} & ja \notin ZA, jot \notin ZA \\ \sum_{k \in ZA} {P.}_{ja k} & ja \notin ZA, jot = ZA \\ 0 & ja = ZA, jot \notin ZA \\ 1 & ja = jot = ZA . \end{cases} \end{array}$ $(\mathbb{P}/A)_{ij} = \begin{array}{ll} \left\{ \begin{array}{ll} P_{ij} & i \notin A,\, j \notin A\\ \sum_{k\in A} P_{ik} & i\notin A, j=A \\ 0 & i=A, j\notin A \\ 1 & i = j = A. \end{array}\right. \end{array}$
Sprowadza się to do zsumowania kolumn odpowiadających i zastąpienia wierszy odpowiadających pojedynczym wierszem, który tworzy przejście do siebie. $\mathbb{P}$ $A$ $A$
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ścia $\mathcal{P}$ $S_P$ $\mathcal{Q}$ $S_Q$ $\mathbb{P}$ $\mathbb{Q}$ $S_P\times S_Q = \{(p,q)\,|\, p\in S_P, q\in S_Q\}$

$(P. \otimes Q)_{(ja, jot), (k, l)} = {P.}_{ja k} Q_{jot l} .$ $(\mathbb{P} \otimes \mathbb{Q})_{(i,j),(k,l)} = P_{ik}Q_{jl}.$
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 to $p$ $S_P = \{\text{T},\text{H}\}$ $\text{T}$ $\text{H}$ $\text H$

P. = (\begin{matrix} 1 - p & p \\ 0 & 1 \end{matrix}) .

$\mathbb{P} = \pmatrix{1-p & p \\ 0 & 1}.$

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, i $\text{TH}$ $\text{HH}$ $\text{T}$ $\text{H}$ $\text{X}$ oznacza, że ostatnie dwa wyniki były główami - to jest stan pochłaniania. Macierz przejścia to

Q = (\begin{matrix} \frac{1}{2)} & \frac{1}{2)} & 0 \\ \frac{1}{2)} & 0 & \frac{1}{2)} \\ 0 & 0 & 1 \end{matrix}) .

$\mathbb{Q} = \pmatrix{\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1}.$

Ł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)$ $\mathbb{P}$ $\mathbb{Q}$ $(\mathbb{P}\otimes\mathbb{Q})_{(T,T),(T,H)}$ $\text T$ $\text T$ $\text T$ $\text H$ $1-p$ $1/2$ $(1-p)/2$ . Pełna macierz przejścia to

P. \otimes Q = (\begin{matrix} \frac{1 - p}{2)} & \frac{1 - p}{2)} & 0 & \frac{p}{2)} & \frac{p}{2)} & 0 \\ \frac{1 - p}{2)} & 0 & \frac{1 - p}{2)} & \frac{p}{2)} & 0 & \frac{p}{2)} \\ 0 & 0 & 1 - p & 0 & 0 & p \\ 0 & 0 & 0 & \frac{1}{2)} & \frac{1}{2)} & 0 \\ 0 & 0 & 0 & \frac{1}{2)} & 0 & \frac{1}{2)} \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}) .

$\mathbb{P}\otimes\mathbb{Q} = \pmatrix{ \frac{1-p}{2} & \frac{1-p}{2} & 0 & \frac{p}{2} & \frac{p}{2} & 0 \\ \frac{1-p}{2} & 0 & \frac{1-p}{2} & \frac{p}{2} & 0 & \frac{p}{2} \\ 0 & 0 & 1-p & 0 & 0 & p \\ 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 0 & 0 & 1 }.$

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

P. \otimes Q = (\begin{matrix} {P.}_{11} Q & {P.}_{12} Q \\ {P.}_{21} Q & {P.}_{22} Q \end{matrix}) = (\begin{matrix} (1 - p) Q & p Q \\ 0 & Q \end{matrix}) .

$\mathbb{P}\otimes\mathbb{Q} = \pmatrix{ P_{11}\mathbb Q & P_{12}\mathbb Q \\ P_{21}\mathbb Q & P_{22}\mathbb Q } = \pmatrix{ (1-p)\mathbb Q & p\mathbb Q \\ \mathbb 0 & \mathbb Q }.$

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 $(\text{H},\text{*})$ $\text{*}$ $\text X$ $(\text{T},\text{X})$ $(\text{H},\text{X})$ $(\text{H},\text{T})$ $(\text{H},\text{H})$ $(T,T), (T,H), (T,X), \{(H,T), (H,H)\}, (H,X)$ jest

R = (\begin{matrix} \frac{1 - p}{2)} & \frac{1 - p}{2)} & 0 & p & 0 \\ \frac{1 - p}{2)} & 0 & \frac{1 - p}{2)} & \frac{p}{2)} & \frac{p}{2)} \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}) .

$\mathbb{R} = \pmatrix{ \frac{1-p}{2} & \frac{1-p}{2} & 0 & p & 0 \\ \frac{1-p}{2} & 0 & \frac{1-p}{2} & \frac{p}{2} & \frac{p}{2} \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 }.$

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)$ $\mu = ((1-p)/2, (1-p)/2, 0, p, 0)$

W limicie od , $n\to \infty$

μ \cdot R^{n} \to \frac{1}{1 + 4 p - p^{2)}} (0, 0, (1 - p)^{2)}, p (5 - p), p (1 - p)) .

$\mu \cdot \mathbb{R}^n \to \frac{1}{1+4p-p^2}(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

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

@ 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