information and coding theory weakly independent problem

Question

$X$ is weakly independent of $Y$ if the rows of the transition matrix $\begin{bmatrix}p(x|y)\end{bmatrix}$ are linearly dependent.

1. Show that if $X$ and $Y$ are independent, then $X$ is weakly independent of $Y$.

2. Show that for random variables $X$ and $Y$, there exists a random variable $Z$ satisfying

   1. $X \to Y \to Z$, (markov chain)

   2. $X$ and $Z$ are independent, and

   3. $Y$ and $Z$ are not independent

   if and only if $X$ is weakly independent of $Y$.

thank you..

$X \to Y \to Z$ markov chain

Answer 1

I suspect that the second problem should be "$Y$ weakly independent of $X$". I leave it open to further discussion and I prove the second part for this new formulation.

---

First part: For the first part, if $X$ and $Y$ are independent, then $p(x_i|y_j)=p(x_i)$ and therefore each row vector is $[p(x_i)\dots p(x_i)]=p(x_i)\times \mathbf 1_{1\times N}$ where $N$ is cardinality of $Y$. Therefore, excluding trivial cases, all rows are product of each other and linearly dependent. Similarly $Y$ is also weakly independent of $X$.

Second part: Here I am proving the necessary and sufficient conditions of 1-3 for $Y$ be weakly independent of $X$ and not the other way.

Now suppose that three conditions hold. We can see from independence that: $$ p(z_k)=p(z_k|x_i)=\sum_{j=1}^N p(z_k|y_j,x_i)p(y_j|x_i)=\sum_{j=1}^N p(z_k|y_j)p(y_j|x_i) $$ On the other hand, we know that: $$ \sum_{j=1}^N p(y_j|x_i)=1 $$ which means the following: $$ \sum_{j=1}^N \left(p(z_k|y_j)-p(z_k)\right)p(y_j|x_i)=0\implies \\ \sum_{j=1}^N \left(\frac{p(z_k|y_j)-p(z_k)}{p(y_j)}\right)p(x_i|y_j)=0 $$ This means that the columns of $[p(x|y)]$ are linearly dependent.

So given your conditions $Y$ is weakly independent of $X$, however I cannot say anything for the moment if $X$ is also weakly independent of $Y$ or not.

---

Assume that rows are linearly dependent, and $\alpha_i$ is the coefficient of the row $i$ in the linear dependence equation. W.l.g. we can assume $|\alpha_i|\leq 1$. So we have: $$ \alpha_1 p(x_1|y_j)+\dots+\alpha_M p(x_M|y_j)=0, $$ where $M$ is cardinality of $X$. On the other hand: $$ p(x_1|y_j)+\dots+ p(x_M|y_j)=1. $$ Summing up the two we get: $$ (1+\alpha_1) p(x_1|y_j)+\dots+(1+\alpha_M) p(x_M|y_j)=1. $$ By some scalings, we can find $\beta_i\in[0,1]$ and summing up to one, such that: $$ \beta_1 p(x_1|y_j)+\dots+\beta_M p(x_M|y_j)=\zeta. $$ Define a random variable $Z$ with conditional probability such that $p(z_k|x_i,y_j)=\beta_i$. Note that size of each row vector is $N$. therefore we have $M$ vectors in $N$-dimensional spaces. The cardinality of $Z$ is therefore equal to cardinality of all distinct, up to scaling, linear dependence of rows, which is the cardinality of Kernel space of rows.

First of all the conditional probability is independent of $j$, which means that we have a Markov chain $Z\rightarrow X \rightarrow Y$. On the other hand, the previous equality means: $$ p(z_k|y_j)=\zeta $$ which is the same for all $j$'s and therefore we can see $Z$ is independent of $Y$. Therefore if $X$ is weakly independent of $Y$, we could find $Z$ independent of $Y$, dependent on $X$, and satisfying $Z\rightarrow X \rightarrow Y$.

---