4
$\begingroup$

Consider two random variables $X,Y$. For simplicity, they are discrete and finite. Let $Q(y|x)$ be the conditional probability of $Y$ given $X$. Their mutual information is defined as:

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

where $H(Y)$ is the entropy of $Y$:

$$H(Y)=-\sum_y p_Y(y)\ln p_Y(y)$$

and $H(Y|X)$ is the conditional entropy of $Y$ given $X$, averaged over $X$:

$$H(Y|X)=-\sum_{x,y} p_X(x)Q(y|x)\ln Q(y|x)$$

The communications channel is defined by the distribution $Q(y|x)$, which determines the reliability of the channel. Given $Q(y|x)$, one would like to exploit as best as the information transfer capabilities of the channel. To do this, one has to chose a probability distribution $p_X(x)$ such that $I$, as defined above, is maximized (see Shannon–Hartley theorem; this maximum value of $I$ is called the channel's capacity).

My question is, given $Q(y|x)$, can you give an explicit, or implicit form for $p_X(x)$? Or maybe $p_Y(y)$ (which is determined by $p_X(x)$ as $p_Y(y) = \sum_x p_X(x) Q(y|x))$?

$\endgroup$
1
$\begingroup$

There is no general analytic solution to the maximization problem for finding channel capacity, but there is a well known numeric algorithm, called the Blahut–Arimoto algorithm.

For a given $Q(y|x)$, the algorithm iteratively computes

$$C = \max_{p} I(p, Q)$$

and produces as output both $p(x)$ and $C$. For a detailed description of the algorithm and proof of its behaviors, see:

  • Blahut, Richard. "Computation of channel capacity and rate-distortion functions." IEEE transactions on Information Theory 18.4 (1972): 460-473.
$\endgroup$

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.