Tag Info

Hot answers tagged

14

You can't do that by using binary codewords for single symbols A, B and C. As mentioned in the comments, for example, arithmetic coding can be used to get near the limit when the input sequence is long. Another simple example: You can consider "super-symbols" that consist of 100 As, Bs and Cs and encode one super-symbol at a time, so that each of the ...


8

The optimal length is given by the Huffman code. In this case, that corresponds to your proposed coding, with average code length 1.6667. So, this is optimal... if you restrict to a single symbol=>single codeword coding. But you can do better if, instead of coding each symbol alone, you code the pairs, or triplets, or... That is, if you encode the ...


4

There is in fact an existing mathematical definition of this exact concept called Kolmogorov complexity, but you will surely be disappointed because there is a serious catch: it is only defined up to a constant additive factor which depends on your model of computation. But aside from that factor, it is an invariant metric across a wide range of models, so ...


2

Both cases are possible. H(X) [=========================] H(Y) [===============] (original) H(X,Y) [==================================] H(X) [=========================] constant H(Y) [=======] less than original H(X,Y) [=============================] decreases ...


2

I think the book is simply saying that it is a measure of how correlated the two variables are. If they are totally independent (un-correlated) then $P(A\cap B)=P(A)P(B)$ and the quantity is $1$. If they are mutually exclusive the quantity is $0$. In general, $$\frac{P(A\cap B)}{P(A)P(B)}=\frac{P(A|B)}{P(A)}=\frac{P(B|A)}{P(B)}$$ So it measures what ...


2

In general, the inequation is false. Take for example two sets, the first one with $M\gg 1$ elements and $p(x_i)= \epsilon\ll1/M$, the second with a single value. Then the global entropy $H(X)$ is near zero, while the weighted entropy will be dominated by the entropy of the first set, which is $\log_2 M$ Say: $M=1024$, $\epsilon=10^{-6}$. Then ...


2

If you are asking about the equality $$E_p\left[\log_2 \frac1{p_x}\right] = -\sum_x p_x\log_2 p_x$$ then it is just the definition of expected value and using $\log_2\frac1x=-\log_2x$. (Which, of course, works for logarithms at any base, not just base two.)


2

If those observations are correct, they are the same as saying that average word length ($N_t$) does not vary so much between different texts of type $t$. The 4-digit accuracy 1.618... is meaningless, but it is possible that $t=$ dictionaries is a category with higher average word length than $t=$ novels, which have higher average word length than $t=$ ...


1

In general, entropy does not tell you if your model is good or bad. But, for natural language, where there is a lot of structure and long range dependencies that are very difficult to capture, we know that the entropy of natural language is lower than a model that cannot capture these long range dependencies. That being said, it is also possible to have a ...


1

Shannon Entropy, given a discrete probability distribution with probabilities $p_1,p_2,\dots,p_n$ is $$-\sum_i p_i\log_2(p_i).$$ This is not equal to the quantity you gave. If $n=1$ then we must have $p_1=1$ and then the Shannon Entropy is 0. A relevant example is to figure out what $p_1$ maximizes Shannon entropy when $n=2$. This can be thought of as what ...


1

Independence of $X$ and $Z$ is not enough to guarantee $I(X;Y|Z) = I(X;Y)$. As an example consider $X \oplus Z = Y$, where $X,Z$ are independent Bernoulli($\frac12$) {0,1} random variables and $\oplus$ is modulo 2 addition. $I(X;Y|Z) = H(X|Z) - H(X|YZ) = H(X) - H((Y \oplus Z)|YZ)= 1 - 0 = 1$. On the other hand, $I(X;Y) = H(X) - H(X|Y) = 1 - 1 = 0$. Put ...


1

There are a number of dependence measures which are defined in similar way. For example, given two $\sigma$-fields $F$ and $G$: $\alpha(F,G)=sup_{(A\in F,B\in G)}|P(A\cap B)-P(A)P(B)|$ $\phi(F,G)=sup_{(A\in F,B\in G)}|P(A|B)-P(A)|$ Your dependence measure defined using similar logic: $\delta(A,B)=\frac{P(A\cap B)}{P(A)P(B)}=\frac{P(A|B)}{P(A)}$ If ...


1

Just do the math. Let me change notation, call $a_x = P_0[x] $, $b_x=P_1[x] $ and let $e_x=a_x-b_x$ Then each term of the sum (using natural logarithms) has the form $$ a_x \, \ln \frac{a_x}{b_x}=b_x \, \left(1+\frac{e_x}{b_x}\right) \ln \left(1 +\frac{e_x}{b_x}\right) =b_x \, (1+u_x) \, \ln(1+u_x)$$ where $u_x=e_x/b_x$. Now, for small $u_x$, we use ...



Only top voted, non community-wiki answers of a minimum length are eligible