# Time distibution in Markov chain

Let $$E=\{A,B\}$$ be a set and $$X_{1,t}, X_{2,t}, X_{3,t}$$ three independent Markov chains on the set $$E$$ with respective transition probability $$P^{(1)}, P^{(2)}, P^{(3)}$$ where $$P^{(i)}=\begin{bmatrix}p^{(i)} & 1-p^{(i)}\\ 1-p^{(i)} & p^{(i)} \end{bmatrix}$$

Let $$P = P^{(1)}\otimes P^{(2)}\otimes P^{(3)}$$ where $$\otimes$$ is the Kronecker product.

The process $$Y_t = X_{1,t}\times X_{2,t}\times X_{3,t}$$ (product of the three Markov chain) is a Markov chain with transition probability $$P$$ and state space $$E_Y = E\times E\times E = \{AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB\}$$ and we can use the standard Markov theory to compute anything we want. But, here are my questions :

1 - As $$''AAB ''$$ and $$''ABA ''$$ are the same value equal to $$A^2B$$, then $$E_Y$$ can be reduce to $$\{A^3, A^2B, AB^2, B^3\}$$. Is $$Y_t$$ still a Markov chain if we combine the transition probability in other to set it in that reduced space?

2 - How can I determine the time distribution probability of begin in a particular state. In other word, how can I compute $$\mathbb{P}[Y_{t+1} \neq A^2B, Y_t = A^2B, Y_{t-1} = A^2B, \dots, Y_1 = A^2B | Y_0=A^2B]$$ for each $$t\in \mathbb{N}$$.

• I guess $\mathbb{P}[Y_1=A^2B|Y_0=A^2B] = \mathbb{P}\left[Y_1 \in \{AAB, ABA, BAA\} | Y_1 \in \{AAB, ABA, BAA \} \right]$ but I don't know how to compute that. – Abdoul Haki Jun 23 '19 at 16:51
• Compute the Kronecker product: it's tantamount to supposing the three transitions from the components of a state are independent. The problem is that you cannot even define transitions among the aggregated states unless the $p^{(i)}$ are all equal. – whuber Jun 24 '19 at 20:12
• I think this is the reason why the aggregated $Y_t$ is not a markov chain. Thank you – Abdoul Haki Jun 24 '19 at 21:02

1. One can only aggregate states like $$(A,B,A)$$ and $$(A,A,B)$$ if the probability to reach the event "$$(A,B,A)$$ or $$(A,A,B)$$" is the same for all starting values $$Y_{t-1}$$ of the chain $$Y_t$$. See the details in the lumpability page on Wikipedia.

2. Since the $$X_{i,t}$$ are independent, $$\Bbb P(Y_t=y'|Y_{t-1}=y)=\prod_{i=1}^3\Bbb P(X_{i,t}=y_i'|X_{i,t-1}=y_i)$$

• 1- I think lumpability theory refer to continus Markov Chains. Here, the Markov chains are discret. And in fact here, the states are exactly the same. The question is not about if we can aggregate this state, because we can do it, but the question is, *Is the process still have the Markov chain properties? * – Abdoul Haki Jun 23 '19 at 8:16
• 2- It is not that simple. In fact, for instance $A^2B$ can be $AAB, ABA$ or $BAA$. Then, $\mathbb{P}[Y_t=A^2B|Y_t=A^2B]$ has to take in account all this differents states. I'm trying to compute that time distribution probability even if the reduced $Y_t$ is not a Markov chain. – Abdoul Haki Jun 23 '19 at 8:20

I found solution for my question. So I'm proposition an answer.

1- $$Y_t$$ is not always a markov chain. And it even be a Markov chain but not homogenus.

2- $$\mathbb{P}[Y_{t+1} \neq A^2B, Y_t =A^2B,\dots, Y_1=A^2B| Y_0=A^2B] = \nu P_\mathcal{B}(I-P_\mathcal{B})\mathbf{1}$$ where $$\nu$$ is the initial probability of $$X_t$$ on the set $$\mathcal{B}:=\{AAB,ABA,BAA\}$$, $$\mathbf{1} = \begin{bmatrix}1\\1\\1\end{bmatrix}$$ and $$P_\mathcal{B}$$ is the transition probability on $$\mathcal{B}$$ in other that : $$P = \begin{bmatrix} P_\mathcal{B} & P_{\mathcal{B}\mathcal{B}^c}\\ P_{\mathcal{B}^c\mathcal{B}} & P_{\mathcal{B}^c}\end{bmatrix}$$

$$\mathcal{B}^c = E_Y - \mathcal{B}$$

• This post is puzzling. Your answer (2) doesn't make any sense: depending on what you might mean by "$\mathcal{B}^c,$" you appear to be defining some kind of $6\times 6$ matrix $P,$ but how is that possibly relevant to a process on four states? If (1) is correct, it can only be because you cannot even define $Y_t.$ – whuber Jun 24 '19 at 20:07
• $Y_t$ is define on the set $E_Y$ which has $8$ values and also the matrix $P$ is $8\times 8$. $P_\mathcal{B}$ is $3\times 3$, $P_{\mathcal{B}^c}$ is $5\times 5$, $P_{\mathcal{B}\mathcal{B}^c}$ is $3\times 5$ and $P_{\mathcal{B}^c\mathcal{B}}$ is $5\times 3$. – Abdoul Haki Jun 24 '19 at 20:46