Rendered at 14:51:33 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
abetusk 19 hours ago [-]
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 states are now dependent on each other.
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?
The article alludes to how entropy evolves. In the context of ergodic Markov chains, this is related to the size of the second eigenvalue?
ssivark 19 hours ago [-]
Here's a thought: once could derive the spectrum of the Markov transition matrix, and assign an entropy to each of the eigenvectors. The dominant eigenvector (highest entropy) would be the ergodic / stationary distribution, but it seems likely that each successive eigenvector would have a little less entropy. One could initialize the system in a "localized" state (very low entropy) and study the thermalization process as each of the low-entropy eigen-components decay away (exponentially, with rates proportional to the corresponding eigenvalue of the transition matrix) finally leaving the system in the high-entropy stationary distribution. The balance between the eigenvalues (exponential rates) and the entropies of respective eigenvectors would characterize the rate of entropy production (at different times) in the Markov chain!
abetusk 19 hours ago [-]
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.
That is the entropy rate. If I'm understanding your original question correctly, you were asking about the standard equilibrium-defining thermodynamic entropy?
abetusk 18 hours ago [-]
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?)?
chermi 16 hours ago [-]
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.
bandrami 8 hours ago [-]
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.
chermi 18 hours ago [-]
Find the equilibrium probabilities from first eigenvector, use definition of entropy like you did. If it's not ergodic then you get subsystems with their own entropies. Second eigenvalue iirc basically characterizes dominant relaxation time.
This is all if you mean the equilibrium entropy of the underlying system, not the entropy rate.
24 hours ago [-]
AIorNot 9 hours ago [-]
It's funny the author does not go into Karl Friston's Markov Blanket concept in regards to Life
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
23 hours ago [-]
niklasbuschmann 23 hours ago [-]
Stochastic thermodynamics covers this
chermi 22 hours ago [-]
This predates stochastic thermo quite a bit. Entropy of markov chain is at least 50 y/o, maybe more.
emsign 5 hours ago [-]
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.
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 states are now dependent on each other.
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?
The article alludes to how entropy evolves. In the context of ergodic Markov chains, this is related to the size of the second eigenvalue?
[0] https://math.stackexchange.com/questions/1040972/entropy-of-...
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?)?
This is all if you mean the equilibrium entropy of the underlying system, not the entropy rate.
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
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.