# Maximization of a total variation distance subject to another total variation distance in Markov chain

Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the joint and marginal distributions.

We want to generate another random variable $Z$ (on a finite alphabet $\mathcal{Z}$) from $X$ (hence $V-X-Z$ forms a Markov chain) such that for a fixed $\epsilon>0$ we have the following total variation distance constraint $$||P_{VZ}-P_VP_Z||_{TV}\leq \epsilon.$$

My question is what is the maximum possible value for $$||P_{XZ}-P_XP_Z||_{TV}.$$ The maximum here is taken over all conditional distribution $P_{Z|X}$ which satisfies the constraint $||P_{VZ}-P_VP_Z||_{TV}\leq \epsilon.$

Note that it can be easily shown that if both $V$ and $X$ are dependent binary random variables, then if $||P_{VZ}-P_VP_Z||_{TV}=0$ implies $||P_{XZ}-P_XP_Z||_{TV}=0$, in other words, independence of $V$ and $Z$ in Markov chain $V-X-Z$ implies independence of $X$ and $Z$ too.

I should mention that my original problem was bounding the relative entropy of $D(P_{XZ}||P_XP_Z)$ subject to $D(P_{VZ}||P_VP_Z)\leq \epsilon$, however I think the above problem can give some insight as to how attack relative entropy problem.

Any comment is appreciated.

• How is $V-X-Z$ a Markov Chain?? – Anthony Quas Jan 15 '14 at 1:13
• $Z$ is generated from $X$, hence $Z$ depends on $V$ only through $X$ so they form Markov chain, do I miss something? – math-Student Jan 15 '14 at 1:20
• Typically a MC has stationary transition matrices. Here you mean just that there is a transition matrix from $V$ to $X$ and another one from $X$ to $Z$. I'm guessing you're imposing that in the Markov chain $V-X-Z$, the distribution of the pair $(V,Z)$ is the given one. – Anthony Quas Jan 15 '14 at 6:34
• Thanks for your comment. I am a bit confused with your comment. My confusion comes from the fact that the distribution of $Z$ is not given! all we know about distribution of the pair $(V,Z)$ is the constraint $||P_{VZ}-P_VP_Z||\leq \epsilon$. Here by Markov chain I mean, for any random variable $Z$ we generate from $X$, we must have $P(V, X, Z)=P(X,V)P(Z|X)$. – math-Student Jan 15 '14 at 14:59
• So, what is the data? Is the distribution of $Z$ also fixed (along with the joint distribution of $X$ and $V$) or not? – R W Jan 17 '14 at 8:16