Compute in practice a channel capacity

Question

I need to compute the capacity of a channel which takes a vector input $X=(x_1,x_2,\ldots,x_n)$ and returns a vector $Y$ which is exactly $X$ but where a random block has been reversed, for example:

$X=(x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8)\xrightarrow{\text{ }Channel\text{ }} Y=(x_1,\color{red}x_\color{red}5\color{red},\color{red}x_\color{red}4\color{red},\color{red}x_\color{red}3\color{red},\color{red}x_\color{red}2,x_6,x_7,x_8)$

I now that in theory I have the formula $C=H(Y)-H(Y|X)$ where $H(\cdot)$ is the entropy function but what if I don't have even probability distributions for $Y$ and $X$ and $Y|X$?

I've seen before the Capacity (or an upperbound on it) been compute as a limit on $n$ of something about the number of posible $Y$'s (which in this case is $\binom{n}{2}$ because this way you count all the posible blocks that can be reversed) but I don't know what to do with that information.

Thanks for your help.

Answer 1

Here I try to derive only the mutual information. As I discuss later, the problem seems to be difficult in general.

To obtain capacity, the important point is to characterize the conditional probability $P_{Y|X}$ of the channel. After that $H(Y)$ and $H(Y|X)$ can be computed as a function of the input distribution $P_X$ which should be optimized later to maximize $I(X;Y)$ and obtain the capacity.

Consider a fixed $n$ and let $X$ be a column vector of dimension $n$. Suppose the the entries of $X$ are discrete so we use discrete entropy. The channel can be written as: $$ Y=AX, $$ where $A$ is randomly chosen from the following subset of permutation matrices: $$ \mathcal A=\left\{A\in\mathbb R^{n\times n}: A=\begin{pmatrix}I_1&0&0\\0&J_2&0\\0&0&I_3\end{pmatrix}\text{ for some } I_1,I_3,J_2\right\}, $$ with $I_1$ and $I_3$ identity matrices and $$ J_2=\begin{pmatrix}0&\dots&0&1\\0&\dots&1&0\\1&\dots&0&0\end{pmatrix}. $$ Note that $J_2$ acts on the block that is reversed. The matrix $A$ is randomly generated by randomly picking a block and associating $J_2$ to that block.

If $Y=y$ is a block-reversed version of $X=x$, then the matrix $A$ can be determined from $x$ and $y$. The matrix is not unique however. Denote the set of these matrices by $A(x,y)$. If $y$ is a block reversed version of $x$, we have: $$ P(Y=y|X=x)=P(AX=y|X=x)=P(A\in A(x,y)) $$ Otherwise $P(Y=y|X=x)=0$. Define the set $T$ and $T_y$ as follows: $$ T=\left\{(x,y):Ax=y\text{ for some } A\in\mathcal A\right\}\\ T_y=\left\{x: Ax=y\text{ for some } A\in\mathcal A\right\}. $$ Hence if $(x,y)\in T$, then $y$ is a block-reversed version of $x$.

Since no particular assumption is given here, we examine uniform distribution as an example.

Assume that we have a uniform distribution on $A$ with $P(A=A_0)=\frac 1{\binom{n}{2}}$. Then, this implies that: $$ P(Y=y|X=x)=\frac {|A(x,y)|}{\binom{n}{2}}\\ P(Y=y)=\sum_{x}P(Y=y|X=x)P(X=x)=\sum_{x\in T_y}\frac{|A(x,y)|}{\binom{n}{2}}P(X=x)=\frac{E(|A(X,y)|)}{\binom{n}{2}}. $$ Therefore: \begin{align} H(Y|X)&=E(\log\frac{1}{P(Y|X)})\\ &=\sum_{(x,y)\in T}P(X=x)\frac {|A(x,y)|}{\binom{n}{2}}\log{\frac {\binom{n}{2}}{|A(x,y)|}}\\ &=\frac{\log{\binom{n}{2}}}{\binom{n}2}\sum_{y}E(|A(X,y)|)+\sum_{(x,y)\in T}P(X=x)\frac {|A(x,y)|}{\binom{n}{2}}\log{\frac {1}{|A(x,y)|}}. \end{align} and \begin{align} H(Y)&=E(\log\frac{1}{P(Y)})\\ &=\sum_{y}E(|A(X,y)|)\frac{1}{\binom n2}\log\frac{{\binom{n}{2}}}{E(|A(X,y)|)} \end{align} So the mutual information is obtained as:

$$ I(X;Y)=\frac{1}{\binom n2}\sum_{(x,y)\in T}P(X=x)|A(x,y)|\log\frac{|A(x,y)|}{E(|A(X,y)|)}. $$

I am not sure how useful this expression is. From now on, we require to know more about the support of $X$. Even with that, e.g. assume vectors on $\mathbb F_2^n$, I do not see any straightforward way to obtain the optimal distribution.

Answer 2

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

Let's assume that the (contiguous) block must have at least two elements, and that all $\binom{n}{2}$ blocks are equiprobable.

Now, $H(Y \mid X=x) \le \log \binom{n}{2}$. This is because there at most $\binom{n}{2}$ different possible values of $Y$ for the given $x$ (it can be less, because if $x$ have repeated values, then different inversion blocks can produce the same $y$).

More in detail, if we denote by $A$ the random variable that corresponds to the block choosing, then the chain rule gives $H(Y A \mid X) = H( Y \mid A X) + H(A\mid X)=H(A\mid Y,X) + H(Y\mid X)$ . But $H( Y \mid A X) =0$ and $H(A\mid X)=H(A)=\log \binom{n}{2}$ . Then $H(Y\mid X)=\log \binom{n}{2}- H(A\mid Y,X) \le \log \binom{n}{2} $

Then $$I(X;Y)= H(Y) + H(A\mid Y,X) - \log\binom{n}{2} \ge H(Y) - \log\binom{n}{2} \tag{1}$$

The $H(Y)$ term is maximized by using the max entropy for each $X$ component (let's call it $h_x$), and making them independent, so that $H(Y)=H(X)=n h_X$

Then $$C \ge n h_X - \log \binom{n}{2} \tag{2}$$

If $n$ is large, the second term is approximately $\log( n^2/2)=2 \log(n) -1$. Further, if $X$ is binary, then $h_x =1$ and then (approximate upper bound)

$$ C \ge n - 2 \log n +1 \tag{3}$$

To get a (non trivial) lower bound seems more difficult.