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.

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 .$\mathbb{P} = P_{ij}, 1 \le i,j\le n$$\mathcal P$$i$$P_{ij}$$j$$1$

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$

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 przez$A$$\mathcal{P}/A$$\{i\,|\, i\notin A\}\cup \{A\}$

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

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

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

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

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

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

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

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

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

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$