1

Consider a Markov chain with $n$ states and transition probabilities $p_{ij}$. For a given pair of states $s_1$ and $s_2$, how can I express the expected time until a chain starting in $s_1$ and a chain starting in $s_2$ will reach the same state?

I take it that the probability that they are in the same state in the next period is given as: $$\sum_{j=1}^n p_{1j}p_{2j}.$$ Based on this expression, I take it that the expected time until they reach the same state is given by the $k$ such that: $$\sum_{m=1}^k \sum_{j=1}^n p_{1j}^{(m)}p^{(m)}_{2j} = 1.$$

I have two questions. First, is this expression correct? Second, can it be expressed in a more convenient way?

Aron Vallinder
  • 13
  • My first instinct would try to make a simplified Markov Chain derived from this; You'd have 2 states, 1 and 0. If you're in state 1, the two original chains are in the same state at that time, and in 0 otherwise.

    Say you go $0\to 0$ with probability $p$, and for the sake of this example (since we're only interested to look up until the first meeting of the two chains) $1$ goes to $1$ with probability $1$.

    Then the expected time to reach $1$ for the first time is $\frac{1}{1-p}$ (by using PGFs for example).

    Now the hard part is figuring out what $p$ is; I haven't found that out yet.

     – Marc Oct 23 '20 at 09:32
  • Your expression certainly seems wrong. You seem to be saying that the chains will (almost) surely be in the same state after the expected time, which is not true. The expression for the expected time should be an infinite sum, I think, since it may take arbitrary long time before they're in the same state. If your expression is correct, I would like to see the justification. – saulspatz Oct 23 '20 at 09:55
  • One way to do it, at least for a specific chain, is to make a new chain with transient states $(i,j)$ meaning chain $1$ is in state $i$, chain $2$ is in state $j$, and $i\neq j$. Also, we'll have one absorbing that signifies that the original chains are in the same state. Now we just want the expected time to absorption. I don't know if this can be expressed in a nice formula. – saulspatz Oct 23 '20 at 10:03

1 Answers1

1

Here is a way to implement the idea saulspatz described in the comments. I assume the chain starting in $\ s_1\ $ and the one starting in $\ s_2\ $ are independent of each other. If $\ s_1\ $ and $\ s_2\ $ are in different communicating classes, or they both belong to a communicating class that contains more than one absorbing state, then the expected time for the two chains to reach the same state will be infinite, because there is a positive probability that they will never do so. I'll therefore assume that the original chain comprises a single communicating class with no absorbing states. If the original chain does have an absorbing state, it can be dealt with by a similar procedure.

Consider the Markov chain with $\ (n-1)^2\ $ non-absorbing states $\ (i,j)\ $ with $\ i\ne j\ $, one absorbing state $\ a\ $, and transition matrix $\ \overline{P}\ $ given by \begin{align} \overline{P}_{\left(i_1,i_2\right) \left(j_1,j_2\right)}=&p_{i_1j_1}p_{i_2j_2}\ \ \text{ for }\ \ i_1\ne i_2, j_1\ne j_2\\ \overline{P}_{\left(i_1,i_2\right)a}=&\sum_{j=1}^np_{i_1j}p_{i_2j}\ \ \text{ for }\ \ i_1\ne i_2\\ \overline{P}_{aa}=&1\ . \end{align} The expected time you wish to find is the expected time, $ e_{\left(s_1s_2\right)}\ $, to absorption in this chain from the starting state $\ \left(s_1,s_2\right)\ $, which must satisfy the linear equations $$ e_{s_1s_2}=1+\sum_{j_1=2}^n\sum_{j_2=1}^{j_1-1}p_{s_1j_1}p_{s_2j_2}e_{j_1j_2}+\sum_{j_1=1}^{n-1}\sum_{j_2=j_1+1}^n p_{s_1j_1}p_{s_2j_2}e_{j_1j_2}\ . $$ If $\ \hat{P}\ $ is the $\ (n-1)^2\times(n-1)^2\ $ submatrix of $\ \overline{P}\ $, obtained from it by deleting the row and column corresponding to the absorbing state $\ a\ $, then these equations can be written in matrix form as $$ e=\left(I_{(n-1)^2\times(n-1)^2}-\hat{P}\right)^{-1}\mathbb{1}_{(n-1)^2}\ . $$

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33