Учитывая две поглощающие цепи Маркова, какова вероятность того, что одна из них прервется раньше другой?

У меня есть две разные цепи Маркова, каждая с одним поглощающим состоянием и известной стартовой позицией. Я хочу определить вероятность того, что цепь 1 достигнет поглощающего состояния за меньшее количество шагов, чем цепь 2.

Я думаю, что могу вычислить вероятность достижения поглощающего состояния в определенной цепочке после n шагов: при заданной матрице перехода вероятность поглощения после шагов равна P ^ n_ {ij}, где i - начальное состояние, а j - это поглощающее состояние.n P n i j i $P$$n$$P^n_{ij}$$i$$j$

Я не уверен, куда идти отсюда, хотя. Аналогичные проблемы, которые я видел, включают в себя игральные кости (например, бросание суммы 7 до суммы 8), но это легче решить, потому что вероятность броска определенной суммы постоянна и не зависит от количества шагов, предпринятых до сих пор.

Запустите цепи параллельно. Определите три поглощающих состояния в полученной цепочке продуктов:

1. Первая цепь достигает поглощающего состояния, а вторая - нет.

2. Вторая цепь достигает поглощающего состояния, а первая - нет.

3. Обе цепи одновременно достигают поглощающего состояния.

Предельные вероятности этих трех состояний в цепочке продуктов дают шансы на интерес.

---

Это решение включает в себя некоторые (простые) конструкции. Как и в вопросе, пусть быть матрица перехода для цепи P . Когда цепочка находится в состоянии i , P i j дает вероятность перехода в состояние j . Поглощающие состояния делают переход к самому себе с вероятностью 1 .$\mathbb{P} = P_{ij}, 1 \le i,j\le n$$\mathcal P$$i$$P_{ij}$$j$$1$

1. Любое состояние можно сделать поглощающим после замены строки P i = ( P i j , j = 1 , 2 , … , n ) вектором индикатора ( 0 , 0 , … , 0 , 1 , 0 , … , 0 ) с 1 в положении я .$i$$\mathbb{P}_{i} = (P_{ij}, j=1, 2, \ldots,n)$$(0,0,\ldots,0,1,0,\ldots,0)$$1$$i$

2. Любой набор поглощающих состояний можно объединить , создав новую цепочку с состояниями . Матрица перехода определяется какP / A { $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}$$

   Это равносильно суммированию столбцов соответствующих A, и замене строк, соответствующих A , одной строкой, которая выполняет переход к себе.$\mathbb{P}$$A$$A$

3. Продукт из двух цепей на состояниях S P и Q на состояниях S Q , с переходом матрицы P и Q , соответственно, представляет собой цепь Маркова на состояния S P × S Q = { ( р , д $\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}.$$

   Фактически, цепочка продуктов управляет двумя цепочками параллельно, отдельно отслеживая, где каждая из них, и выполняет переходы независимо.

---

Простой пример может прояснить эти конструкции. Предположим, Полли подбрасывает монету с шансом приземления голов. Она планирует сделать это, пока не увидит головы. Состояния для процесса подбрасывания монеты: S P = { T , H }, представляющие результаты самого последнего броска: T для хвостов, H для голов. Планируя остановиться на головах, Полли применит первую конструкцию, сделав H поглощающим состоянием. Результирующая матрица перехода$p$$S_P = \{\text{T},\text{H}\}$$\text{T}$$\text{H}$$\text H$

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

Он начинается в случайном состоянии заданном первым броском.$(1-p,p)$

Со временем с Полли Куинси подбросит честную монету. Он планирует остановиться, как только увидит две головы подряд. Поэтому его цепочка Маркова должна отслеживать предыдущий результат, а также текущий результат. Существует четыре таких комбинации двух голов и двух хвостов, которые я буду сокращать , например, как « », где первая буква - это предыдущий результат, а вторая буква - текущий результат. Куинси применяет конструкцию (1), чтобы сделать ЧЧ поглощающим состоянием. После этого он понимает, что ему на самом деле не нужны четыре состояния: он может упростить свою цепочку до трех состояний: T означает, что текущий результат - это хвосты, H - текущий результат - головы, а $\text{TH}$$\text{HH}$$\text{T}$$\text{H}$$\text{X}$означает, что последние два результата были обе головы - это поглощающее состояние. Матрица перехода

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

Цепочка продуктов работает в шести состояниях: . Матрица перехода является тензорное произведение из P и Q , и так же легко вычислена. Например, ( P ⊗ Q ) ( T $(T,T), (T,H), (T,X); (H,T), (H,H), (H,X)$$\mathbb{P}$$\mathbb{Q}$ является вероятностьчто попка делает переход отТкТи, в то же время (и независимо другдруга), Квинси делает переход отТкН. Первый имеет шанс1-ри последний шанс1 / 2. Поскольку цепочки работают независимо, эти шансы умножаются, давая(1-p) / 2. Полная матрица перехода$(\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 }.$$

Он находится в форме блочной матрицы с блоками, соответствующими второй матрице :$\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$