Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.