Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do we get the functional form for the entropy of a binomial distribution? Do we use Stirling's approximation? According to Wikipedia, the entropy is $\frac1 2 \log_2 \big( 2\pi e\, np(1-p) \big) + O \left( \frac{1}{n} \right)$.

As of now, my every attempt has been futile so I would be extremely appreciative if someone could guide me or provide some hints for the computation.

share|improve this question
2  
A comment: the entropy of the normal distribution with variance $\sigma^2$ is ${1 \over 2} \log (2\pi e \sigma^2)$, which can be computed by a fairly straightforward integration. Perhaps using Stirling's approximation you can reduce the computation of the entropy of the binomial to this same integral plus some error terms. (I haven't actually tried to do this.) –  Michael Lugo Nov 25 '12 at 19:51

1 Answer 1

up vote 8 down vote accepted

This answer follows roughly the suggestion of @MichaelLugo in the comments.

We are interested in the sum $$H = -\sum_{k=0}^n {n\choose k}p^k(1-p)^{n-k} \log_2\left[{n\choose k}p^k(1-p)^{n-k} \right].$$ For $n$ large we can use the de-Moivre-Laplace theorem, $$H \simeq -\int_{-\infty}^\infty dx \, \frac{1}{\sqrt{2\pi}\sigma} \exp\left[-\frac{(x-\mu)^2}{2\sigma^2}\right] \log_2\left\{\frac{1}{\sqrt{2\pi}\sigma} \exp\left[-\frac{(x-\mu)^2}{2\sigma^2}\right] \right\},$$ where $\mu = n p$ and $\sigma^2 = n p(1-p)$. Thus, $$\begin{eqnarray*} H &\simeq& \int_{-\infty}^\infty dx \, \frac{1}{\sqrt{2\pi}\sigma} \exp\left[-\frac{(x-\mu)^2}{2\sigma^2}\right] \left[\log_2(\sqrt{2\pi}\sigma) + \frac{(x-\mu)^2}{2\sigma^2} \log_2 e \right] \\ &=& \log_2(\sqrt{2\pi}\sigma) + \frac{\sigma^2}{2\sigma^2} \log_2 e \\ &=& \frac{1}{2} \log_2 (2\pi e\sigma^2) \end{eqnarray*}$$ and so $$H \simeq \frac{1}{2} \log_2 \left[2\pi e n p(1-p)\right].$$ Higher order terms can be found, essentially by deriving a more careful (and less simple) version of de-Moivre-Laplace.

share|improve this answer
    
Thanks!You really helped me. –  user844541 Nov 26 '12 at 7:16
    
@user844541: You are welcome! –  user26872 Nov 26 '12 at 11:56
    
How is the integration done in the second to last step? –  Thomas Ahle Jul 15 at 18:55
    
@ThomasAhle: Here we are asking for the zeroeth and second central moments of the normal distribution. But $E(1) = 1$ and $E((X-\mu)^2) = \sigma^2$. If you are more interested in thinking about tricks for evaluating Gaussian integrals, see here for example. Cheers! –  user26872 Jul 15 at 20:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.