0
$\begingroup$

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 $V-X-Z$ and $Z$ and $V$ are independent.

$\endgroup$
  • $\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 "$V-X-Z$" 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
0
$\begingroup$

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(v|x)\}$. 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 well-known that $\dim(\text{conv}(G))=\dim(\text{span}(G))-1$. Suppose $\dim(\text{span}(G))=d$ and hence $\dim(\text{conv}(G))=d-1$. By assumption, $d\leq k-1$. 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_i|z) P(v|x_i)$ for all $v$ and $z$.

$\endgroup$
  • $\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;Z|V)=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

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.