[Math] Entropy of sum of two Uniform random variables

entropyrandom variables

say $X$ and $Y$ are two identical, independent and discrete Uniform random variables and $Z=X+Y$. I do not know more about the random variables.

Assuming $H(\cdot)$ to be the entropy of a random variable, I know that $H(Z) \geq \max\{H(X),H(Y)\}$. However, I wonder if a tighter bound exists given $X$ and $Y$ are discrete Uniform random variables?

any hint is appreciated.

Best Answer

Here's my attempt. We're using this definition for $H(X)$, for a discrete r.v. $X$ with probabilities $p_1, p_2, \ldots, p_n$: $$ H(X)=-\sum_{i=1}^n p_i \log_2(p_i) $$

We know that the sum of two i.i.d. discrete uniform r.v. is a discrete triangular r.v., call it $Z$. $Z$ is symmetrical, so even though the support extends to $2n$ we need only to evaluate the sum until midway. We also know that the probabilities $z_i$ of $Z$ are $\frac{1}{n^2}, \frac{2}{n^2},\ldots,\frac{n}{n^2},\frac{n-1}{n^2},\ldots,\frac{1}{n^2}$. Hence, we have, $$ \begin{aligned} H(Z) &= -2\sum_{i=1}^{n-1} z_i \log_2(z_i) - z_n \log_2(z_n)\\ &= -2\sum_{i=1}^{n-1} \frac{i}{n^2} \log_2 \left( \frac{i}{n^2} \right) -\frac{n}{n^2}\log_2 \left( \frac{n}{n^2}\right) \\ &= - \frac{2}{n^2} \sum_{i=1}^{n-1} i [\log_2(i) - 2\log_2(n)] + \frac{\log_2(n)}{n}\\ &= - \frac{2}{n^2} \left(\sum_{i=1}^{n-1} i \log_2(i) - 2\log_2(n) \sum_{i=1}^{n-1} i \right) + \frac{\log_2(n)}{n}\\ &= - \frac{2}{n^2} \left[\sum_{i=1}^{n-1} \log_2(i^i) - 2\log_2(n) \frac{n(n-1)}{2} \right] + \frac{\log_2(n)}{n}\\ &= \frac{2(n-1) \log_2(n)}{n}- \frac{2}{n^2} \log_2 \left(\prod_{i=1}^{n-1} i^i \right) + \frac{\log_2(n)}{n}\\ &= \frac{(2n-1) \log_2(n)}{n}- \frac{2}{n^2} \log_2 \mathcal{H}(n-1). \end{aligned} $$ In the derivation, $\mathcal{H}(x)$ is the hyperfactorial function. And you'll probably need to adjust the formula if $n$ is odd.

As a check, if $n=6$ (a fair dice), then the information entropy associated with the event that observes the sum of two dice is about $3.2744$ (checked with WolframAlpha). I am not familiar with this area, so I do not know if this is the actual result, but it seems reasonable.

Related Question