Dobrushin, in this paper, looked into the following problem. Suppose We are given a Markov kernel (conditional distribution) $P_{Y|X}$. Information theorist usually call $W$ a channel. It is known that the total variation (TV) is a contraction over the channel $W$, that is, $\text{TV}(P\circ W, Q\circ W)\leq \text{TV}(P, Q)$ where $P\circ W$ and $Q\circ W$ are output distributions of input distributions $P$ and $Q$, respectively. Then Dobrushin showed that, for a fixed input distribution $Q$,

$$\sup_{P\neq Q} \frac{\text{TV}(P\circ W,Q\circ W)}{\text{TV}(P,Q)}=1-\alpha(W)$$

where $\alpha(W)$ is a quantity which only depends on the channel. It can be shown that this supremum is achieved when $\text{TV}(P,Q)\leq \epsilon$, input distributions are so close.

I am interested in an inverse problem in which the output distributions need to be close. More precisely, for a fixed input distribution $Q$

$$\sup ~~\text{TV}(P, Q),$$ subject to the constraint that $$\text{TV}(P\circ W,Q\circ W)\leq \epsilon.$$

This is closely related to my other problem published in MO here almost 9 moths ago.


I don't understand your interpretation of what Dobrushin actually did. Let me restate it in terms closer to his work (as it was the language of functional analysis that he used). A family of probability measures $\pi_x$ on the space $Y$ indexed by points $x\in X$ provides a linear operator ($P$ in Dobrushin's notation, and $W$ in yours). Then he notes that if one endows spaces of measures on $X$ and $Y$ the the total variation norm, then the norm of the restriction of $P$ to zero total mass measures is precisely $\sup_{x_1,x_2\in X} \| \pi_{x_1}-\pi_{x_2} \|/2$. Your contraction coefficient is 1 minus this norm (formulas 1.5, 1.5', 1.5''', 1.15). Therefore, in order to realize it one should look at singular (rather than total variation close) pairs of measures on $X$.

EDIT: If there are two probability measures $\mu_1,\mu_2$ on $X$ which are not mutually singular (i.e., $\|\mu_1-\mu_2\|<2$), then there is a uniquely defined "common part" $\lambda$ such that $2\|\lambda\| + \|\mu_1-\mu_2\|=2$ and $\mu_i=\lambda +\mu'_i$, where $\mu'_1,\mu'_2$ are now mutually singular. Let $\overline{\mu'_i}=\mu'_i/(1-\|\lambda\|)$ be normalizations of $\mu'_i$. Then obviously $$ \| P\mu_1 - P\mu_2 \| = \| P\mu'_1 - P\mu'_2 \| = (1-\|\lambda\|) \|P\overline{\mu'_1} - P\overline{\mu'_2} \| \;, $$ or $$ \|P\overline{\mu'_1} - P\overline{\mu'_2} \| = \frac1{1-\|\lambda\|} \| P\mu_1 - P\mu_2 \| > \| P\mu_1 - P\mu_2 \| \;, $$ so that in order to maximize $\| P\mu_1 - P\mu_2 \|$, the measures $\mu_1,\mu_2$ must be singular.

PS Of course, without any additional assumptions on the family $\{\pi_x\}$ there is no reason to think that $\sup_{x_1,x_2\in X} \| \pi_{x_1}-\pi_{x_2} \|$ is attained. For instance, one can easily construct a family of pairwise absolutely continuous measures (so that no two of them are mutually singular) with $\sup_{x_1,x_2\in X} \| \pi_{x_1}-\pi_{x_2} \|=2$.

PPS I use here the literal definition of the total variation norm, so that $\|\mu\|$ is the sum of the masses of the positive and negative parts of the Hahn decomposition of $\mu$. Unfortunately, what many probabilists (apparently, in the belief that in probability there is no place to numbers greater than 1, and wanting to set probability apart from the rest of mathematics) call "total variation distance" is the result of dividing the true total variation by 2. Alas, it is this misleading definition that appears in the wiki article http://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures. For the sake of historical truth one has to admit though that Dobrushin himself did divide by two in the quoted paper.

  • $\begingroup$ thanks for your nice explanation. This is my problem. Consider the linear operator, $P$, you defined above, which maps the space of probability measures on set $X$ into the space of probability measures on $Y$. For each $x\in X$ we have a prob measure $\mu_x$ on $X$. Call $\bar{mu}$ the barycentre of all probability measures for all $x\in X$, that is, $E[\mu_x]=\bar{\mu}$ where $E[\cdot]$ is the expectation operator with respect to $x$. I want to impose the constraint $E[||\mu_x-\bar{\mu}||]\leq \epsilon$ and then maximize $E[||P\mu_x-P\bar{\mu}||]$. $\endgroup$ Oct 29 '14 at 15:48
  • $\begingroup$ So $P$ is fixed, and one is allowed to vary the family $\mu_x$ under your constraint? Since you are talking about an expectation, there must also be a probability measure on $X$. Is it also fixed alongside with $P$? $\endgroup$
    – R W
    Oct 30 '14 at 17:10
  • $\begingroup$ Originally I had assumed the measure with respect to which the expectation is defined is not fixed and can vary but I think this might the problem hard so lets assume that measure is fixed. $\endgroup$ Oct 30 '14 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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