Wie hoch ist bei zwei absorbierenden Markov-Ketten die Wahrscheinlichkeit, dass eine vor der anderen endet?

Ich habe zwei verschiedene Markov-Ketten mit jeweils einem absorbierenden Zustand und einer bekannten Ausgangsposition. Ich möchte die Wahrscheinlichkeit bestimmen, dass Kette 1 in weniger Schritten einen absorbierenden Zustand erreicht als Kette 2.

Ich denke, ich kann die Wahrscheinlichkeit berechnen, nach n Schritten einen absorbierenden Zustand in einer bestimmten Kette zu erreichen: Bei einer Übergangsmatrix beträgt die Wahrscheinlichkeit, nach Schritten absorbiert zu werden, wobei der Startzustand und ist absorbierender Zustand.n P n i j i $P$$n$$P^n_{ij}$$i$$j$

Ich bin mir allerdings nicht sicher, wohin ich von hier aus gehen soll. Analoge Probleme, die ich gesehen habe, betreffen Würfel (z. B. das Würfeln einer Summe von 7 vor einer Summe von 8), aber das ist einfacher zu lösen, da die Wahrscheinlichkeit, eine bestimmte Summe zu würfeln, konstant und unabhängig von der Anzahl der bisher unternommenen Schritte ist.

Führen Sie die Ketten parallel. Definieren Sie drei Absorptionszustände in der resultierenden Produktkette:

1. Die erste Kette erreicht einen absorbierenden Zustand, die zweite jedoch nicht.

2. Die zweite Kette erreicht einen absorbierenden Zustand, die erste jedoch nicht.

3. Beide Ketten erreichen gleichzeitig einen absorbierenden Zustand.

Die begrenzenden Wahrscheinlichkeiten dieser drei Zustände in der Produktkette geben die Chancen von Interesse.

---

Diese Lösung beinhaltet einige (einfache) Konstruktionen. Wie in der Frage sei eine Übergangsmatrix für eine Kette $\mathbb{P} = P_{ij}, 1 \le i,j\le n$$\mathcal P$ . Wenn sich die Kette im Zustand , gibt P i j die Wahrscheinlichkeit eines Übergangs in den Zustand j an . Ein absorbierender Zustand geht mit Wahrscheinlichkeit 1 zu sich selbst über .$i$$P_{ij}$$j$$1$

1. Jeder Zustand kann absorbiert werden, wenn die Zeile P i = ( P i j , j = 1 , 2 , … , n ) durch einen Indikatorvektor ( 0 , 0 , $i$$\mathbb{P}_{i} = (P_{ij}, j=1, 2, \ldots,n)$ mit einer 1 in Position i .$(0,0,\ldots,0,1,0,\ldots,0)$$1$$i$

2. Jede Menge absorbierender Zustände kann zusammengeführt werden, indem eine neue Kette P / A erstellt wird, deren Zustände { $A$$\mathcal{P}/A$ . Die Übergangsmatrix ist gegeben durch$\{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}$$

   Dies läuft darauf hinaus, die Spalten von , die A entsprechen, zu summieren und die Zeilen, die A entsprechen, durch eine einzelne Zeile zu ersetzen, die zu sich selbst übergeht.$\mathbb{P}$$A$$A$

3. Das Produkt zweier Ketten in den Zuständen S P und Q in den Zuständen S Q mit den Übergangsmatrizen P bzw. Q ist eine Markov-Kette in den Zuständen S P × S Q = { ( p , q $\mathcal{P}$$S_P$$\mathcal{Q}$$S_Q$$\mathbb{P}$$\mathbb{Q}$ mit Übergangsmatrix$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}.$$

   Tatsächlich führt die Produktkette die beiden Ketten parallel aus, verfolgt getrennt, wo sich jede befindet, und führt unabhängig voneinander Übergänge durch.

---

Ein einfaches Beispiel kann diese Konstruktionen verdeutlichen. Angenommen Polly eine Münze mit einer Chance ist Flipping Landeköpfe. Sie plant dies, bis sie einen Kopf beobachtet. Die Zustände für den Münzwurfprozess sind S P = { T , H $p$$S_P = \{\text{T},\text{H}\}$ was die Ergebnisse des letzten Wurfs darstellt: für Schwänze, H für Köpfe. Durch die Planung, an den Köpfen anzuhalten, wird Polly die erste Konstruktion anwenden, indem H zu einem absorbierenden Zustand gemacht wird. Die resultierende Übergangsmatrix ist$\text{T}$$\text{H}$$\text H$

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

Es beginnt in einem zufälligen Zustand , der durch den ersten Wurf gegeben wird.$(1-p,p)$

Pünktlich zu Polly wird Quincy eine faire Münze werfen. Er will aufhören, sobald er zwei Köpfe hintereinander sieht. Seine Markov-Kette muss daher sowohl das vorhergehende als auch das aktuelle Ergebnis verfolgen. Es gibt vier solcher Kombinationen von zwei Köpfen und zwei Schwänzen, die ich zum Beispiel als " " abkürzen werde , wobei der erste Buchstabe das vorherige Ergebnis und der zweite Buchstabe das aktuelle Ergebnis ist. Quincy wendet Konstruktion (1) an, um zu machen$\text{TH}$ einem absorbierenden Zustand. Danach stellt er fest, dass er nicht wirklich vier Zustände benötigt: Er kann seine Kette auf drei Zustände vereinfachen: T bedeutet, dass das aktuelle Ergebnis Schwänze ist, H bedeutet, dass das aktuelle Ergebnis Köpfe ist, und$\text{HH}$$\text{T}$$\text{H}$$\text{X}$bedeutet, dass die letzten beiden Ergebnisse beide Köpfe waren - dies ist der absorbierende Zustand. Die Übergangsmatrix ist

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

Die Produktkette läuft in sechs Zuständen: . Die Übergangsmatrix ist einTensorproduktvon P und Q und ebenso einfach zu berechnen. Zum Beispiel ( T ) , ( T , $(T,T), (T,H), (T,X); (H,T), (H,H), (H,X)$$\mathbb{P}$$\mathbb{Q}$ ist die Chance, dass Polly einen Übergang vonTnachT machtund Quincy gleichzeitig (und unabhängig) einen Übergang vonTnachH macht. Die erstere hat eine Chance von1-pund die letztere eine Chance von1 / 2. Da die Ketten unabhängig voneinander laufen, multiplizieren sich diese Chancen und ergeben(1-p) / 2. Die vollständige Übergangsmatrix ist$(\mathbb{P}\otimes\mathbb{Q})_{(T,T),(T,H)}$$\text T$$\text T$$\text T$$\text H$$1-p$$1/2$$(1-p)/2$

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

Es liegt in Blockmatrixform mit Blöcken vor, die der zweiten Matrix :$\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 und Quincy konkurrieren darum, wer zuerst ihr Ziel erreicht. Der Gewinner ist Polly, wenn zuerst ein Übergang zu wobei * nicht X ist . Der Gewinner ist Quincy, wenn zum ersten Mal ein Übergang zu ( T , X ) erfolgt . und wenn bevor einer dieser Fälle eintreten kann, ein Übergang zu ( H , X ) erfolgt , ist das Ergebnis ein Unentschieden. Um den Überblick zu behalten, werden wir die Zustände ( H , T ) und ( H , H ) erstellen. beide absorbiert (über die Konstruktion (1)) und sie dann zusammenführt (über die Konstruktion (2)). Die resultierende Übergangsmatrix, geordnet nach den Zuständen ( T , $(\text{H},\text{*})$$\text{*}$$\text X$$(\text{T},\text{X})$$(\text{H},\text{X})$$(\text{H},\text{T})$$(\text{H},\text{H})$ ist$(T,T), (T,H), (T,X), \{(H,T), (H,H)\}, (H,X)$

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

$(T,T), (T,H), (T,X), \{(H,T), (H,H)\}, (H,X)$$\mu = ((1-p)/2, (1-p)/2, 0, p, 0)$

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

$(T,X), \{(H,T), (H,H)\}, (H,X)$$(1-p)^2:p(5-p):p(1-p)$

Als Funktion von $p$