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 trying to solve a quiz that asks the following.

The variable $X$ can be the values $1,2,3,...,n$ with the probabilities $\frac{1}{2^1}, \frac{1}{2^2},\frac{1}{2^3},...,\frac{1}{2^n}$

How can I calculate the entropy of $X$? Don't I have to know all the probability values of X?

share|improve this question
2  
Shouldn't the probabilities add up to $1$? Those probabilities add up to $1-\frac{1}{2^n}$ –  Thomas Andrews Jan 15 '13 at 16:56
    
Without knowing what happens the remaining $1/2^n$, you can only come up with a minimum value. –  Thomas Andrews Jan 15 '13 at 17:00
    
Hi Thomas. So that minimum value would be the $-0.5log_2(0.5)$? –  Favolas Jan 15 '13 at 17:03
    
Perhaps the $n$ term and the $1/2^n$ probability is meant to denote the general term, over all the positive integers, rather than a range? –  leonbloy Jan 15 '13 at 17:38
    
Ah, perhaps that is the case @leonbloy –  Thomas Andrews Jan 15 '13 at 17:40
show 1 more comment

2 Answers

Your probability space is incomplete, so the entroy is not well-defined.

The minimum entropy is achieved if the remaining $\frac{1}{2^n}$ of the time, it takes a single value, which we'll just assume is $X=0$. In that case (using $\log$ base $2$:)

$$\begin{align} H(X) &= - \sum_{k=0}^n P(X=k)\log P(X=k) \\ &=-\frac{1}{2^n}\log \frac{1}{2^n} - \sum_{k=1}^n \frac{1}{2^k}\log \frac{1}{2^k}\\ &=\frac{n}{2^n} + \sum_{k=1}^n \frac{k}{2^k} \end{align}$$

This is the absolute minimum for the entropy. There is no upper bound for the entropy.

Using $$\sum_{k=1}^n kx^k = x\frac {nx^{n+1}-(n+1)x^n +1}{(x-1)^2}$$ with $x=\frac 1 2$, we can compute $\sum_{k=1}^n \frac{k}{2^k}$ which I think yields a minimum entropy of:

$$2-\frac{1}{2^{n-1}}$$

But I don't entirely trust my calculation here.

Perhaps the commenter above is right, and the real intent of the problem is that the probability is over all natural numbers, $1,...,n,...$ with $P(X=n)=\frac{1}{2^n}$. Then the entropy is the limit as $n\to\infty$ of the above lower bound, which is $2$ (assuming my calculation is correct.)

share|improve this answer
add comment

Entropy is simply

$$H = -\sum_{k=1}^{n} p_k \log_2{p_k} = \sum_{k=1}^{n} k \: 2^{-k} = \frac{1/2}{(1 - 1/2)^2} - \frac{n (1/2)^{n+1}}{1-1/2} = 2 \left [ 1 - n 2^{-(n+1)} \right ] $$

share|improve this answer
    
What about the missing $2^{-n}$? –  MJD Jan 15 '13 at 17:24
    
Hi. Assume $n = 2$ and $H(X)=1$, $n = 3$ and $H(X)=1.375$, $n = 4$ and $H(X)=1.625$. So if $n$ keeps incrementing it will be impossible to calculate $H(X)$. Right? –  Favolas Jan 15 '13 at 17:25
    
In this case, $H>2$ and approaches 2 from above as $n \rightarrow \infty$. I do not know what you mean about the missing $2^{-n}$. And $H$ is certainly not impossible to calculate for increasing values of $n$; rather, it is very simple, as you stated it. –  Ron Gordon Jan 15 '13 at 18:38
add comment

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.