9
$\begingroup$

I have two different Markov chains, each with one absorbing state and a known starting position. I want to determine the probability that chain 1 will reach an absorbing state in fewer steps than chain 2.

I think I can calculate the probability of reaching an absorbing state in a particular chain after n steps: given a transition matrix $P$ the probability of being absorbed after $n$ steps is $P^n_{ij}$ where $i$ is the starting state and $j$ is the absorbing state.

I'm not certain where to go from here though. Analogous problems I've seen involve dice (e.g., rolling a sum of 7 before a sum of 8), but that is easier to solve because the probability of rolling a particular sum is constant and independent of the number of steps taken so far.

$\endgroup$
13
+100
$\begingroup$

Run the chains in parallel. Define three absorbing states in the resulting product chain:

  1. The first chain reaches an absorbing state but the second does not.

  2. The second chain reaches an absorbing state but the first does not.

  3. Both chains simultaneously reach an absorbing state.

The limiting probabilities of these three states in the product chain give the chances of interest.


This solution involves some (simple) constructions. As in the question, let $\mathbb{P} = P_{ij}, 1 \le i,j\le n$ be a transition matrix for a chain $\mathcal P$. When the chain is in state $i$, $P_{ij}$ gives the probability of a transition to state $j$. An absorbing state makes a transition to itself with probability $1$.

  1. Any state $i$ can be made absorbing upon replacing the row $\mathbb{P}_{i} = (P_{ij}, j=1, 2, \ldots,n)$ by an indicator vector $(0,0,\ldots,0,1,0,\ldots,0)$ with a $1$ in position $i$.
  2. Any set $A$ of absorbing states can be merged by creating a new chain $\mathcal{P}/A$ whose states are $\{i\,|\, i\notin A\}\cup \{A\}$. The transition matrix is given by

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

    This amounts to summing the columns of $\mathbb{P}$ corresponding to $A$ and replacing the rows correspond to $A$ by a single row that makes a transition to itself.

  3. The product of two chains $\mathcal{P}$ on states $S_P$ and $\mathcal{Q}$ on states $S_Q$, with transition matrices $\mathbb{P}$ and $\mathbb{Q}$, respectively, is a Markov chain on the states $S_P\times S_Q = \{(p,q)\,|\, p\in S_P, q\in S_Q\}$ with transition matrix

    $$(\mathbb{P} \otimes \mathbb{Q})_{(i,j),(k,l)} = P_{ik}Q_{jl}.$$

    In effect, the product chain runs the two chains in parallel, separately tracking where each is, and making transitions independently.


A simple example may clarify these constructions. Suppose Polly is flipping a coin with a chance $p$ of landing heads. She plans to do so until observing a heads. The states for the coin flipping process are $S_P = \{\text{T},\text{H}\}$ representing the results of the most recent flip: $\text{T}$ for tails, $\text{H}$ for heads. By planning to stop at heads, Polly will apply the first construction by making $\text H$ an absorbing state. The resulting transition matrix is

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

It begins in a random state $(1-p,p)$ given by the first toss.

In time with Polly, Quincy will toss a fair coin. He plans to stop once he sees two heads in a row. His Markov chain therefore has to keep track of the preceding outcome as well as the current outcome. There are four such combinations of two heads and two tails, which I will abbreviate as "$\text{TH}$", for instance, where the first letter is the previous outcome and the second letter is the current outcome. Quincy applies construction (1) to make $\text{HH}$ an absorbing state. After doing so, he realizes that he doesn't really need four states: he can simplify his chain to three states: $\text{T}$ means the current outcome is tails, $\text{H}$ means the current outcome is heads, and $\text{X}$ means the last two outcomes were both heads--this is the absorbing state. The transition matrix is

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

The product chain runs on six states: $(T,T), (T,H), (T,X); (H,T), (H,H), (H,X)$. The transition matrix is a tensor product of $\mathbb{P}$ and $\mathbb{Q}$ and is just as easily computed. For instance, $(\mathbb{P}\otimes\mathbb{Q})_{(T,T),(T,H)}$ is the chance that Polly makes a transition from $\text T$ to $\text T$ and, at the same time (and independently), Quincy makes a transition from $\text T$ to $\text H$. The former has a chance of $1-p$ and the latter a chance of $1/2$. Because the chains are run independently, those chances multiply, giving $(1-p)/2$. The full transition matrix is

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

It is in block matrix form with blocks corresponding to the second 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 and Quincy compete to see who will achieve their goal first. The winner will be Polly whenever a transition is first made to $(\text{H},\text{*})$ where $\text{*}$ is not $\text X$; the winner will be Quincy whenever a transition is first made to $(\text{T},\text{X})$; and if before either of those can happen a transition is made to $(\text{H},\text{X})$, the result will be a draw. To keep track, we will make the states $(\text{H},\text{T})$ and $(\text{H},\text{H})$ both absorbing (via construction (1)) and then merge them (via construction (2)). The resulting transition matrix, ordered by the states $(T,T), (T,H), (T,X), \{(H,T), (H,H)\}, (H,X)$ is

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

The results of the simultaneous first throw by Polly and Quincy will be the states $(T,T), (T,H), (T,X), \{(H,T), (H,H)\}, (H,X)$ with probabilities $\mu = ((1-p)/2, (1-p)/2, 0, p, 0)$, respectively: this is the initial state at which to start the chain.

In the limit as $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)).$$

Thus the relative chances of the three absorbing states $(T,X), \{(H,T), (H,H)\}, (H,X)$ (representing Quincy wins, Polly wins, they draw) are $(1-p)^2:p(5-p):p(1-p)$.

Figure

As a function of $p$ (the chance that any one of Polly's throws will be heads), the red curve plots Polly's chance of winning, the blue curve plots Quincy's chance of winning, and the gold curve plots the chance of a draw.

$\endgroup$
  • 1
    $\begingroup$ Very neat example, thanks for this. I'm still working out the details to see them for myself. Just a question: here we assumed the two events (Polly and Quincy throws) were happening simultaneously, how much of a difference would it make if we made them sequential, or even chose at random each time who'd throw next? $\endgroup$ – user929304 Mar 2 '16 at 11:37
  • 1
    $\begingroup$ @user929304 You would get different answers, possibly substantially so. For instance, suppose P and Q are running a chain in which the states are partitioned into subsets A and B where all transitions from A go to B and all from B go to A. Let P and Q both start at states in A. In the product chain they both simultaneously alternate between A and B, but the sequential and random-choice chains break that invariant pattern. $\endgroup$ – whuber Mar 2 '16 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.