Probability two (specific) independent Markov chains are some time at the same state 
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.
 A: 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.


*

*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.

*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$.

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

A: 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)$
