Suppose two random variables $X$ and $V$ are given. I am wondering what kind of condition we need to impose on joint distribution of $V$ and $X$ to make sure that there exists a random variable $Z$ such that they form Markov chain $VXZ$ and $Z$ and $V$ are independent.

$\begingroup$ Couldn't parse your last sentence. Do you mean that $(V,X,Z)$ is Markov? Please specify what exactly is Markov, and what exactly is independent. And, BTW, I don't see what it has to do with convex analysis. $\endgroup$ – Alexander Shamov Feb 3 '14 at 4:26

1$\begingroup$ Doesn't $Z=0$ satisfy your condition? Or do you want the Markov chain to be homogeneous? $\endgroup$ – Alexander Shamov Feb 4 '14 at 15:35

1$\begingroup$ @Alexander Sharnov: Why remove the convex analysis tag? Isn't the condition going to be some sort of convex constraint? This problem looks fine, and I don't understand the down votes. $\endgroup$ – Douglas Zare Feb 4 '14 at 15:39

4$\begingroup$ And BTW, I suspect I'm not the only one who reads the "$$" in "$VXZ$" as "minus" by default. $\endgroup$ – Alexander Shamov Feb 4 '14 at 15:39

1$\begingroup$ As far as I can tell from your answer, you are viewing $X$ and $V$ as living in different spaces (which, I believe, you should have clarified in the question). Thus are you not viewing $Z$ independent of the couple $(V,X)$ as a solution? In particular, as I suggested in an earlier comment, what's wrong with $Z = \mathrm{const}$? $\endgroup$ – Alexander Shamov Feb 4 '14 at 20:27
The necessary and sufficient condition for existence of such random variable which forms the Markov chain $V\to X\to Z$ is "row linear dependence" of the transition kernel from $X$ to $V$. Let $V\in\mathcal{V}$ and $X\in\mathcal{X}$ and also $\mathcal{V}=r$ and $\mathcal{X}=k$. Suppose $\mathcal{A}=\{P(\textbf{V}x_i), ~ i=1,2,\dots, k\}$ is the set of all the rows of matrix $\{P(vx)\}$. Consider the equation $P(\textbf{V})=\sum_{i=1}^k \alpha_i P(\textbf{V}x_i)$ for $\alpha_i\geq 0$ and $\sum_i \alpha_i=1$ which has an obvious solution $\alpha_i=P(x_i)$ (which asserts that $P(\textbf{V})$ lies in the convex hull of $\mathcal{A}$). The condition "row linear dependence" is needed to make sure this equation has other solutions as well. It is wellknown that $\dim(\text{conv}(G))=\dim(\text{span}(G))1$. Suppose $\dim(\text{span}(G))=d$ and hence $\dim(\text{conv}(G))=d1$. By assumption, $d\leq k1$. By Caratheodory theorem, $P(\textbf{V})$ can be expressed as a convex combination of $d$ points in $\mathcal{A}$. Let $P(\textbf{V})=\sum_{i=1}^d \mu_iP(\textbf{V}x_i)$. So, $[\mu_1, \mu_2, \dots, \mu_d, 0,0,\dots,0]$ is also another solution for $P(\textbf{V})=\sum_{i=1}^k \alpha_i P(\textbf{V}x_i)$. It is easy to see that the solution set of this equation is a convex set because if $\psi$ and $\zeta$ are two solutions then $\lambda \psi + (1\lambda)\zeta$ for $0\leq \lambda \leq 1$ is also a solution. Therefore, each point in the solution set (like $P(\textbf{X})$) can be expressed as convex combination of $\mu$ and another point in the boundary of the set solution set, say $\nu$. Using all these said, we can construct a binary random variable $Z$ as the following: $P(\textbf{X}z_1)=\mu$, $P(\textbf{X}z_2)=\nu$ and $\mu P(\textbf{X}z_1)+ \nu P(\textbf{X}z_2)=P(\textbf{X})$.
Note that the $Z$ constructed above is independent with $V$ because it satisfies the equation $P(\textbf{V})=\sum_{i=1}^k \alpha_i P(\textbf{V}x_i)$. Recall that for the above Markov chain the independence of $Z$ and $V$ implies $P(v)=\sum_{i=1}^k P(x_iz) P(vx_i)$ for all $v$ and $z$.

$\begingroup$ This nice argument needs a little more details, what is the sufficient condition for general random variable $X,V,Z$ (rather than binary one) to satisfy $I(X;ZV)=0$ $\Leftrightarrow$ $I(X;Z)=0$? i.e, what is the converse proof? We have already known the Fenchel extension of Caratheodory theorem as you asserted. Which property of boundary of Conv($\mathcal{A}$) makes you choose $p(z_2)$ from it? $\endgroup$ – user75459 Jun 28 '15 at 20:03