New answers tagged

3

Given a probability distribution $p$ with $n$ distinct outcomes $x_i$, the quantity $$\frac{H}{H_\text{max}} = \frac{-\sum_{i=1}^n p(x_i) \log(p(x_i))}{-\sum_{i=1}^n \frac{1}{n} \log(\frac{1}{n})} = -\sum_{i=1}^n \frac{p(x_i) \log(p(x_i))}{\log(n)}$$ is sometimes called as the efficiency, or the normalized entropy. Wikipedia has a short paragraph on this, ...


2

First of all, I would use log base 2 instead of natural log because it's easier to talk about its meaning as the number of yes/no questions on average to guess the value. Given 20 choices, the maximum entropy distribution has entropy of 4.322 bits. While your distribution has 3.607 bits, which is 83% of the maximum possible value. Of course you can ...


1

$T = n_1 + \ldots + n_A$, so $$\eqalign{-n_1 \log_2 n_1 &- \ldots - n_A \log_2 n_A + T \log_2 T = -n_1 (\log_2 n_1 - \log_2 T) - \ldots - n_A (\log_2 n_A - \log_2 T)\cr &= -n_1 \log_2(n_1/T) - \ldots - n_A \log_2(n_A/T)} $$ This, together with $-n_1 - \ldots - n_A + T = 0$, gives the notes' result. Your answer would be $-n_1 \log_2 n_1 - \ldots - ...


2

I don't think that intution can help much here. It's true that the number of sortings fits in 29 bits ($12 ! < 2^{29}$), so it's in principle possible to identify a permutation by making at most 29 yes-no questions. But a comparison algorithm imposes a huge restriction: instead of chossing among all the arbitrary yes-no questions ($2^{11}=2048$ questions)...


0

Actually $H(X|Y=Y)$ is a random variable, and $H(X|Y=y)$ is a number, namely, the entropy of the conditional distribution $p_{X|Y=y}$. In older textbooks you see the more accurate notation $$ EH(X|Y) = \sum_y p_Y(y)H(X|Y=y)$$ which means that the conditional entropy is an expectation over the random variable $H(X|Y=Y)$. In newer textbooks this is now ...


0

From what I could find it seems the answer lies in that the "exact" definition is to replace the function with it's positive limit. So instead of using $P_i*log_2(\frac{1}{P_i})$ we use the positive limit $\lim_{x->P_i}(x*log_2(\frac{1}{x}))$ which can then be solved with l'hopital.


1

For the first question: Entropy can be viewed as the expected value of the random variable that is the logarithm of the probabilities (alphabet size $M$): $$H_b = -\sum_{i=0}^{M}\log_b(p_i)p_i = -E[\log_b(p_i)]$$ For logarithm with base 2, this is the average number of bits required per symbol $(H_2)$. For some other number system, change the base of ...



Top 50 recent answers are included