更改

===Simplification of Markov chains===

===Model Reduction of Markov chains===

The [[simplification of Markov chains]], also referred to as [[coarse-graining of Markov chains]], is closely related to causal emergence. The coarse-graining process in causal emergence is essentially the simplification of Markov chains. Model simplification of Markov processes <ref>Zhang A, Wang M. Spectral state compression of markov processes[J]. IEEE transactions on information theory, 2019, 66(5): 3202-3231.</ref> is an important problem in state transition system modeling. It reduces the complexity of Markov chains by merging multiple states into one state.

The [[Model Reduction of a Markov Chain]], also referred to as [[coarse-graining of Markov chains]], is closely related to causal emergence. The coarse-graining process in causal emergence is essentially a model reduction of a Markov chain. Coarse-graining Markov processes <ref>Zhang A, Wang M. Spectral state compression of markov processes[J]. IEEE transactions on information theory, 2019, 66(5): 3202-3231.</ref> is an important problem for modeling a state transition system. It reduces the complexity of Markov chains by merging multiple states into one state.

There are mainly three meanings of simplification. First, when we study a very large-scale system, it is unnecessary to focus on the changes of each microscopic state. Coarse-graining filters out noise and heterogeneity to derive mesoscale or macroscopic laws from microscopic data. Second, some state transition probabilities are very similar, so they can be regarded as the same kind of state. Clustering this kind of state (also called partitioning the state) to obtain a new smaller Markov chain can reduce the redundancy of system representation. Third, in reinforcement learning using Markov decision processes, coarse-graining the Markov chain can reduce the size of the state space and improve training efficiency. In much of the literature, coarse-graining and dimension reduction are equivalent <ref>Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>.

There are mainly three meanings of coarsening. First, when we study a very large-scale system, it is unnecessary to focus on the changes of each microscopic state. Coarse-graining filters out noise and heterogeneity to derive mesoscale or macroscopic laws from microscopic data. Second, some state transition probabilities are very similar, so they can be regarded as the same kind of state. Clustering(partitioning) this kind of states (also called lumping the states) to obtain a new smaller Markov chain can reduce the redundancy of system representation. Third, in reinforcement learning using Markov decision processes, coarse-graining the Markov chain can reduce the size of the state space and improve training efficiency. In much of the literature, coarse-graining and dimension reduction are equivalent <ref>Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>.

Among them, there are two types of coarse-graining of the state space: hard partitioning and soft partitioning. Soft partitioning involves breaking up microscopic states, reconstructing macroscopic states, and allowing their superposition. Hard partitioning is a strict grouping of microscopic states, dividing several microscopic states into one group without allowing overlap and superposition  (see [[coarse-graining of Markov chains]]).

Among them, there are two types of partitioning(clustering, grouping) of the state space: hard partitioning and soft partitioning. Soft partitioning involves breaking up microscopic states, reconstructing macroscopic states, and allowing their superposition. Hard partitioning is a strict grouping of microscopic states, dividing several microscopic states into one group without allowing overlap and superposition  (see [[coarse-graining of Markov chains]]).

The coarse-graining of Markov chains not only needs to be done on the state space, but also on the transition matrix. This involves simplifying the original transition matrix according to the state grouping to obtain a new, smaller transition matrix. In addition, the state vector needs to be reduced. Therefore, a complete coarse-graining process needs to consider the coarse-graining of state, transition matrix, and state vector at the same time. Thus, This raises the question of how to calculate transition probabilities in the new Markov chain after state grouping. Another question is whether the normalization condition can be guaranteed.

The coarse-graining of Markov chains not only needs to be done on the state space, but also on the transition matrix. This involves simplifying the original transitional probability matrix (TPM) according to the state grouping to obtain a new, smaller TPM. In addition, the state vector needs to be reduced. Therefore, a complete coarse-graining process needs to consider the coarse-graining of states, TPM, and state vector at the same time. Thus, This raises the question of how to calculate TPM in the new Markov chain after states grouping. Another question is whether the normalization condition can be guaranteed.

In addition to these guarantees, the coarse-graining operation of the transition matrix is typically required to be commutative with the matrix itself. This condition ensures that the one-step evolution of the state vector through the coarse-grained matrix (equivalent to macroscopic dynamics) is preserved. It is equivalent to first performing one-step transition matrix evolution on the state vector (equivalent to microscopic dynamics) and then applying coarse-graining. This puts forward requirements for both the state grouping (the coarse-graining process of the state) and the coarse-graining process of the transition matrix. This requirement of commutativity leads people to propose the requirement of [[clustering property of Markov chains]].

In addition to these requirements, the coarse-graining operation of the TPM is typically required to be commutative with the operation of time evolution, i.e., the TPM itself. This condition ensures that the one-step evolution of the state vector through the coarse-grained TPM (equivalent to macroscopic dynamics) is equivalent to the procedure of first performing one-step transition matrix evolution on the state vector (equivalent to microscopic dynamics) and then applying coarse-graining. This puts forward the requirement of the consistency for both the state grouping (the coarse-graining process of the state) and the coarse-graining process of the TPM. This requirement of commutativity leads people to propose the requirement of [[lumpability of Markov chains]].

For any hard partition of states, we can define the concept of lumpability. Lumpability is a measure of clustering. This concept first appeared in Kemeny, Snell's Finite Markov Chains in 1969 <ref name=":33">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>. Lumpability is a mathematical condition to determine whether a hard-blocked microscopic state grouping scheme is reducible to the microscopic state transition matrix. No matter which hard-blocking scheme the state space is classified according to, it has a corresponding coarse-graining scheme for the transition matrix and probability space <ref>Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>.

For any hard partition of states, we can define the concept of lumpability. Lumpability is a requirement of clustering. This concept first appeared in Kemeny, Snell's Finite Markov Chains in 1969 <ref name=":33">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>. Lumpability is a mathematical condition to determine whether a hard-blocked microscopic state grouping scheme is reducible to the macroscopic TPM. No matter which hard-blocking scheme the state space is partitioned according to, it has a corresponding coarse-graining scheme for the TPM and distributions <ref>Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>.

Suppose a grouping method '''<math>A=\{A_1, A_2,...,A_r\}</math>''' is given for the Markov state space '''<math>A</math>'''. Here [math]A_i[/math] is any subset of the state space '''<math>A</math>''' and satisfies [math]A_i\cap A_j= \Phi[/math], where [math]\Phi[/math] represents the empty set. [math]\displaystyle{ s^{(t)} }[/math] represents the microscopic state of the system at time [math]\displaystyle{ t }[/math]. The microscopic state space is [math]\displaystyle{ S=\{s_1, s_2,...,s_n\} }[/math] and the microscopic state '''<math>s_i\in A</math>''' are all independent elements in the Markov state space. Let the transition probability from microscopic state <math>s_k</math> to <math>s_m</math> be <math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>, and the transition probability from microscopic state <math>s_k</math> to macroscopic state <math>A_i</math> be <math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k)</math>. Then the necessary and sufficient condition for lumpability is that for any pair <math>A_i, A_j</math>, <math>p_{s_k \rightarrow A_j}</math> of every state <math>s_k</math> belonging to <math>A_i</math> is equal, that is:

Suppose a grouping method '''<math>S=A_1\cup A_2\cup ... ,A_r\}</math>''' is given for the state space '''<math>A</math>'''. Here [math]A_i[/math] is any subset of the state space '''<math>S</math>''' and satisfies [math]A_i\cap A_j= \Phi[/math], where [math]\Phi[/math] represents the empty set. [math]\displaystyle{ s^{(t)} }[/math] represents the microscopic state of the system at time [math]\displaystyle{ t }[/math]. The microscopic state space is [math]\displaystyle{ S=\{s_1, s_2,...,s_n\} }[/math] and the microscopic state '''<math>s_i\in S</math>''' are all independent elements in the Markov state space. Let the transition probability from microscopic state <math>s_k</math> to <math>s_m</math> be <math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>, and the transition probability from microscopic state <math>s_k</math> to macroscopic state <math>A_i</math> be <math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k)</math>. Then the necessary and sufficient condition for lumpability is that for any pair <math>A_i, A_j</math>, <math>p_{s_k \rightarrow A_j}</math> of every state <math>s_k</math> belonging to <math>A_i</math> is equal, that is:

For specific methods of coarse-graining Markov chains, please refer to [[coarse-graining of Markov chains]].

For specific methods of coarse-graining Markov chains, please refer to [[coarse-graining of Markov chains]].

==References==

==References==