# Capacity of Binary Erasure Channel

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)})}.$$
• I don't understand the first argument. Why can we assume $p(x=0)=p(x=1)$? – Xugui Manuel Apr 22 at 11:20
• 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. – Yuval Filmus Apr 22 at 11:22