8
$\begingroup$

I have tried very very hard to get a good intuitive grasp on entropy. I read all the information theoretic intuitions on the web, but I have not exactly been able to understand what information is, what does it mean to gain information. I would love a combination of intuitive and formal(!) explanation of this information aspect (so your explanation must explain why $log(1/p)$ is the correct value, since it is not always an integer so it's not exactly about representing with bits, although I'm also willing to accept an asymptotic result, similiar to Shannons theorem).

In my effort I have also read the proof of Shannons theorem on decoding in order to try and get intuition from there (https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem). I think I might have got some, so I'd like to verify it (this gives me intuition as to why Entropy is an important function, and how it is relevant to compressing, but I don't know how to perfectly transfer this to information intuitively, espcially since Shannons theorem talks about high probability). So to verify I understand correctly, it seems to me that entropy (given the setting in the article, we have a sequence of IID variables) is a sort of an approximation to what we would really love to understand, which is the distribution of $P(X_1=x_1,X_2=x_2,..X_n=x_n)$, however this is very complicated (just calculating the expected value is difficult). So intead, we consider the log of this, where we can now use the strong\weak law of large numbers and understand the distribution very well, and then we can go back to what interested us with a good approximation.

So my question is consisted of 3 parts:

$1$ What is this information thing more formally?

$2$ Is my understanding of the intuition in compressing as I wrote above correct?

$3$ Is there a way to transfer this intuition (in the case that it is correct) to an information theoretic one, because assuming I'm correct about the above, I feel comfortable with this, so I would understand the information theoretic point of view well?

My objective is that as many of the formulas involving entorpy will be trivial from our intuition. I will update here whenever I understand another one. Since everytihng happens with higih probability about encoding, with union bound everything will be good, I'm just going to assume it is always satisfied to make the writing smoother.

For example, we easily get (using my intuition of compressing) that $H((X,Y))<=H(X)+H(Y),$ since in both cases with high probability we can encode well, therefore by union bound with high probabiliy we can encode well for both of them, and we can just concatenate the encodings.

Let's see why there must be equality if they are independent. If we look at the proof of Shannons theorem, we saw there that $P(x_1,x_2..x_n)$ is about $2^{(-nH(x))}$, and the same for $Y$. So clearly we have $P(x_1,y_1,x_2,y_2,..)$ is about $2^{(-nH(x))}2^{(-nH(y))}=2^{(-n(H(x)+H(y))}$ which is what we wanted.

Now let's do conditional entropy. So given $Y$, we want $H(X|Y)=H((X,Y))-H(Y)$. I haven't yet figured this one out

Thanks in advance.

$\endgroup$
  • $\begingroup$ Have you seen this previous question? math.stackexchange.com/q/331103/856 $\endgroup$ – Rahul Jun 27 '17 at 8:03
  • $\begingroup$ ֲ@Rahul I have, the accepted answer is like other things I read on the web, claiming information and uncertainty, but they don't define what it is. $\endgroup$ – Andy Jun 27 '17 at 9:47
2
$\begingroup$

I would STRONGLY reccomend you the section "Introduction to finite-dimensional entropy" from this book:

https://books.google.com.br/books/about/Entropy_Optimization_and_Mathematical_Pr.html?id=emTBu1KOmc4C&source=kp_cover&redir_esc=y

There is an axiomatic and intuitive construction of entropy. It is beautiful!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.