2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ It would be good if you could give some information on the context of the problem as well. $\endgroup$
    – Arash
    Sep 19, 2018 at 15:36
  • $\begingroup$ You need to specify which probability law dictates the selection of the block to be reversed. $\endgroup$
    – leonbloy
    Sep 21, 2018 at 3:17
  • $\begingroup$ @Arash, I'm sorry this was a problem that occurred to me watching a magic show on television, so I didn't think in all the details I was just wondering how a channel like this could work... I thought in a binary, memoryless and discrete channel where the probability of all blocks to be reverse is the same. $\endgroup$
    – Luis GC
    Sep 21, 2018 at 8:05
  • $\begingroup$ @leonbloy As I say in the comment above, this is a binary, memoryless and discrete channel where the probability of all blocks to be reversed is the same. $\endgroup$
    – Luis GC
    Sep 21, 2018 at 8:07

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ thanks for your help @leonloy, there is some things I don't understand yet, 1) "This is because there at most $\binom{n}{2}$ different possible values of $Y$ for the given $y$" it's not "Y" completely defined when you determine "y"? 2) Why $H(Y)=H(X)$? 3) Why you say it is an upperbound if $C$ is bigger than $n-2\log n +1$? Also, just to try, I used Stirling's approximation formula in your result $\log\binom{n}{2}$ and I get $n\log\frac{n}{n-2} +2\log(n-2)-log 2 -2+O(\log n)-O(\log(n-2))$ to have a tighter bound (which it is), but I am not quite sure of how to operate with the $O$'s. $\endgroup$
    – Luis GC
    Sep 21, 2018 at 7:55
  • $\begingroup$ also, what does it means that $C$ is bigger that $n+something$ this means that asymptotically the channel has an infinite capacity? $\endgroup$
    – Luis GC
    Sep 21, 2018 at 8:20
  • $\begingroup$ 1) I meant "for the given $x$", of course. Fixed 2) $H(Y)=H(X)$ if $X$ are iid (because then $P(Y)=P(X)$ 3) No need to use Stirling approximation, $\binom{n}{2} = \frac{n(n-1)}{2} \approx n^2/2$ $\endgroup$
    – leonbloy
    Sep 21, 2018 at 11:57
  • $\begingroup$ Yes, for $n \to \infty$ the channel has infinite capacity $\endgroup$
    – leonbloy
    Sep 21, 2018 at 11:59
  • $\begingroup$ I added some explanation for the first inequality $\endgroup$
    – leonbloy
    Sep 21, 2018 at 12:08
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ "Note that if $Y=y$ is a block-reversed version of $X=x$, then the matrix $A$ can be uniquely determined from $x$ and $y$". I'm not sure if I understand that. If $x=[1 2 3 1]$ and $y=[1 3 2 1]$ then you have two possible $A$, right? $\endgroup$
    – leonbloy
    Sep 21, 2018 at 3:23
  • $\begingroup$ Thaks for your answer @Arash, I love the way you described the channel with the matices, Its very visual and easy to get, I don't understand, as leonbloy comments above, why there is a bijection between $A$ and $(x,y)$ $\endgroup$
    – Luis GC
    Sep 21, 2018 at 8:24
  • $\begingroup$ Your comments are definitely right; this is not a bijection; I will edit. $\endgroup$
    – Arash
    Sep 22, 2018 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .