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.

  • $\begingroup$ How is $V-X-Z$ a Markov Chain?? $\endgroup$ Jan 15 '14 at 1:13
  • $\begingroup$ $Z$ is generated from $X$, hence $Z$ depends on $V$ only through $X$ so they form Markov chain, do I miss something? $\endgroup$ Jan 15 '14 at 1:20
  • $\begingroup$ 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. $\endgroup$ Jan 15 '14 at 6:34
  • $\begingroup$ 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)$. $\endgroup$ Jan 15 '14 at 14:59
  • $\begingroup$ So, what is the data? Is the distribution of $Z$ also fixed (along with the joint distribution of $X$ and $V$) or not? $\endgroup$
    – R W
    Jan 17 '14 at 8:16

Your Answer

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

Browse other questions tagged or ask your own question.