Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $(E,\mathscr E)$ be a measurable space and $P,\tilde P$ be two stochastic kernels on that space. I wonder how the induced measures $\mathsf P_x$ and $\tilde{\mathsf P}_x$ differ on the space of finite trajectories $(\Omega_n,\mathscr F_n)$ and on the space of infinite trajectories $(\Omega,\mathscr F)$. I've already asked the finite-trajectories part of the question here and get two answers proving that $$ \sup\limits_{x\in E}\sup\limits_{C\in \mathscr F_n}|\tilde{\mathsf P}_x(C) - \mathsf P_x(C)| \leq n\|\tilde P - P\|. \tag{1} $$

  1. Unfortunately, I didn't see in replies any canonical references on $(1)$ so I wonder if somebody has seen anything that looks like that result - or anything on the topic I've described.

  2. I also wonder, when the rhs in $(1)$ can be bounded if we take the supremum over $C\in \mathscr F$, since clearly $(1)$ does not help in that case. I know that in general there are no trivial bounds since: there exists the example of the kernel $P$ and the pair $x,C$ such that $\mathsf P_x(C) = 1$ but for any $\delta>0$ there is $\tilde P^\delta$ such that $\|\tilde P^\delta - P\|\leq \delta$ but $\tilde{\mathsf P}_y(C) = 0$ for all $y$. On the other hand, I thought that some structural assumptions on $P$ may help: e.g. uniqueness of the invariant distribution and convergence of $P^n$ to this distribution. Again, I would be highly interested in references on the topic of how $(1)$ can be extended from $\mathscr F_n$ to $\mathscr F$, if there are any.

To be precise, I give here the formal statement of the problem.

Let $(E,\mathscr E)$ be a measurable space and for each $n\geq 0$ define $(\Omega_n,\mathscr F_n) = (E^{n+1},\mathscr E^{\otimes(n+1)})$ to be a measuruable product space. In the same fashion, let $\Omega = E^{\mathbb N_0}$ and $\mathscr F$ be its product $\sigma$-algebra.

Let $P$ be a stochastic kernel on $(E,\mathscr E)$, i.e. $P(x,\cdot)$ is a probability measure for each $x\in E$ and $P(\cdot,A)$ is a measurable function for each $A\in \mathscr E$. There is the unique family of measures $(\mathsf P_x)_{x\in E}$ on the space $(\Omega,\mathscr F)$ such that $$ \mathsf P_x(A_0\times A_1\times\dots \times A_n) = 1_{A_0}(x)\int\limits_{A_1}\dots\int\limits_{A_n}P(x_{n-1},\mathrm dx_n)\dots P(x,\mathrm dx_1) \tag{2} $$ where $n\geq0$ is any and $A_i\in \mathscr E$. Moreover, for each $n\geq 0$ let us denote $(\mathsf P^n_x)_{x\in E}$ to be the family of measures on the space $(\Omega_n,\mathscr F_n)$ which is defined uniquely by $(2)$.

Finally, the norm $\|\tilde P - P\|$ is defined by $$ \|\tilde P - P\| = \sup\limits_{f\in \mathrm b\mathscr E}\frac{\|\tilde Pf - Pf\|}{\|f\|} $$ where $\mathrm b\mathscr E$ is a Banach space of real-value bounded measurable functions with a norm $\|f\| = \sup\limits_{x\in E}|f(x)|$ and $$ Pf(x) = \int\limits_E f(y)P(x,\mathrm dy). $$

share|improve this question
You should be able to improve the bound on the right hand side of your inequality to $$2-2\left(1-\Vert\tilde P-P\Vert/2\right)^n.$$ Not that that helps with the $n=\infty$ case though. –  George Lowther May 2 '12 at 0:36
And in general, the measures $\tilde P$, $P$ will be singular (on infinite paths), except in very special cases. E.g., if the processes tend towards states on which the kernels agree. For example, if the processes always reach some absorbing state in finite time. –  George Lowther May 2 '12 at 0:39
@George: thanks for your comments. I have a few question though, if I may. 1) Have you seen any literature on that topic? 2) convergent bounds that you provided are interesting, would you give a hint how to derive them? 3) for infinite paths an example that you gave for sure works. I think, it can be extended to the case when processes do not reach the same absorbing set (where kernels should coincide) but rather converge to that set and kernels are Feller. On the other hand, I thought that it may be can be further extended to the case when they just converge to the same invariant distribution –  Ilya May 2 '12 at 8:30
Hi. No, sorry, I am not aware of much in the way of literature on this subject. I don't think that approaching the same limit distribution is enough. Think of two Brownian motions on the unit circle with constant (but different) drift. They will both have the same limit distribution (uniform), but the rate at which they wind around the circle in the limit $n\to\infty$ will almost surely be different. You really need to the processes to converge to a set on which $P$ and $\tilde P$ agree (or something close to that). –  George Lowther May 2 '12 at 22:28
And, for my bound, you can consider simulating paths for two particles, one for each transition kernel, so that they start at the same point and have probability at least $1-\Vert\tilde P-P\Vert/2$ of staying together at each step. –  George Lowther May 2 '12 at 22:30
show 2 more comments

1 Answer

up vote 2 down vote accepted

It's much easier to understand and answer this question by using the (equivalent) language of families of transition probabilities corresponding to stochastic kernels. So, let $(\pi_x)$ (resp., $(\tilde\pi_x)$ be the family of transition probabilities corresponding to the kernel $P$ (resp., $\tilde P$). Then $$\|P-\tilde P\|=\sup_x \|\pi_x-\tilde\pi_x\|$$ (note that in the RHS I am using the definition of the total variation, according to which the distance between two mutually singular measures equals 2 - it's twice the distance which you use in formula (1)).

Let $\mathbf P^n_x$ and $\widetilde{\mathbf P^n_x}$ be the corresponding measures on the space of sample paths from time $0$ to time $n\le \infty$, and put $$\|P-\tilde P\|^{(n)}=\sup_x \|\mathbf P^n_x-\widetilde{\mathbf P^n_x}\|,$$ so that $\|P-\tilde P\|^{(1)}=\|P-\tilde P\|$. You are interested in estimating $\|P-\tilde P\|^{(n)}$ in terms of $\|P-\tilde P\|$.

By the definition of the total variation, the "overlap" of two probability measures $\mu,\tilde\mu$ is $$\|\mu\wedge\tilde\mu\|=1-\|\mu-\tilde\mu\|/2$$ Since the measure $\mathbf P^{n+1}_x$ naturally projects onto the measure $\mathbf P^n_x$, and the conditional measures of this projection are precisely the one-step transition probabilities, the numbers $$\phi_n = \inf_x \| \mathbf P^n_x\wedge\widetilde{\mathbf P^n_x} \| = 1-\|P-\tilde P\|^{(n)}/2$$ satisfy the inequality $$ \phi_{n+1} \ge \phi_n \phi_1, $$ and one arrives precisely at George Lowther's inequality. Moreover, one can easily see that it is optimal.

I think this is as much as what one can say about your question in this generality. Two more comments:

  1. Given a big finite state space $X$, the number of parameters describing probability distributions on $X$ is much less than the number of parameters describing Markov chains on $X$. The moral is that there is a lot of of pairs of distinct irreducible Markov chains with the same stationary distributions. The corresponding measures on the infinite path spaces of these chains will obviously be mutually singular. For the simplest example one can take a Bernoulli measure and any non-Bernoulli Markov chain with the same stationary distribution (such an example exists even for $|X|=2$).

  2. There is a general Kakutani theorem which gives necessary and sufficient conditions for two measures on an infinite product space to be equivalent in terms of their finite dimensional distributions.

EDIT: I will answer here as comments don't provide enough space.

(1) Yes, $\pi_x=P(x,\cdot)$.

(2a) Let $\lambda_+$ and $\lambda_-$ be, respectively, the positive and the negative parts of the difference $\lambda=\mu-\tilde\mu$, then the total variation distance between $\mu$ and $\tilde\mu$ is $$ \|\mu-\tilde\mu\| = \|\lambda_+\| + \|\lambda_-\| = 2 \|\lambda_+\| = 2 \|\lambda_-\| $$ (by the way, this is the reason why it is this quantity that should be called the "total variation distance", not its half). The "common part" of the measures $\mu$ and $\tilde\mu$ is $$ \mu\wedge\tilde\mu=\mu-\lambda_+=\tilde\mu-\lambda_- $$ (this is the infimum of $\mu$ and $\tilde\mu$ with respect to the natural order on the cone of positive measures).

(2b) In this situation the projection business is very simple as one deals with product spaces. If you have a measure $m$ on a space $X$ and a family of measures $m_x$ on another space $Y$ parametrized by points of $X$, then the result of integration of the family $m_x$ against $m$ gives you a new measure on the product space $X\times Y$. One can consider this construction as a generalization of the Fubini theorem (actually, under reasonable conditions on the involved measures the converse is also true, namely, any measure on $X\times Y$ can be uniquely presented in this way - this is a particular case of the famous theorem on existence of conditional measures). It is precisely this construction that is used when passing from $\mathbf P^n_x$ to $\mathbf P^{n+1}_x$.

(3) Actually what I meant is not the original Kakutani theorem, but its generalization to arbitrary pairs of locally equivalent measures - see, for instance, the textbook of Shiryaev, Section VII.6. However, it would only help in your situation if you deal with Markov chains without finite stationary measures. The reason is the following. For a finite stationary measure of a Markov chain the associated shift invariant measure is ergodic if and only if the state space does not admit a decomposition into two non-communicating subsets of positive measure. On the other hand, any two distinct ergodic measures are mutually singular, so that $\mathbf P^\infty_x$ and $\widetilde{\mathbf P^\infty_x}$ are also pairwise singular for a.e. $x$.

EDIT 2: Once again, hanc marginis exiguitas non caperet, so that I am adding another edit to the original answer.

  1. Yes, when talking about conditional decompositions of measures on product spaces I meant that any probability measure $M$ on $X\times Y$ can be uniquely decomposed as $dM(x,y)=dm(x)dm_x(y)$, or, equivalently, $M=\int m_x dm(x)$, where $m$ is its projection onto $X$, and $m_x$ are its conditional measures on the fibers of this projection. In your case $$d \mathbf P_x^{n+1}(x,x_1,\dots,x_n,x_{n+1})= d \mathbf P_x^n(x,x_1,\dots,x_n)d\pi_{x_n}(x_{n+1}).$$ [Another general comment: there are no sets in my formulas for measures - this notation is actually much more convenient.]

  2. Let me explain it in the general setup of measures on product spaces. Let $M$ and $\tilde M$ be two measures on the same product space $X\times Y$ with conditional decompositions $M=\int m_x dm(x)$ and $\tilde M=\int \tilde m_x d\tilde m(x)$. Then $$\|M\wedge \tilde M\| = \int \|m_x\wedge\tilde m_x\| d (m\wedge\tilde m)(x),$$ whence $$\|M\wedge \tilde M\| \ge \|m\wedge\tilde m\| \inf_x \|m_x\wedge\tilde m_x\|,$$ which in your particular case takes precisely the form $$ \phi_{n+1} \ge \phi_n \phi_1 . $$

share|improve this answer
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. [...] –  Ilya Jul 27 '12 at 8:02
[...] 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? –  Ilya Jul 27 '12 at 8:07
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\}$? [...] –  Ilya Jul 29 '12 at 8:40
[...]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? –  Ilya Jul 29 '12 at 8:48
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? –  Ilya Jul 30 '12 at 7:27
show 8 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.