Which norm are you interested in? If talking about the norm induced by the infinity norm over the state space ($\|x\| = \max\limits_{i}|x_i|$) then in general you can only say that for the sub-stochastic matrix $A$ you have $\|A\| := \sup\limits_{\|x\| =1}\|Ax\| \leq 1$. Further bounds depend on the structure of $A$.

@Jochen: thank you very much, I'll take a look on these papers - fortunately they are available.

@Wolfgang: thanks for the suggestion, done.

@RW: I got your idea - but then I am not even sure that the RHS of the inequality is well-defined as I do not know how to show that $(m_x\wedge \tilde m_x)$ is a kernel (so that it is measurable in $x$). I tried to ask it on math.stackexchange.com - but I got no answers. Maybe, you can comment on this. By the way, this question is here: math.stackexchange.com/questions/177631/…

I do not think that the statement is correct: let $X = Y = \{0,1\}$ and $m = (0.3,0.7)$ while $\tilde m = (0.4,0.6)$. Moreover, let $m_x$ and $\tilde m_x$ be independent of $x$ and put $m_x = (0.6,0.4)$ and $\tilde m_x = (0.5,0.5)$. Then the LHS takes the value of $0.18$ while the RHS is $0.15$. Could you please help my to resolve this issue?

I am not an expert in probability at all, so please don't consider me as an example for your statement. However, I have found that my sources on measure theory (Durrett and Folland) are not sufficient to prove the formula we are talking about. Maybe you can advise then some reference on measure theory where products are treated sufficiently?

I'll try that, thanks. Anyway - would you point me on the source like a textbook where the $\wedge$ operation on measures is treated on product spaces (in the case you are aware of such source, of course)?

Thanks - the latter inequality $$ \|M\wedge \tilde M\|\geq \|m\wedge \tilde m\| \cdot\inf\limits_x\|m_x\tilde m_x\| $$ follows immediately from the representation $$ \|M\wedge \tilde M\| = \int\limits_E \|m_x\wedge\tilde m_x\| \; (m\wedge\tilde m)(\mathrm dx) $$ but how can I obtain such representation - maybe it has even a stronger form $$ (M\wedge \tilde M)(A) = \int\limits_E (m_x\wedge\tilde m_x)(A) \; (m\wedge\tilde m)(\mathrm dx) $$ for all measurable $A$? I guess this topic may be covered in some textbook - in such case, would you advise such a book?

[...]I have tried to follow your arguments and arrived to the point $$ \phi_{n+1} = \sup\limits_x\|\mathsf P^{n+1}_x - (\mathsf P^{n+1}_x - \tilde{\mathsf P}^{n+1}_x)_+\| $$ which together with the formula in the previous comment should imply (as far as I get from your answer) that \phi_{n+1}\geq \phi_n\phi_1$, i.e. $$ \inf\limits_x\|\mathsf P^{n+1}_x - \tilde{\mathsf P}^{n+1}_x\|\geq \inf\limits_x\|\mathsf P^{n}_x - \tilde{\mathsf P}^{n}_x\|\inf\limits_x \|\pi_x - \tilde{\pi}_x\|. $$ However, I cannot see how to obtain this inequality immediately - would you help me, please?

Thank you very much for the edit, I am accepting the answer since it seems to be complete - the only problem is that I couldn't get it so far, which should not be a reason for non-accepting. Though, I still have questions w.r.t. your answer, which I hope you'll comment on. 1. Thanks, I've gotten it. 2. With projections - do you mean the representation $$ \mathsf P^{n+1}_x(C) = \int\limits_{E}\mathsf P^n_y(C_y)P(x,\mathrm dy) $$ where $C_y = \{z:(y,z)\in C\}$? [...]

Cross-posted on MSE: math.stackexchange.com/questions/176383/…

[...] 3. With the general Kakutani theorem do you mean the Kakutani dichotomy theorem? In that case, did you mean its original statement for the direct product of measures?

Thank you very much for the answer! May I ask you about come moments which are unclear to me? 1. Do you mean that $\pi_x(\cdot) = P(x,cdot)$? 2. It is not easy for me to follow the proof of the inequality you have suggested since I never heard of the overlap of measures and never met the notation $\|\mu\wedge \nu\|$ - as much as I never worked with the projections of measures. I guess, it is a lack of my background in measure theory - so would you advise me where to get familiar with such concepts? The idea of the proof is now more clear, though. [...]

@George: Thanks a lot for your comments! Sorry for the late response, but I still have some question w.r.t. comment you've left if possible. 1) I agree that the rate of winding for two Brownian motions over the circle will be different - but could you hint on, which event in $\mathbb S^{[0,∞)}$ can correspond to this situation? 2) For the bound you've mentioned, what do you mean by the probability of staying together at each step if the state space is continuous?

Wouldn't it better to ask this question on math.stackexchange.com?

@i707107: why do you think it is necessary?