Given $\sigma$ a shift map, $m$  a Markov measure, $C_a$, $C_b$  cylinder sets. Suppose $P \in C_b$. The problem is to show the following \begin{equation} m(C_a \cap \sigma^{1}(P)) = \frac{m(C_a \cap \sigma^{1}(C_b))}{m(C_b)} m(P). \end{equation} This seems to be obvious, but I don't see how to prove this in a simple way for general $P$ (if $P$ is a cylinder set or an open set then the statement apparently holds).

There is a more conceptual explanation. This is a direct corollary of the Markov property formulated in "invariant form": the past and and the future are conditionally independent with respect to the present. Your identity can be rewritten as $$ \frac{m(C_a \cap \sigma^{1}(P))}{m(P)} = \frac{m(C_a \cap \sigma^{1}(C_b))}{m(C_b)} \;, $$ or $$ m(C_a\sigma^{1}(P)) \frac{m(\sigma^{1}(P))}{m(P)} = m(C_a\sigma^{1}(C_b)) \frac{m(\sigma^{1}(C_b))}{m(C_b)} \;. $$ Now it is quite easy to see that the corresponding terms in the LHS and in the RHS are equal, which proves your identity. The formal justification is pretty straightforward if a bit tedious. First, $$ m(C_a\sigma^{1}(P)) = m(C_a\sigma^{1}(C_b)) $$ by the Markov property formulated above. In order to explain it on the formal level let me introduce some additional notation. By $\mathcal A_n$ (resp., $\mathcal A_m^n$) I denote the $\sigma$algebra in the space $A^{\mathbb N}=\{a_i\}_{i=1}^\infty$ generated by the coordinate $a_n$ (resp., the coordinates $a_i$ with $m\le i\le n$), so that the cylinders $C_a,C_b$ belong to $\mathcal A_1$, and the preimage $\sigma^{1}(C_b)$ belongs to $\mathcal A_2$. Further, the set $P$ can be presented as $$ P=C_b \cap Q \;, $$ where $Q\in\mathcal A_2^\infty$. Therefore, $$ \sigma^{1}(P)=\sigma^{1}(C_b) \cap \sigma^{1}(Q) \;, $$ where $\sigma^{1}(Q)\in\mathcal A_3^\infty$. Thus, the sets $A_=C_a$ and $A_+=\sigma^{1}(Q)$ are conditionally independent with respect to $A_0=\sigma^{1}(C_b)$. It means that $$ \frac{m(A_\cap A_0\cap A_+)}{m(A_0)} = \frac{m(A_\cap A_0)}{m(A_0)} \frac{m(A_0\cap A_+)}{m(A_0)} \;, $$ or $$ m(A_ A_0\cap A_+) = m(A_A_0) \;, $$ that is $$ m(C_a\sigma^{1}(P)) = m(C_a\sigma^{1}(C_b)) \;. $$ Note that this argument does not even require time homogeneity of the transition probabilities of the measure $m$. It remains to check that $$ \frac{m(\sigma^{1}(P))}{m(P)} = \frac{m(\sigma^{1}(C_b))}{m(C_b)} \;. $$ This identity can be rewritten as $$ \frac{m(\sigma^{1}(P))}{m(\sigma^{1}(C_b))} = \frac{m(P)}{m(C_b)} \;, $$ or, equivalently, as $$ m(\sigma^{1}(Q)\sigma^{1}(C_b)) = m(QC_b) \;, $$ for which one has to require time homogeneity of the transition probabilities of the measure $m$ (its stationarity is still not necessary). 


I've got the following hint: to approximate $P$ with cylinder sets of increasing length (i.e. it seems, that HW was right). I'm not sure that this is the easiest way, but at least it will work. Thanks to everyone for the help! 


Let $(X_n)$ be a Markov chain and ${\cal F_n}=\sigma(X_{n1},X_{n2},\ldots)$ the past $\sigma$field at time $n$. The quite complicated statement of your problem says nothing but that the equality $$\Pr (X_{n+1} = a \mid {\cal F_n})=\Pr(X_{n+1} = a \mid X_n=b)$$ holds on the event $\{X_n=b\}$. 

