# Maximizing entropy for sum of random variables

Problem Setting

Let $X_1, X_2,\cdots,X_m$ be identical and marginally $Bern(p=0.5)$ random variables. There is no restriction on the joint distribution of $X_1, X_2,\cdots,X_m$.

Observation

The entropy $H(X_1, X_2,\cdots,X_m)$ is maximized (over all possible joint distributions) when $X_i's$ are independent. This can be proved by expanding the entropy term using chain rule

Question

Is the entropy of their sum, $S=X_1+X_2+\cdots+X_m$ also maximized when they are independent?

• Are we seeking to maximize the entropy (of the sum) over all possible joint distributions of $X_1,\ldots,X_m$ with the condition that the marginals need to be $Bern(0.5)$? – Juho Kokkala Aug 5 '16 at 9:43
• @Juho: Yes. I'll update the question. – Vivek Bagaria Aug 5 '16 at 17:55

No. The entropy of $S = X_1 + X_2+\cdots+X_m$ is maximized when $S$ is a uniformly distributed in $[m].$
Example for $m = 2$
$$P(X_1 = 0, X_2 = 0 ) = 1/3 \\ P(X_1 = 1, X_2 = 0 ) = 1/6 \\ P(X_1 = 0, X_2 = 1 ) = 1/6 \\ P(X_1 = 1, X_2 = 1 ) = 1/3$$ Tha above joint distribution in $X_1$, $X_2$ has the highest entropy for $H(X_1 +X_2)$. Also, by symmetry, $X_1$, $X_2$ are indentically distributed in the above distribution.