Mengingat dua rantai Markov menyerap, berapa probabilitas bahwa satu akan berakhir sebelum yang lain?

Saya memiliki dua rantai Markov yang berbeda, masing-masing dengan satu negara menyerap dan posisi awal yang diketahui. Saya ingin menentukan probabilitas bahwa rantai 1 akan mencapai kondisi menyerap dalam beberapa langkah lebih sedikit daripada rantai 2.

Saya pikir saya bisa menghitung probabilitas mencapai keadaan menyerap dalam rantai tertentu setelah n langkah: diberi matriks transisi $P$ probabilitas diserap setelah langkah adalah mana adalah keadaan awal dan adalah negara menyerap.$n$$P^n_{ij}$$i$$j$

Saya tidak yakin ke mana harus pergi dari sini. Masalah analog yang pernah saya lihat melibatkan dadu (misalnya, menggulirkan jumlah 7 sebelum jumlah 8), tetapi itu lebih mudah untuk dipecahkan karena kemungkinan menggulirkan jumlah tertentu konstan dan independen dari jumlah langkah yang diambil sejauh ini.

Jalankan rantai secara paralel. Tentukan tiga kondisi menyerap dalam rantai produk yang dihasilkan:

1. Rantai pertama mencapai kondisi menyerap tetapi yang kedua tidak.

2. Rantai kedua mencapai kondisi menyerap tetapi yang pertama tidak.

3. Kedua rantai secara bersamaan mencapai kondisi menyerap.

Probabilitas yang membatasi dari ketiga kondisi ini dalam rantai produk memberikan peluang menarik.

---

Solusi ini melibatkan beberapa konstruksi (sederhana). Seperti dalam pertanyaan, biarkan menjadi matriks transisi untuk rantai . Saat rantai dalam status ,P$\mathbb{P} = P_{ij}, 1 \le i,j\le n$$\mathcal P$$i$ memberikan probabilitas transisi ke keadaan j . Keadaanmenyerapmembuat transisi ke dirinya sendiri dengan probabilitas 1 .$P_{ij}$$j$$1$

1. Keadaan apa pun yang dapat lakukan ketika mengganti baris P i = ( P i j , j = 1 , 2 , … , n ) dengan vektor indikator ( 0 , 0 , … , 0 , 1 , 0 , … , 0 ) dengan 1 pada posisi i .$i$$\mathbb{P}_{i} = (P_{ij}, j=1, 2, \ldots,n)$$(0,0,\ldots,0,1,0,\ldots,0)$$1$$i$

2. Setiap set menyerap negara dapat digabungkan dengan menciptakan sebuah rantai baru P / A yang negara adalah { $A$$\mathcal{P}/A$ . Matriks transisi diberikan oleh$\{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}$$

   Ini sama dengan menjumlahkan kolom sesuai dengan A dan mengganti baris yang sesuai dengan A dengan satu baris yang membuat transisi ke dirinya sendiri.$\mathbb{P}$$A$$A$

3. The produk dari dua rantai pada negara-negara S P dan Q pada negara-negara S Q , dengan transisi matriks P dan Q , masing-masing, adalah rantai Markov pada negara-negara S P × S Q = { ( p , q $\mathcal{P}$$S_P$$\mathcal{Q}$$S_Q$$\mathbb{P}$$\mathbb{Q}$ dengan matriks transisi$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}.$$

   Akibatnya, rantai produk menjalankan dua rantai secara paralel, secara terpisah melacak di mana masing-masing, dan membuat transisi secara mandiri.

---

Contoh sederhana dapat memperjelas konstruksi ini. Misalkan Polly adalah membalik koin dengan kesempatan kepala mendarat. Dia berencana untuk melakukannya sampai mengamati kepala. Status untuk proses membalik koin adalah S P = { T , H } yang mewakili hasil flip terbaru: T untuk ekor, H untuk kepala. Dengan berencana berhenti di kepala, Polly akan menerapkan konstruksi pertama dengan menjadikan H sebagai negara penyerap. Matriks transisi yang dihasilkan adalah$p$$S_P = \{\text{T},\text{H}\}$$\text{T}$$\text{H}$$\text H$

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

Itu dimulai dalam keadaan acak diberikan oleh lemparan pertama.$(1-p,p)$

Seiring dengan Polly, Quincy akan melemparkan koin yang adil. Dia berencana untuk berhenti begitu dia melihat dua kepala berturut-turut. Rantai Markov-nya harus melacak hasil sebelumnya serta hasil saat ini. Ada empat kombinasi dua kepala dan dua ekor, yang saya akan menyingkat " ", misalnya, di mana huruf pertama adalah hasil sebelumnya dan huruf kedua adalah hasil saat ini . Quincy menerapkan konstruksi (1) untuk menjadikan HH sebagai negara penyerap. Setelah melakukan itu, ia menyadari bahwa ia tidak benar-benar membutuhkan empat keadaan: ia dapat menyederhanakan rantai ke tiga keadaan: T berarti hasil saat ini adalah ekor, H berarti hasil saat ini adalah kepala, dan $\text{TH}$$\text{HH}$$\text{T}$$\text{H}$$\text{X}$berarti dua hasil terakhir sama-sama kepala - ini adalah negara menyerap. Matriks transisi adalah

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

Rantai produk berjalan di enam negara: . Matriks transisi adalah produk tensor dari P dan Q dan dengan mudah dihitung. Misalnya, ( P ⊗ Q ) ( T $(T,T), (T,H), (T,X); (H,T), (H,H), (H,X)$$\mathbb{P}$$\mathbb{Q}$ adalah kesempatan yang Polly membuat transisi dariTkeTdan, pada saat yang sama (dan mandiri), Quincy membuat transisi dariTkeH. Mantan memiliki kesempatan1-pdan kesempatan kedua1 / 2. Karena rantai dijalankan secara independen, peluang itu berlipat ganda, memberi(1-p) / 2. Matriks transisi penuh adalah$(\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 }.$$

Itu dalam bentuk matriks blok dengan blok yang sesuai dengan matriks kedua :$\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 dan Quincy bersaing untuk melihat siapa yang akan mencapai tujuan mereka terlebih dahulu. Pemenang akan Polly setiap kali transisi pertama kali dilakukan ke mana * tidak X ; pemenangnya adalah Quincy setiap kali transisi pertama kali dilakukan ke ( T , X ) ; dan jika sebelum salah satu dari itu bisa terjadi transisi dibuat ke ( H , X ) , hasilnya akan menjadi seri. Untuk melacak, kami akan membuat status ( H , T ) dan ( H , H $(\text{H},\text{*})$$\text{*}$$\text X$$(\text{T},\text{X})$$(\text{H},\text{X})$$(\text{H},\text{T})$$(\text{H},\text{H})$keduanya menyerap (melalui konstruksi (1)) dan kemudian menggabungkannya (melalui konstruksi (2)). Matriks transisi yang dihasilkan, diurutkan oleh state adalah$(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$