Étant donné deux chaînes de Markov absorbantes, quelle est la probabilité que l'une se termine avant l'autre?

J'ai deux chaînes de Markov différentes, chacune avec un état absorbant et une position de départ connue. Je veux déterminer la probabilité que la chaîne 1 atteigne un état d'absorption en moins d'étapes que la chaîne 2.

Je pense que je peux calculer la probabilité d'atteindre un état absorbant dans une chaîne particulière après n étapes: étant donné une matrice de transition la probabilité d'être absorbé après étapes est où est l'état de départ et est le état absorbant.n P n i j i $P$$n$$P^n_{ij}$$i$$j$

Je ne sais pas où aller à partir d'ici cependant. Les problèmes analogues que j'ai vus impliquent des dés (par exemple, rouler une somme de 7 avant une somme de 8), mais cela est plus facile à résoudre car la probabilité de rouler une somme particulière est constante et indépendante du nombre de pas effectués jusqu'à présent.

Exécutez les chaînes en parallèle. Définissez trois états d'absorption dans la chaîne de produits résultante:

1. La première chaîne atteint un état absorbant mais pas la seconde.

2. La deuxième chaîne atteint un état absorbant mais pas la première.

3. Les deux chaînes atteignent simultanément un état absorbant.

Les probabilités limitatives de ces trois états dans la chaîne de produits donnent des chances d'intérêt.

---

Cette solution implique quelques constructions (simples). Comme dans la question, que une matrice de transition pour une chaîne P . Lorsque la chaîne est dans l'état i , P i j donne la probabilité d'une transition vers l'état j . Un état absorbant se transforme en lui-même avec la probabilité 1 .$\mathbb{P} = P_{ij}, 1 \le i,j\le n$$\mathcal P$$i$$P_{ij}$$j$$1$

1. Tout état peut être rendu absorbant en remplaçant la ligne P i = ( P i j , j = 1 , 2 , … , n ) par un vecteur indicateur ( 0 , 0 , … , 0 , 1 , 0 , … , 0 ) avec un 1 en position i .$i$$\mathbb{P}_{i} = (P_{ij}, j=1, 2, \ldots,n)$$(0,0,\ldots,0,1,0,\ldots,0)$$1$$i$

2. Tout ensemble d'états absorbants peut être fusionné en créant une nouvelle chaîne P / A dont les états sont { $A$$\mathcal{P}/A$ . La matrice de transition est donnée par$\{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}$$

   Cela revient à additionner les colonnes de correspondant à A et à remplacer les lignes correspondent à A par une seule ligne qui effectue une transition vers elle-même.$\mathbb{P}$$A$$A$

3. Le produit de deux chaînes sur les états S P et Q sur les états S Q , avec les matrices de transition P et Q , respectivement, est une chaîne de Markov sur les états S P × S Q = { ( p , q $\mathcal{P}$$S_P$$\mathcal{Q}$$S_Q$$\mathbb{P}$$\mathbb{Q}$ avec matrice de transition$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}.$$

   En effet, la chaîne de produits exécute les deux chaînes en parallèle, suivant séparément où elles se trouvent et effectuant des transitions indépendamment.

---

Un exemple simple peut clarifier ces constructions. Supposons que Polly lance une pièce avec une chance d'atterrir. Elle prévoit de le faire jusqu'à observer une tête. Les états du processus de retournement des pièces sont S P = { T , H } représentant les résultats du dernier retournement: T pour les queues, H pour les têtes. En prévoyant de s'arrêter aux têtes, Polly appliquera la première construction en faisant de H un état absorbant. La matrice de transition résultante est$p$$S_P = \{\text{T},\text{H}\}$$\text{T}$$\text{H}$$\text H$

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

Il commence dans un état aléatoire donné par le premier lancer.$(1-p,p)$

Avec Polly, Quincy lancera une bonne pièce. Il prévoit de s'arrêter une fois qu'il verra deux têtes d'affilée. Sa chaîne Markov doit donc suivre le résultat précédent ainsi que le résultat actuel. Il existe quatre de ces combinaisons de deux têtes et de deux queues, que je vais abréger en " ", par exemple, où la première lettre est le résultat précédent et la deuxième lettre est le résultat actuel . Quincy applique la construction (1) pour faire de HH un état absorbant. Après cela, il se rend compte qu'il n'a pas vraiment besoin de quatre états: il peut simplifier sa chaîne en trois états: T signifie que le résultat actuel est pile, H signifie que le résultat actuel est têtes, et $\text{TH}$$\text{HH}$$\text{T}$$\text{H}$$\text{X}$signifie que les deux derniers résultats étaient les deux têtes - c'est l'état absorbant. La matrice de transition est

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

La chaîne de produits fonctionne sur six états: . La matrice de transition est un produit tensoriel de P et Q et se calcule tout aussi facilement. Par exemple, ( P ⊗ Q ) ( T $(T,T), (T,H), (T,X); (H,T), (H,H), (H,X)$$\mathbb{P}$$\mathbb{Q}$ est la probabilité que Polly effectue une transition deTàTet, en même temps (et indépendamment), Quincy effectue une transition deTàH. Le premier a une chance de1-pet celuici une chance de1 / 2. Parce que les chaînes sont gérées indépendamment, ces chances se multiplient, donnant(1-p) / 2. La matrice de transition complète est$(\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 }.$$

Il se présente sous forme de matrice de blocs avec des blocs correspondant à la deuxième matrice :$\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 }.$$

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

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

$p$