Compute in practice a channel capacity 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.
 A: 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. 
A: 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.
