# What does it mean when we say p(y|x) is fixed?

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:

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

• Presumably $p()$ denotes a density. Is that correct? – Glen_b Sep 30 '17 at 5:09

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}

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.
• 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$. – Christian Chapman Sep 30 '17 at 10:11