Consider the following setup: $(X, Y)$ is a doubly symmetric binary source with parameter $0 < p < 1/2$, i.e., $X \sim \text{Bernoulli}(1/2)$, $Z \sim \text{Bernoulli}(p)$ and $Y = X \oplus Z$. Let $(U, V)$ be another pair of binary variables, where $U$ is derived from $X$ and $V$ is derived from $Y$, i.e., the Markov chain $U - X - Y - V$ holds. My question is the following: Can you find binary random variables $U'$ and $V'$ such that $U' - X - Y - V'$ form a Markov chain and the channels $X \rightarrow U'$ and $Y \rightarrow V'$ are binary symmetric channels with ($I(\cdot;\cdot)$ denotes mutual information.)

$I(U';X) \le I(U;X)$, $I(V';Y) \le I(V;Y)$, and $I(U'; V') \ge I(U;V)$ ?

The question can also be phrased in terms of the probabilities of the binary symmetric channels: Are there values $0 \le r,q \le 1/2$ such that

$1 - h(r) \le I(U;X)$, $1 - h(q) \le I(V;Y)$, and $1 - h(r * p * q) \ge I(U;V)$ ?

($h(x) = -x \cdot \log_2(x) - (1-x) \cdot \log_2(1-x)$ is the binary entropy function and $p * q = p*(1-q) + (1-p)*q$ the binary convolution.)

I did some numerical evaluation which suggests a positive answer to that question: Choosing $r,q$ such that $1 - h(r) = I(U;X)$ and $1 - h(q) = I(V;Y)$, it seemed that $1 - h(r * p * q) \ge I(U;V)$ is always satisfied. But I don't know how to formally prove this statement. I wasn't lucky trying to apply Mrs. Gerber's Lemma in this context. I also tried splitting the problem in two stages: First fix $V'=V$ and try to show that a BSC $X \rightarrow U'$ with $I(U';X) \le I(U;X)$ maximizes $I(U'; V')$. But I have a counterexample to this claim, so it appears necessary to consider both channels simultaneously.


2 Answers 2


No. You can get a higher $I(U;V)$ using asymmetric channels. Below I construct a counterexample, but first a more succinct restatement of the question.


To summarize, there is an input $U$ distorted by three independent binary hops, each described by $2\times 2$ stochastic matrices $C_L,\ C,\ C_R.$ Labeling all your RV's, $$U\overset{C_L}{\to}X\overset{C}{\to}Y\overset{C_R}{\to}V.$$ We are interested in maximizing $I(U;V)$ subject to constraints:

  • $C$ is determined by nature.
  • $C_L$ is such that $I(U;X) \leq r_L$,
  • $C_R$ is such that $I(Y;V) \leq r_R$,
  • $U$'s distribution is such that the left channel's output (i.e. $X$) is $B(1/2)$.


You claim the $C_L,C_R$ which produce the maximum are binary symmetric.

  • If $C_L$ is a BSC with $B(1/2)$ output then its input must also be $B(1/2).$ For a given rate $r_L \leq 1$, then there is at most one 'positive' (i.e. can't be improved by relabeling the outputs) BSC $C_L$ whose output is $B(1/2).$
  • You have assumed $C$ is a BSC, so with a symmetric input its output is also symmetric.
  • For a rate $r_R\leq 1$ there is only one positive choice for $C_R.$

So to say they are binary symmetric is to determine all of $U,C_L$ and $C_R$.

Now take $C$ a perfect channel, $C= \left[\begin{smallmatrix} 1 & 0 \\ 0 & 1 \end{smallmatrix}\right]$ and $r_L=r_R=0.4.$ The associated positive BSC for this rate has crossover probability $\approx 0.15,$ and the end-to-end mutual information can be computed: $$I(U_{BSC}, V_{BSC})< 0.1895$$

However, trying randomly[1] you can find $U^\ast, C_L^\ast, C_R^\ast$ that satisfy all the mutual information constraints, but have greater $U$-to-$V$ mutual information. One I found happens to be quite close to a Z-channel:

\begin{equation} I(U^\ast; V^\ast) > 0.19, \end{equation} \begin{equation} C_L^\ast \approx \left[\begin{smallmatrix}0.2493 & 0.7507 \\ 0.9657 & 0.0343 \end{smallmatrix}\right], \qquad C_R^\ast \approx \left[\begin{smallmatrix} 0.9821 & 0.0179 \\ 0.3374 & 0.6626 \end{smallmatrix}\right], \qquad U^\ast \sim B(0.35) \end{equation}


This result is to be expected since there is a vague sense that uniform noise over a bounded space is the most degrading, even holding mutual information fixed. (by one heuristic "uniform noise means you can't precode to mitigate it")

A gentle introduction for a good, visualisable framework for studying binary symmetric channels is given in a short paper, Algebraic Information Theory for Binary Channels by Martin, Moskowitz and Allwein. Under this framework your maximization can be restated as a convex optimization problem for which I see no easy special cases.

An easier-to-investigate (and arguably more interesting) problem is one identical to yours that omits the fourth constraint that $X\sim B(1/2)$. But I could not find an easy path towards an answer for this either.

For both of these there might be some magical connection to KL divergence which I am not seeing.


[1]: Below is a crude counterexample finder.

% Helper functions
    % Binary entropy
fn_h = @(p) -p.*log2(p) - (1-p).*log2(1-p); 
    % MI across mtx_bc when v_distn is input
fn_I = @(mtx_bc,v_distn) fn_h(v_distn(1)) + fn_h(v_distn*mtx_bc(:,1)) ...
    - nansum(nansum(-log2(diag(v_distn)*mtx_bc).*(diag(v_distn)*mtx_bc)));
    % Channel matrix when P(out=0|in=0)=pa, P(out=0|in=1)=pb
fn_mtxBC = @(pa,pb) [pa, 1-pa; pb, 1-pb];

% Set params
d_r_L = 0.4; 
d_r_R = 0.4;
d_xp = 0.146102; % solution to 1-H(p) = 0.4
mtxBSC = fn_mtxBC(d_xp, 1-d_xp);

% Search 
while true
    mtxL = fn_mtxBC(rand, rand);
    mtxR = fn_mtxBC(rand, rand);
    v_d = (mtxL'\[0.5, 0.5]')';
    if (abs(sum(v_d)-1) > 0.001 || ...
        min(v_d) < 0)
    if(fn_I(mtxL, v_d)      > 0.4 || ...
       fn_I(mtxR, v_d*mtxL) > 0.4)
    if fn_I(mtxL*mtxR, v_d) > fn_I(mtxBSC*mtxBSC, [0.5, 0.5])
  • $\begingroup$ I believe your statement of the problem is accurate. You can indeed require all the Z's to be independent due to the Markov constraint. However, numerical evidence suggest that this conjecture does hold (not only in trivial cases). Could you give me an explicit counterexample? You state that uniform noise is the most "degrading" and "maximally bad". In which sense? Not in the sense of mutual information over each intermediate hop, as we choose U' and V' precisely to preserve this quantity. $\endgroup$ May 18, 2017 at 9:09

the channel does not maximize the mutual information, the source can select a distribution to maximize the mutual information and achieve a mutual information close to the capacity for a given channel. the best channel is an one to one mapping $f$ so $I(X,f(X))=I(X,X)=H(X)$. You can also use the data processing inequality for the Markov chain.

$I(V;U)\leq min \{ I(V;X,Y),I(U;X,Y)\}=min \{ I(V;Y),I(U;X)\}$

$I(V',U')\leq min \{ I(V';X,Y),I(U';X,Y)\}=min \{ I(V';Y),I(U';X)\}\leq min \{ I(V;Y),I(U;X)\} $

Sorry I don't have enough points to comment.

  • 1
    $\begingroup$ I don't udnerstand how your answer relates to this problem. Choosing $U'=X$ certainly maximizes mutual information but in general violates the first condition $I(U';X) \le I(U;X)$. Moreover, beware that $U'$ and $V'$ need to be generated by a binary symmetric channel. Hence, you are not free to choose them arbitrarily. Please clarify. $\endgroup$ Apr 20, 2016 at 9:28
  • $\begingroup$ sorry I have not understood it. What do you mean by find binary random variables $U'$ and $V'$ ? Also is there any other constraint for $U$ and $V$ apart from $I(U';X) \le I(U;X)$, $I(V';Y) \le I(V;Y)$. Can $U=X$ or $V=Y$? $\endgroup$
    – Cauchy
    Apr 21, 2016 at 0:06
  • $\begingroup$ I think the phrasing of the question is pretty clear. I tried to make this more explicit: $U,X,Y,V$ are binary random variable satisfying the Markov chain $U-X-Y-V$ and $(X,Y)$ constitute a doubly symmetric binary source with parameter $p$ (DSBS($p$)). Other than that, $U$ and $V$ are arbitrary. The special case $U=X$ is of course trivial and follows straightforward from Mrs. Gerber's Lemma. The question is now, if there exist binary random variables $U'$ and $V'$ satisfying the given constraints. I do not see how your answer relates to this question. $\endgroup$ Apr 21, 2016 at 11:52
  • $\begingroup$ If $U=X$ and $V=Y$ then $I(U';X) \leq I(U;X)$, $I(V';Y) \leq I(V;Y)$, and $I(U'; V') \leq I(U;V)$ do you agree or am I missing something ? $\endgroup$
    – Cauchy
    Apr 21, 2016 at 19:04
  • $\begingroup$ What you claim is correct. But maybe I wasn't clear enough: $U$ and $V$ are part of the problem description. You are not allowed to choose them freely. All you know about $U,V,X,Y$ is that 1) all of them are binary, 2) $(X,Y)$ is a DSBS($p$) and 3) the Markov chain $U-X-Y-V$ holds. This does by no means imply $U=X$ or $V=Y$. Then the question is if $U'$, $V'$ exist satisfying the given conditions. Did I explain that clearly? $\endgroup$ Apr 22, 2016 at 11:14

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.