Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Entropy of a Markov Chain

chillphysicsenjoyer.substack.com

Post reply on HN
Print view View original

11–19 of 19 posts

Re: The Entropy of a Markov Chain

#11

Post by chermi »

abetusk wrote: post #8
abetusk wrote: post #6

So how does one calculate the entropy of a Markov Chain? Is it actually specified? If so, it seems buried. The Markov chain provided as an example has the edge labels swapped (np should be qp and qp should be np). Regardless, what is the entropy of the example provided? The problem with Markov chains is that states are dependent, so simply cataloguing states now violates the basic entropy calculation as neighboring s…

OK, no, I'm wrong. The entropy of a Markov chain with stationary distribution v is [0]: -\sum v_i p_{i,j} \log(p_{i,j}) That is, the "entropy" of the transition matrix modified by the stationary distribution. [0] https://math.stackexchange.com/questions/1040972/entropy-of-...

That is the entropy rate. If I'm understanding your original question correctly, you were asking about the standard equilibrium-defining thermodynamic entropy?

Re: The Entropy of a Markov Chain

#12

Post by abetusk »

chermi wrote: post #11
abetusk wrote: post #8

Earlier quoted context omitted.

OK, no, I'm wrong. The entropy of a Markov chain with stationary distribution v is [0]: -\sum v_i p_{i,j} \log(p_{i,j}) That is, the "entropy" of the transition matrix modified by the stationary distribution. [0] https://math.stackexchange.com/questions/1040972/entropy-of-...

That is the entropy rate. If I'm understanding your original question correctly, you were asking about the standard equilibrium-defining thermodynamic entropy?

I'm not sure I had a well formed question. I saw the post title, didn't get a clarification in the article and started searching.

The entropy rate seems like a pretty natural definition of "entropy of a Markov chain", no? It's not exactly this but it's similar to "start at state i, end on state j (maybe in n steps?), what is the number of bits I need to send over the wire to tell you what path was taken".

What does the entropy of the raw stationary distribution give you? Is the entropy rate related to the entropy of the stationary distribution (the thermodynamic entropy?)?

Re: The Entropy of a Markov Chain

#13

Post by chermi »

abetusk wrote: post #12
chermi wrote: post #11

Earlier quoted context omitted.

That is the entropy rate. If I'm understanding your original question correctly, you were asking about the standard equilibrium-defining thermodynamic entropy?

I'm not sure I had a well formed question. I saw the post title, didn't get a clarification in the article and started searching. The entropy rate seems like a pretty natural definition of "entropy of a Markov chain", no? It's not exactly this but it's similar to "start at state i, end on state j (maybe in n steps?), what is the number of bits I need to send over the wire to tell you what path was taken". What does t…

I was probably projecting. I like both path and equilibrium entropies, but my assumption I guess was that when people hear entropy in physics they're usually thinking of the equilibrium-defining entropy. That is, the value that is maximized as the system relaxes to equilibrium, the vanilla thermodynamic entropy.

Re: The Entropy of a Markov Chain

#14

Post by AIorNot »

It's funny the author does not go into Karl Friston's Markov Blanket concept in regards to Life

https://www.fil.ion.ucl.ac.uk/~karl/Life%20as%20we%20know%20...

His paper here presents a heuristic proof (and simulations of a primordial soup) suggesting that life—or biological self-organization—is an inevitable and emergent property of any (ergodic) random dynamical system that possesses a Markov blanket

Re: The Entropy of a Markov Chain

#15

Post by bandrami »

abetusk wrote: post #6

So how does one calculate the entropy of a Markov Chain? Is it actually specified? If so, it seems buried. The Markov chain provided as an example has the edge labels swapped (np should be qp and qp should be np). Regardless, what is the entropy of the example provided? The problem with Markov chains is that states are dependent, so simply cataloguing states now violates the basic entropy calculation as neighboring s…

Anything with a probability mass or distribution function has entropy; the state space of Markov chains just tends to get combinatorially big as the chain's memory increases.

Re: The Entropy of a Markov Chain

#16

Post by emsign »

I love this stuff. Like the one definition of death being an organism dying is one that starts failing to maintain itself. Maintenance being the essence of being alive. Or in other words creating local order by sourcing energy from the environment and thus increasing entropy outside the organism.

The laws of thermodynamics are so universal and primordial, they even preceed all of fundamental physics. And once you "get them" which is more like accepting them to be universally true, you can use them to evaluate and explain a lot of things. They help you decern reality from magic for instance, or magical thinking. Ideas that would only work if the second law of thermodynamics makes an exception is magic and therefore impossible in this universe.

Re: The Entropy of a Markov Chain

#17

Post by sm-silversight »

emsign wrote: post #16

I love this stuff. Like the one definition of death being an organism dying is one that starts failing to maintain itself. Maintenance being the essence of being alive. Or in other words creating local order by sourcing energy from the environment and thus increasing entropy outside the organism. The laws of thermodynamics are so universal and primordial, they even preceed all of fundamental physics. And once you "ge…

>And once you "get them" which is more like accepting them to be universally true, you can use them to evaluate and explain a lot of things

Can you give an example? This seems like the same confirmation bias I see psychology students make.

Re: The Entropy of a Markov Chain

#18

Post by elevation »

sm-silversight wrote: post #17
emsign wrote: post #16

I love this stuff. Like the one definition of death being an organism dying is one that starts failing to maintain itself. Maintenance being the essence of being alive. Or in other words creating local order by sourcing energy from the environment and thus increasing entropy outside the organism. The laws of thermodynamics are so universal and primordial, they even preceed all of fundamental physics. And once you "ge…

>And once you "get them" which is more like accepting them to be universally true, you can use them to evaluate and explain a lot of things Can you give an example? This seems like the same confirmation bias I see psychology students make.

The world is full of plausible-sounding but provably incorrect explanations if you understand the laws of physics.

As a university student I happened upon a liberal arts undergrad who explained to me in earnest that electric vehicles could be powered for free if only we would mount wind generators on top of them. Once on the highway, they would have free energy! To this student, evil corporations were the main force opposing the proliferation of this technology.

This is a silly example, but without some underlying principles, otherwise intelligent people will happily accept all kinds of other disprovable delusions.

Re: The Entropy of a Markov Chain

#19

Post by kgwgk »

abetusk wrote: post #6

So how does one calculate the entropy of a Markov Chain? Is it actually specified? If so, it seems buried. The Markov chain provided as an example has the edge labels swapped (np should be qp and qp should be np). Regardless, what is the entropy of the example provided? The problem with Markov chains is that states are dependent, so simply cataloguing states now violates the basic entropy calculation as neighboring s…

> If the Markov chain is ergodic then maybe you can talk about the entropy of the stationary distribution? Then it's just $-\sum p_i lg(p_i)$ of the stationary distribution probabilities?

That's essentially what he's doing there. He makes the calculation for N=8 but for very large N the result converges to N times that entropy.

Post reply on HN