Probability two (specific) independent Markov chains are some time at the same state

Question

Let $\{X_n\},~\{Y_n\}$ be two independent Markov chains, with state space $\{1,2,3,4,5\}$, both with transition probability matrix: $$\displaystyle P=\left( \begin{array}{ccccccc} 0 & 1 & 0 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/4 & 1/4 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1/2 & 0& 0 & 1/2 \\ 0 & 1/2 & 0 & 1/2 & 0 \\ \end{array} \right).$$ If initial states $X_0\neq Y_0$ on $\{1,2,3,4,5\}$ are given, find the probability that $X_n=Y_n$ for some $n$.

Attempt. I thought of working on $Z_n=X_n-Y_n,~n\geq 1$, and find $P(T<+\infty~|~Z=z_0),$ where $T=\inf\{k\geq 0:~Z_n=0\}$, but working with $\{Z_n\}$ doesns't seem a good choice (in terms of calculations).

Any hint will be appreciated. Thank you in advance!

Thank you in advance!

Edit. As @Did mentioned, if $X_0\neq Y_0$, the chains can not be indentically distributed.

Answer 1

Waiting for a clarification on the actual meaning of the question posed, and considering the comments given and received, let's put the answer under three possible hypotheses.

1. Probability that at step $n$ the two chains are in the same given state = $m$
   Given the probability vectors $$ \mathbf{X}_{\,n} = \overline {\mathbf{P}} ^{\,n} \,\mathbf{X}_{\,0} = \left\| {\,x_{\,m}^{\left( n \right)} \,} \right\|\quad \mathbf{Y}_{\,n} = \overline {\mathbf{P}} ^{\,n} \,\mathbf{Y}_{\,0} = \left\| {\,y_{\,m}^{\left( n \right)} \,} \right\| $$ then the probability that the two chains, at step $n$ be in the same state $m$ is by definition $$ p(n,m) = x_{\,m}^{\left( n \right)} y_{\,m}^{\left( n \right)} \quad \left| {\;1 \leqslant m \leqslant 5} \right. $$ where $i$ and $j$ denote the starting state for $X$ and $Y$. For this probability to be non-null, the two corresponding entries in $ \mathbf{P} ^{\,n}$ must be non-null, at the same $n$: this is a double condition, which is related to the irreducibility and regularity of $ \mathbf{P} $.
   Now, the given matrix can be permuted as to get $$ \left( {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \end{array} } \right)\;\overline {\mathbf{P}} \;\left( {\begin{array}{*{20}c} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \end{array} } \right)\; = \left( {\begin{array}{ccc|cc} 0 & 0 & 0 & & 0 & {1/4} \\ 0 & 0 & 0 & & 0 & {1/4} \\ 0 & 0 & 0 & & {1/2} & {1/4} \\ \hline 0 & 0 & {1/2} & & 0 & {1/4} \\ 1 & 1 & {1/2} & & {1/2} & 0 \\ \end{array} } \right) $$ thus it is irreducible, and it becomes fully positive for $4 \leqslant n$.
   It is therefore a matter to compute the 2nd and 3rd power to see for which combination of the initial states ($i,j$) and final state ($m$) it is null.
2. Probability that at step $n$ the two chains are in the same state (whichever)
   From the results above, we will clearly have that: $$ \begin{gathered} p^ * (n) = \sum\limits_{1\, \leqslant \,k\, \leqslant \,m} {p(n,k)} = \mathbf{X}_{\,n} \cdot \mathbf{Y}_{\,n} = \sum\limits_{1\, \leqslant \,k\, \leqslant \,m} {P_{\,i\,,\,k}^{\left( n \right)} \,P_{\,k\,,\,j}^{\left( n \right)} } = \hfill \\ = \overline {\mathbf{X}_{\,0} } \;\mathbf{P}^{\,n} \;\overline {\mathbf{P}} ^{\,n} \;\mathbf{Y}_{\,0} \,\quad \left| {\;1 \leqslant i,j \leqslant 5} \right. \hfill \\ \end{gathered} $$ and since $\overline{\mathbf{P}}$ can be permuted into the block partition already shown it is easy to get that the product matrix is fully positive already for $n=2$.
3. Probability that at step $n$ the two chains have the same probability to be in each of the possible states
   i.e. that they have the same probability vector.
   $$ \mathbf{X}_n = \overline {\mathbf{P}}^{\,n} \,\mathbf{X}_0 = \mathbf{Y}_n = \overline {\mathbf{P}}^{\,n} \,\mathbf{Y}_0 \quad \Rightarrow \quad \mathbf{0} = \overline {\mathbf{P}}^{\,n} \left( {\mathbf{X}_0 - \mathbf{Y}_0 } \right) $$ where $\overline {\mathbf{P}} $ indicates the transpose of $\mathbf{P}$.
   Now it is easy to get that the nullspace of $ \overline{\mathbf{P}}$ is given by $(1,\, 0,\, -1,\, 0,\, 0)$.
   Of course, that is also the nullspace of $ \overline {\mathbf{P}}^{\,n}$, and viceversa the nullspace of $ \overline{\mathbf{P}}^{\,n}$ cannot be other than that, for whichever $1 \leqslant n$.
   Therefore $$ \left( {\mathbf{X}_0 - \mathbf{Y}_0 } \right) = \lambda \;\left( {\begin{array}{*{20}c} 1 \\ 0 \\ { - 1} \\ 0 \\ 0 \\ \end{array} } \right)\quad \Leftrightarrow \quad \mathbf{X}_n = \mathbf{Y}_n \quad \left| \begin{gathered} \;\lambda \; \in \;\;\mathbb{R}\,\, \hfill \\ \;1 \leqslant \forall n \hfill \\ \end{gathered} \right. $$ So we are looking for the couples of vectors $(\mathbf X, \, \mathbf Y)$ such that $$ \left\{ \begin{gathered} 1 \leqslant x_{\,k} ,y_{\,k} \leqslant 5 \hfill \\ \lambda \in \;\;\mathbb{Z}\, \hfill \\ x_{\,1} - y_{\,1} = \lambda \hfill \\ x_{\,3} - y_{\,3} = - \lambda \hfill \\ x_{\,2} = y_{\,2} ,\quad x_{\,4} = y_{\,4} ,\quad x_{\,5} = y_{\,5} \hfill \\ \end{gathered} \right. $$
   By drawing the line $y=x+\lambda$ within a square $(1, \cdots, 5) \times (1, \cdots, 5)$ we can realize that the 2nd identity above has $5^2$ solutions, each associated with a solution to the 3rd id.
   Thus the number of the couples of vectors satisfying the conditions will be: $$ 5^{\,2} \cdot 5^{\,3} = 5^{\,5} $$ versus a total of $5^{10}$.

Answer 2

You can combine any two Markov chains to make a new Markov chain.

If we combine $X$ and $Y$, we get a Markov chain with state space $\{(1,1),(1,2),(1,3),\dots,(5,4),(5,5)\}$ and initial state $(X_0,Y_0)$. Let's call this Markov chain $W$.

Since we have 25 states, the transition matrix $P_W$ of $W$ will be of size $25 \times 25$. The probability of going from, for example, state $(1,2)$ to state $(3,4)$ will simply be the probability of going from 1 to 3 in the first chain multiplied by the probability of going from 2 to 4 in the second chain. You may want to construct the matrix with a computer program such as Mathematica.

The probability of being in a certain state can be calculated as usual:

$W_n = ({P_W}^\mathrm{T})^n W_0$,

where $W_0$ is the initial probability of the states, in your case a vector with one of the elements equal to 1 and the other 24 equal to 0. Now we can do:

$P(X_n = Y_n) = \sum_{i=1}^5 P(W_n=(i,i)) = wW_n$,

where $w = (1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1)$