5
$\begingroup$

The channel under consideration is $T = A + B$, where $A$ and $B$ take on values in $\{0, 1\}$ according to a probability mass function. Let (joint) random vector $(A_1, A_2,\ldots, A_n)$ be denoted as $A^n$. Addition is performed in $Z$ as opposed to $Z_2$. Let $H_\alpha(X)$ denote the Renyi entropy of order $\alpha$ for (discrete) probability distribution $X$ (http://en.wikipedia.org/wiki/Renyi_entropy). In this problem, $0 < \alpha < 1$. The problem is to maximize $H_\alpha(A_1+B_1, A_2+B_2, \ldots, A_n+B_n)$ over all joint distributions $A^n$ and $B^n$ subject to the constraint that $A^n$ is independent of $B^n$ (all random variables take on values in $\{0, 1\}$). The conjecture is that the maximum occurs at $A_i$, $B_j$ all uniformly (and independently) distributed on $\{0, 1\}$, i.e $H_\alpha(A_1+B_1, A_2+B_2, \ldots, A_n+B_n) \leq nH_\alpha([0.25, 0.5, 0.25])$.

For $n = 1$, a smoothing argument gives the result. Computer simulations suggest that the result is true for $n = 2$ and $n = 3$ (higher n is difficult to simulate). Computer code also confirms that smoothing arguments do not work for $n = 2$. For now, I am just focusing on $n = 2$. An equivalent (more explicit) reformulation for $n = 2$ is the inequality: $(p_0q_0)^\alpha + (p_1q_1)^\alpha + (p_2q_2)^\alpha + (p_3q_3)^\alpha + (p_0q_1 + p_1q_0)^\alpha + (p_0q_2 + p_2q_0)^\alpha + (p_1q_3 + p_3q_1)^\alpha + (p_2q_3 + p_3q_2)^\alpha + (p_0q_3 + p_1q_2 + p_2q_1 + p_3q_0)^\alpha \leq \frac{1}{4^\alpha} + \frac{4}{8^\alpha} + \frac{4}{16^\alpha}$, where $[p_0, p_1, p_2, p_3]$ and $[q_0, q_1, q_2, q_3]$ are probability vectors.

I would greatly appreciate any ideas as to how one may go about proving/disproving $n = 2$ case, and hopefully the general $n$ case as well.

Update: Seeing the form of the problem ($n = 2$), I believed that Karamata's inequality looks very promising (http://en.wikipedia.org/wiki/Karamata%27s_inequality). However, counterexamples were easily generated to show that majorization does not necessarily hold here. If it is of any help, Karamata's "almost goes through", in the sense that from all the examples I could generate, majorization, if it failed, failed only on the largest element comparison.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.