# Markov Chain: state reduction

Hi I am trying to understand a proof in a paper (written by Isaac Sonin), I don't know if anyone could give me a clarification on the following: Firstly we have a Markov chain $\{Y_k\}$ with finite state space $X_1$ and a probability transition matrix $P_1=\{p_1(x,y)\}$. Let $D \subset X_1$ and $\tau_1, \tau_2, ..., \tau_n, ...$ the sequence of first, second and so on time visits of the Markov chain to the set $X_2=X_1\setminus D$. Let $u_1^{X_2}(x,.)$ be the distribution of the Markov chain at the moment of first visit to set $X_2$. Then we have the first result (which I understand): 1) The random sequence $\{Y_{\tau_k}\}$ is a Markov chain in a model with state space $X_2$ and transition probability given by: $$(Eq1) \quad p_2(x,y)= p_1(x,y)+ \sum_{z \in D} p_1(x,z)u_1^{X_2}(z,y) \quad x, y \in X_2$$ Now, consider $H_1$ (resp $H_2$) the set of all trajectories for the Markov chain $\{Y_k\}$ (resp $\{Y_{\tau_k}\}$) with state space $X_1$ (resp $X_2$) and $\mathcal{B}_1$ (resp $\mathcal{B}_2$) the corresponding $\sigma - algebra$. Introduce the mapping: $F: H_1 \rightarrow H_2$ by $F(x_0x_1...x_s...)= (x_{\tau_1} ...x_{\tau_k}...)$, i.e all $x_i \in D$ are deleted from the trajectory $(x_0x_1...x_s...)$ in $H_1$. Then the author write as proposition that using Equation (Eq1) we have: $P_2(x,B)=P_1(x,F^{-1}(B))$ for all $B \in \mathcal{B}_2$. Intuitively, I think I can somehow give sense to the equality but I could not write a formal proof although the writer says it is clear. Thanks

Before starting you have to note that the definition of $P_2$ and $P_1$ at the end of the question are not the same as the definitions at the top of the question. At the top, they're matrices, whereas at the bottom, they are probability measures on $H_1$ and $H_2$. More specifically, $P_1(x,B)$ means $\mathbb P((X_1,X_2,X_3,X_4,\ldots)\in B|X_0=x)$, where the family of variables $(X_i)_{i\ge 0}$ is the Markov chain with transition matrix $P_1$.
It's enough to check the equality for `cylinder' sets $B\in \mathcal B_2$. Specifically, it suffices to check the condition for $B$ of the form $\lbrace x\in X_2^{\mathbb N}\colon x_1=a_1,\ldots,x_k=a_k\rbrace$ for arbitrary $k>0$ and any $a_1,\ldots,a_k$. You then can describe $F^{-1}B$ as the set of all sequences in $H_1$ where $a_1,\ldots,a_k$ are the first $k$ entries in $X_2$.
You should then be able to check that $P_1(x_0,F^{-1}B)=p_2(x_0,a_1)p_2(a_1,a_2),\ldots,p_2(a_{k-1},a_k)$ just by summing over the possible paths in $H_1$ going through the $X_2$ states $a_1,\ldots,a_k$ in that order.
• Thank you very much, it looks clearer to me, I was exactly confused with the notation $P_1$ and $P_2$. Just to make sure I understand it right: if I sum over all the possible paths $h$ in $H_1$ going through $a_1,...,a_k$ then is this what I have got? \begin{align} P_1(x_0,F^-1(a_1,...,a_k)) & = \sum_{h\in H_1} P_1(h)p_2(x_0,a_1,...,a_k) \\ & = \sum_h P_1(h)p_2(x_0,a_1)p_2(a_1,a_2)...p_2(a_{k-1},a_k) \\ & = p_2(x_0,a_1)p_2(a_1,a_2)...p_2(a_{k-1},a_k) \sum_h P_1(h) \\ & = p_2(x_0,a_1)p_2(a_1,a_2)...p_2(a_{k-1},a_k) = P_2(a_1,...,a_k) \end{align} Thanks again! – Cal Sep 6 '13 at 17:34
• I don't think this quite captures it. Firstly, you can't sum over $H_1$ because it's uncountable. Secondly, there shouldn't be a $p_2$ term in the first line. Thirdly you shouldn't be summing over all of $H_1$, but rather those paths in $H_1$ starting from $x_0$ and going through $a_1,\ldots,a_k$ in order before hitting any other element of $X_2$. There are a countable number of finite paths starting at $x_0$ and going through the $a$'s in order up to $a_k$. You should be summing over these, expanding out the $P_1$ probabilities of these, and then grouping them to make the $p_2$'s. – Anthony Quas Sep 7 '13 at 0:59