# Calculate entropy with n values

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?

-
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

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

-

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

-
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