An alternative construction of Shannon entropy (opens in new tab)

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

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

Interestingly this has a rather frequentist flavor. The probabilities end up coming from frequency ratios in very large samples.

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.

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)

The story I came up with for the first term, is that in the sequence of lenght L, you need to choose L1 locations that will get the symbol x1, so there are choose(L,L1) ways to do that. Next you have L-L1 remaining spots to fill, and L2 of those need to have the symbol x2, hence the choose(L-L1,L2) term, etc.

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

Eh ok, but the trick is then taking the limit for L->infty and use Stirling’s approx which is what Shannon did