Entropy of a distribution over strings Suppose for some parameter $d$, we choose a string from the Hamming cube ($\{0,1\}^d$) by setting each bit to be $0$ with probability $p$ and $1$ with probability $1-p$. What is the entropy of this distribution on the Hamming cube? Clearly, if $p=\frac{1}{2}$, then the entropy would just be $\log \left(\frac{1}{2^d} \right) = d$. If $p = 0$, then the entropy would be $0$. What would be the entropy for the general case in terms of $p$? It would clearly be less than $d$....

In the Hamming $d$-cube there are $\binom{d}k$ points with $k$ zeroes and $d-k$ ones, so the entropy is
$$-\sum_{k=0}^d\binom{d}kp^k(1-p)^k\lg\left(p^k(1-p)^{d-k}\right)\;,$$
or
$$-\sum_{k=0}^d\binom{d}kp^k(1-p)^{d-k}\Big(k\lg p+(d-k)\lg(1-p)\Big)\;.$$
Now
$$\begin{align*}
\sum_{k=0}^d\binom{d}kkp^k(1-p)^{d-k}&=d\sum_{k=0}^d\binom{d-1}{k-1}p^k(1-p)^{d-k}\\\\
&=dp\sum_{k=0}^{d-1}\binom{d-1}kp^k(1-p)^{d-k-1}\\\\
&=dp\;,
\end{align*}$$
and
$$\sum_{k=0}^d\binom{d}kdp^k(1-p)^{d-k}=d\;,$$
so
$$-\sum_{k=0}^d\binom{d}kp^k(1-p)^k\lg\left(p^k(1-p)^{d-k}\right)=-d\Big(p\lg p+(1-p)\lg(1-p)\Big)\;.$$
