Editing Entropy (information theory) (section)

===Approximation to binomial coefficient===
For integers {{math|0 < ''k'' < ''n''}} let {{math|1=''q'' = ''k''/''n''}}. Then
<math display="block">\frac{2^{n\Eta(q)}}{n+1} \leq \tbinom nk \leq 2^{n\Eta(q)},</math>
where <ref>Aoki, New Approaches to Macroeconomic Modeling.</ref>{{rp|p=43}}
<math display="block">\Eta(q) = -q \log_2(q) - (1-q) \log_2(1-q).</math>

{| class="toccolours collapsible collapsed" width="80%" style="text-align:left; margin-1.5em;"
!Proof (sketch)
|-
|Note that <math>\tbinom nk q^{qn}(1-q)^{n-nq}</math> is one term of the expression
<math display="block">\sum_{i=0}^n \tbinom ni q^i(1-q)^{n-i} = (q + (1-q))^n = 1.</math> 
Rearranging gives the upper bound. For the lower bound one first shows, using some algebra, that it is the largest term in the summation. But then,
<math display="block">\binom nk q^{qn}(1-q)^{n-nq} \geq \frac{1}{n+1}</math>
since there are {{math|''n'' + 1}} terms in the summation. Rearranging gives the lower bound.
|}

A nice interpretation of this is that the number of binary strings of length {{math|''n''}} with exactly {{math|''k''}} many 1's is approximately <math>2^{n\Eta(k/n)}</math>.<ref>Probability and Computing, M. Mitzenmacher and E. Upfal, Cambridge University Press</ref>