This is the question I met while reading Shannon's channel coding theorem. Assume a random variable $X$ is transmitted through a noisy channel with transition probability $p(y|x)$. At the receiver a random variable $Y$ is obtained. Assume we have an additional random variable $X'$ which is independent of $X$. How to show that $X'$ is independent of bivariate random variable $(X,Y)$ and $X'$ is independent of $Y$? It looks obvious because $Y$ is generated only from $X$, but I just can not prove it rigorously, i.e., that $p(x,y|x')=p(x,y)$ and $p(y|x')=p(y)$. Thanks a lot for your answer!

-

There does not seem to be enough information in your model to decide that. In order to do so, you need to have specified the joint distribution of $(X,Y,X')$.

1. You have specified the conditional distribution of $Y$ given $X$ (there seems to be a typo in your question), which together with marginal distribution of $X$ gives the joint distribution of $(X,Y)$.
2. You have also said that $X$ and $X'$ are independent which gives the joint distribution of $(X,X')$.

There is more that one joint distribution on $(X,Y,X')$ which agrees with these two pieces of information.

Here is the example: Consider $X$ to be a symmetric Bernoulli random variable (i.e. takes values 0 and 1 with equal probabilities). Let $X'$ be independent of $X$, with the following distribution $$X' \sim \begin{cases} 0 & \text{w.p.} \;0.9\\ 100 & \text{w.p.} \;0.1 \end{cases}$$ Also, take $X'$ to be the channel noise and let $Y = X + X'$. Conditioned on $X' = 0$, $Y$ has the same distribution as $X$, while conditioned on $X' = 100$, $Y$ takes values $100$ and $101$ with equal probabilities. Hence $X'$ and $Y$ are not independent.

-
but $X'$ and $Y$ are indeed independent in the proof to show subsequent results. Let's assume $X'$ and $X$ have the same distribution. –  Zhou Heng Feb 17 '13 at 6:08
There are probably more assumptions implicitly made. It might have been easily assumed that $X'$ is independent of $(X,Y)$. –  passerby51 Feb 17 '13 at 6:22
Yes, I must have omitted some assumptions, but I don't know what they are. Currently the assumptions can be summarized as: $X$ and $X'$ are iid with common probability $p(x)$. $Y$ is generated from $X$ according to the trasition probability $p(y|x)$ (sorry for the typo in the original post; I have corrected it). I really can not think of any other assumptions. Maybe someone who read the proof of Shannon's channel coding theorem before and familiar with random coding and joint typicality can answer this question. –  Zhou Heng Feb 17 '13 at 7:38
The answer to that is pretty clear: one ASSUMES that $X'$ is independent of $(X,Y)$. –  Did Feb 17 '13 at 7:39
Note that Y is generated solely from X... Not in the sense you believe. In fact Y is generated by X and by some external randomness. Otherwise, the transition kernel $p(y\mid x)$ mentioned in your question would be degenerate, in the sense that for each given $x$, $p(y\mid x)$ would be zero except for one value of $y$. –  Did Feb 17 '13 at 8:35

Two given conditions are:

(1)$X'$ is independent of $X$,

(2)$Y$ is generated only from $X$, i.e., $p(y|x)=p(y|x,x')$. This acutually means $X'\to X\to Y$ forms a Markov chain.

Now let's prove $X'$ is independent of bivariate random variable $(X,Y)$, i.e., $p(x,y|x')=p(x,y)$:

$p(x,y|x')=p(x|x')p(y|x,x')=p(x)p(y|x,x')$(from (1))$=p(x)p(y|x)$(from (2))$=p(x,y)$.

It can easily shown that if $X'$ is independent of $(X,Y)$, then $X'$ is independent of each component. I have shown $X'$ is independent of $(X,Y)$, so $X'$ is also independent of $Y$.

-