Consider two identically distributed independent random vectors $X$ and $Y$ of dimension $n$ (assume $n$ is large). Both $X$ and $Y$ have only non-negative integer entries less than or equal to $n$ and $H(X)= H(Y) = n$.

What is the maximum possible value of $H(X + Y)$?

In particular, how close can it get to $2n$?

My working so far

If $X$ and $Y$ are random $0/1$ vectors then $H(X+Y) = 3n/2$ I believe. This is the highest value for $H(X+Y)$ I have managed to find so far.


There is a well known bound on $H(X+Y)$ i.e., $\max{\{H(X),H(Y)\}}\leq H(X+Y) \leq H(X)+H(Y)$. Hence the maximum possible value of $H(X+Y)$ is $H(X)+H(Y)$. Equality holds iff $X=Y$. Hence $H(X+Y)\leq 2n$, and it can come close to $2n$ by picking same value for $X$ and $Y$ always (to be more precise $X=Y$ almost surely).

For proof of above bound, one can refer to http://www2.isye.gatech.edu/~yxie77/ece587/SumRV.pdf

  • $\begingroup$ $X$ and $Y$ are independent in this question so it's not clear your answer works (apart from the upper bound). $\endgroup$ – user66307 Dec 13 '15 at 8:32
  • 2
    $\begingroup$ I don't think this answers my question. In my case $X$ and $Y$ are independent as Lembik points out. $\endgroup$ – dorothy Dec 13 '15 at 9:06
  • $\begingroup$ The key is that they are independent and identically distributed. $\endgroup$ – felipa Dec 13 '15 at 9:59

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.