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.


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$ Apr 22 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$ Apr 22 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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