Consider the the binary erasure channel, with input and output alphabet $\{0,?,1\}$ and channel matrix \begin{bmatrix} 1-\lambda-\mu & \mu & \lambda\\ 0 & 1 & 0\\ \lambda & \mu & 1-\lambda-\mu \end{bmatrix} I want to determine its capacity, i.e. maximize $I(X;Y)$ over the probabilities distribution of the input.

I have tried writing and rewriting $I(X;Y)$ in different ways but the expression gets too complicated and I can't find a way to assign values to $p(x)$ so that $I(X;Y)$ is maximized. Any suggestions? Thank you in advance.


1 Answer 1


By symmetry, we can assume that $\Pr[X=0] = \Pr[X=1] = p$, and so $\Pr[X=?] = 1-2p$. We can then express $I(X;Y)$ as a function of $p,\lambda,\mu$. The capacity of the channel is the maximum of $I(X;Y)$ over all $p \in [0,1/2]$. You can find this maximum using calculus.

In more detail, let us first note that $\Pr[Y = 0] = \Pr[Y = 1] = (1-\mu)p$ and $\Pr[Y=?] = 1-2(1-\mu)p$. Furthermore, $H(Y|X=?) = 0$ and $H(Y|X=0) = H(Y|X=1) = H(1-\lambda-\mu,\lambda,\mu)$. Therefore $$ I(X;Y) = H((1-\mu)p,(1-\mu)p,1-2(1-\mu)p) - 2pH(1-\lambda-\mu,\lambda,\mu). $$ The derivative of this with respect to $p$ is $$ -2(1-\mu)\log((1-\mu)p)+2(1-\mu)\log(1-2(1-\mu)p) - 2H(1-\lambda-\mu,\lambda,\mu) = \\ 2(1-\mu) \log \frac{1-2(1-\mu)p}{(1-\mu)p} - 2H(1-\lambda-\mu,\lambda,\mu). $$ Equating this to zero, we get $$ \log \frac{1-2(1-\mu)p}{(1-\mu)p} = \frac{H(1-\lambda-\mu,\lambda,\mu)}{1-\mu} $$ and so $$ \frac{1-2(1-\mu)p}{(1-\mu)p} = e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)}. $$ Massaging this, we finally get $$ p = \frac{1}{(1-\mu)(2 + e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)})}. $$

  • $\begingroup$ I don't understand the first argument. Why can we assume $p(x=0)=p(x=1)$? $\endgroup$
    – user128868
    Commented Apr 22, 2021 at 11:20
  • $\begingroup$ This requires a symmetrization argument. If you take an arbitrary distribution and symmetrize it, then this can only increase $I(X;Y)$, due to concavity of mutual information. Details left to you. $\endgroup$ Commented Apr 22, 2021 at 11:22

Your Answer

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