An alternative construction of Shannon entropy
rkp.scienceCalling this 'alternative' construction seems like coming full circle since this line of combinatorial argument is how Boltzmann came up with his H-function in the first place, which inspired Shannon's entropy.
Yep! This relationship is well known in statistical mechanics. I was just surprised that in many years of intersecting with information theory in other fields (computational neuroscience in particular) I'd never come across it before, even though IMO it provides an insightful perspective.
Seems similar to https://en.wikipedia.org/wiki/Principle_of_maximum_entropy#T...
This is what I learned as the “theory of types” from Cover and Thomas, chapter 11, from original work by Imre Csiszar. See just under “theorem 6” in
https://web.stanford.edu/class/ee376a/files/2017-18/lecture_...
The key (which is not in OP) is not the construction of E log(p), but in being able to prove that the “typical set” exists (with arbitrarily high probability), and that the entropy is its size.
The site is unreadable on mobile because it disables overflow on the equations (which it shows as images, even though it’s 2024 and all modern browsers support MathML).
Today I learned! I'd missed the news that MathML was back in Chrome. I've been publishing web pages using MathML for years, along with a note that the equations don't render in Chrome. I can finally remove the note.
Nice!
The key step of the derivation is counting the "number of ways" to get the histogram with bar heights L1, L2, ... Ln for a total of L observations.
I had to think a bit why the provided formula is true:
choose(L,L1) * choose(L-L1,L2) * ... * choose(Ln,Ln)
In Physics, the log part comes in when you use the Stirling approximation for large N.
Ideal gas: https://bytepawn.com/entropy-of-an-ideal-gas-with-coarse-gra...
Physical gas: https://bytepawn.com/the-physical-sackur-tetrode-entropy-of-...
Interestingly this has a rather frequentist flavor. The probabilities end up coming from frequency ratios in very large samples.
That line of inferential philosophy is very Jaynesian, for those who are interested.
Eh ok, but the trick is then taking the limit for L->infty and use Stirling’s approx which is what Shannon did