As we all know, formula for mutual information is as follows:

$ I(X, Y) = H(Y) - H(Y|X) $

In case of Binary Symmetric Channel with flip probability equal to $f$ and both alphabets of size $2$:

$ I(X, Y) = H(Y) - H(Y|X) = log2 - H(f) = 1 - H(f) $

I'm confused about the equality $H(Y) = log2$ a little bit. Is it always the case that entropy of output is equal to $log$ of size of alphabet? If not, could you give me an example of such a channel?

Thank you


1 Answer 1


It is not always true. However, the entropy of a discrete random variable $Y$ on a finite alphabet $\mathcal{Y}$ is always upper bounded by $\log |\mathcal{Y}|$: this is because the uniform distribution on $\mathcal{Y}$ maximizes the entropy.

So for the mutual information, because

$$I(X; Y) = H(Y) - H(Y | X)$$

the first term is maximized when $Y$ is uniform. Luckily, for the BSC we can choose $X$ to be uniform, which will also make $Y$ uniform. Since the distribution of $Y$ given $X$ is just $\mathrm{Bernoulli}(f)$, the second term doesn't depend on the distribution of $X$ at all. Therefore we can just choose the distribution of $X$ to maximize $H(Y)$.

It's not true in general that we can make $H(Y) = \log |\mathcal{Y}|$ in order to maximize the mutual information: sometimes that will also make $H(Y | X)$ large so the difference is smaller than it would be with another choice of $X$.


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.