While reading The Elements of Information Theory on page 59. I got stuck in intuiting this line:

If p(y|x) is fixed, then p(y) is a linear function of p(x).

$p(y) = \sum_{x\in\mathcal{X}} p(y|x) p(x)$

If $p(y|x)$ is fixed, then $p(y)$ is obviously a linear function of $p(x)$.

PS: this is the theorem:

enter image description here

Could anyone please illustrate the linear relation between p(y) and p(x) given that p(y|x) is fixed?

  • $\begingroup$ Presumably $p()$ denotes a density. Is that correct? $\endgroup$
    – Glen_b
    Commented Sep 30, 2017 at 5:09

1 Answer 1


In Cover there is a common abuse of notation where $p(x)$ is meant as some distribution on $\mathcal{X}$. It is only literally interpreted as "the mass at $x$ for some distribution $p$ over $\mathcal{X}$" when $x$ is further specified (say for instance, if $x$ is being summed over). They often switch between the two meanings in a single context. Without exposure it only gets more confusing when you involve conditionals.

"The distribution $p(x)$ of $X$" is more properly denoted $p_X$. Extending this notation, it is clear what is meant by $p_Y$, $p_{X,Y}$ and $p_{Y|X=x}$.

By "$p(y|x)$ is fixed" here they mean "the distribution $p_{Y|X=x}$ over $\mathcal{Y}$ is fixed for each $x\in\mathcal{X}$."

What you are meant to see is that for $y\in \mathcal{Y}$, $x\in \mathcal{X}$: \begin{align} p_Y=\sum_{x} p_{X,Y}(x,\cdot)=\sum_x p_{Y|X=x}p_X(x) \end{align}

More info

This question touches on one thing I think Cover fails to stress enough. One of the main objects of interest in the book is a "noisy channel:" Notionally, if one feeds a noisy channel an input $x$, they get a random output $Y$ that has some distribution $p_{Y|X=x}$ over $\mathcal{Y}$. The underlying object being referred to when one talks about a "noisy channel" is this mapping from inputs to output distributions:

$$x\mapsto p_{Y|X=x}$$ This is why "fixing $p(y|x)$" is a natural, usual thing to do: it specifies a noisy channel.

  • 1
    $\begingroup$ A different way of looking at it: imagine a matrix $M\in \mathbb{R}^{\mathcal{X}\times \mathcal{Y}}$ where $[M]_{x,y}=p(y|x)$, and $p_X\in \mathbb{R}^{\mathcal{X}}$ as a row-vector specifying $X$'s distribution. Then $p_Y=p_X \cdot M$! So clearly $p_Y$ is a linear function of $p_X$. $\endgroup$ Commented Sep 30, 2017 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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