Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm studing for an information theory exam, maybe some of you can help me here with an exercise.

What's the entropy of $X$ as $\{1,2,\ldots,n\}$ ($n$=infinity) where the probabilities are $P \{1/2^1, 1/2^2,\ldots, 1/2^n\}$?

The question is multiple choice and gives 4 possible answers: 1. $2 \over 3$ bits/symbol; 2. $1 \over 2$ bits/symbol; 3. $\infty$ bits/symbol; 4. none of the above;

So far i got: $$ H(X) = - \sum_{i=1}^{n} P(x_i) \cdot\log_2( P(x_i)) $$

So in this case, $$ H(X) = - \sum_{i=1}^{\infty} {1 \over 2^i} \cdot\log_2\left({1 \over 2^i}\right) $$

$\log_2(1/x) = -\log_2(x)$, while $x>0$, so,

$$ H(X) = - \sum_{i=1}^{\infty} {1 \over 2^i}\cdot(-i) $$

I also know that:

$$ \sum_{i=1}^{\infty} a \cdot r^{-i} = {a \over r-1} $$

But in this case I think 'a' must be a constant, right?

Wolfram Alpha gives me H(X) = 2 bits/symbol as the result:

It is correct? Any hint?

Greatly apreciated. Cheers.

share|cite|improve this question
In the last series $i$ starts at $0$. It should be $\displaystyle\sum_{i=0}^{\infty}a\cdot r^i=\dfrac{a}{1-r}$. – Américo Tavares Jul 10 '11 at 17:35
The first two options can be eliminated by adding up a few terms. To eliminate infinity, one needs some intuition, that the $1/2^i$ go down very fast, enough to neutralize the $i$ on top. So knowing a closed form for $\sum \frac{i}{2^i}$ is not necessary to decide on the answer. But the closed form is nice. – André Nicolas Jul 10 '11 at 23:49
up vote 10 down vote accepted

Here is a correct version of the question:

What is the entropy of $X$ such that $P(X=i)=1/2^i$ for every positive integer $i$?

You need to know the value of the series $t(x)=\sum\limits_{i\geqslant0}ix^i$. You probably already know the value of the series $s(x)=\sum\limits_{i\geqslant0}x^i$ since $s(x)$ is the classical geometric series: $s(x)=\frac1{1-x}$.

But $t(x)=xs'(x)$ hence $t(x)=\frac{x}{(1-x)^2}$.

In your case, you start at $i=1$ instead of $i=0$ but this does not change anything since the $0$th term of $t(x)$ is $0$, and you choose $x=\frac12$. Hence $t\left(\frac12\right)=\frac{\frac12}{(1-\frac12)^2}=2$, as desired.

share|cite|improve this answer
Cool, thanks. Got it. So in the end the answer to the question is 4. none of the above; – pedrosanta Jul 10 '11 at 17:27
pedrosanta: No, it is not. And your own accepted answer is wrong. – Did Feb 25 '12 at 20:50
Ok. I removed it. I'll look into this with greater detail later to figure/close this. :) (Anyway, thanks all for your help. It was greatly appreciated. I passed at the class btw.) – pedrosanta Feb 27 '12 at 14:26

Your Answer


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.