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.

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: bit.ly/nbQwgV

It is correct? Any hint?

Greatly apreciated. Cheers.

share|improve this question
1  
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
3  
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

1 Answer 1

up vote 10 down vote accepted

You need to know the value of the series $t(x)=\displaystyle\sum_{i\ge0}ix^i$. You probably already know the value of the series $s(x)=\displaystyle\sum_{i\ge0}x^i$ since $s(x)$ is the classical geometric series: $s(x)=1/(1-x)$.

But $t(x)=xs'(x)$ hence $t(x)=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(\frac12)=\frac12/(1-\frac12)^2=2$, as desired.

share|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

 
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.