Calculate entropy with n values

Question

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
@leonboy hummm. You're right. At the end of the quiz as the following note: $\sum_{n=1}^\infty ar^{-n}$. But I still don't understand — Favolas, Jan 15 '13 at 18:42

Ron Gordon · Answer 1 · 2013-01-16T00:52:01.240

1

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

edited Jan 16 '13 at 00:52

answered Jan 15 '13 at 17:07

Ron Gordon

138,521

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

Thomas Andrews · Answer 2 · 2013-01-15T17:44:53.030

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

Calculate entropy with n values

2 Answers2