1
$\begingroup$

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$....

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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)\;.$$

$\endgroup$
2
  • $\begingroup$ Thanks! Upvoted you. It's nice to see a combinatorial working out of the entropy here explicitly. $\endgroup$
    – Amir
    Nov 28, 2013 at 18:56
  • $\begingroup$ @Amir: You’re welcome. $\endgroup$ Nov 28, 2013 at 18:58
1
$\begingroup$

The probability that we select a specific string with $k$ one bits is $$p^k(1-p)^{d-k}$$ Thus $$\Bbb{E}[-\log_2 P] = -\sum_{i\in\{0,1\}^d}P(i)\log_2P(i) \\= -\sum_{k=0}^{d}\binom{d}{k}p^k(1-p)^{d-k}\log_2(p^k(1-p)^{d-k})\\ =-\sum_{k=0}^d\binom{d}{k}p^k(1-p)^{d-k}[k\log_2(p)+(d-k)\log_2(1-p)]\\ = -\log(p) \Bbb{E}[H] - \log(1-p)\Bbb{E}[T]$$

Where $H\sim \operatorname{Binom}(d,p)$ and $T\sim\operatorname{Binom}(d,1-p)$. These respectively have means $dp$ and $d(1-p)$. The resulting entropy is therefore $$-d(p\log_2(p)+(1-p)\log_2(1-p))$$

$\endgroup$
4
  • $\begingroup$ Just to slightly recast your answer. Can you make an argument that each bit has entropy $-(p \log p + (1-p) \log (1-p))$ ? And then since entropy is additive, over the $d$ bits of the string the entropy is $-dp(\log p + (1-p) \log (1-p)$? I know this is essentially what you said, but I was wondering if one could omit any terms of the form $d \choose k$ altogether from a proof. $\endgroup$
    – Amir
    Nov 28, 2013 at 18:41
  • 1
    $\begingroup$ Are you familiar with en.wikipedia.org/wiki/Binary_entropy_function, the entropy of a Bernoulli trial? That's actually exactly what you said. I'm not sure how the additivity argument would work though. $\endgroup$ Nov 28, 2013 at 18:45
  • $\begingroup$ I think addivity is a basic property of entropy right? If two events $X$ and $Y$ are independent, then $H(X,Y) = H(X) + H(Y)$. (I'm citing wikipedia here though en.wikipedia.org/wiki/Entropy_%28information_theory%29). Since each bit here is set to be $0$ or $1$ independently in this scenario, we can consider them as independent. And yes, I'm essentially thinking of this as $d$ independent Bernoulli trials now. $\endgroup$
    – Amir
    Nov 28, 2013 at 18:53
  • $\begingroup$ Then yes, I feel that that works. And it explains where the $\Bbb{E}[H]$ and $\Bbb{E}[T]$ come from, the expected number of ones and zeroes. $\endgroup$ Nov 28, 2013 at 18:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .