## 5 Mathematical Models
### Models at the Meso Scale
#### 5.2.1 Monte Carlo-Based Methods
_A-periodic_ if, for all states \(i\) and \(j\), the Greatest Common Divisor of the set \(\left\{K:\big{(}\mathbf{P}^{K}\big{)}_{i,j}>0\right\}\) is equal to \(1\). An irreducible, a-periodic Markov Chain must have a unique distribution \(\pi\) on the state space \(S\) with the property that  
\[\pi=\pi\mathbf{P}. \tag{67}\]  
where \(\pi=(\pi_{1},\pi_{2},\ldots,\pi_{N})\) and where \(\pi_{i}\) is the probability of state \(i\). If Equation (67) is valid, the Markov Chain is said to be _\"stable on the distribution\"_\(\pi\), or that \(\pi\) is the stable distribution for the Markov Chain. The following two considerations are valid:  
* If \(\pi\) is the stable distribution for an irreducible, a-periodic Markov Chain, then the Markov Chain can be used to sample from \(\pi\). * Samples from \(\pi\) can be used to approximate the properties of \(\pi\). For example, suppose \(f\) is any real-valued function on the state space \(S\), and suppose that \(s_{1},s_{2},\ldots,s_{M}\) is a sample from \(\pi\); then, the ergodic theorem [114] ensures that \[\lim_{M\to\infty}\frac{1}{M}\sum_{i=1}^{M}f(s_{i})=E_{\pi}[f],\] (68) where \(E_{\pi}[f]\) is the expected value \(E_{\pi}[f]=\sum_{i=1}^{N}f(i)\pi_{i}\). So, if an irreducible, a-periodic Markov Chain can be built that is stable on \(\pi\), that chain can be used to generate states from \(S\) that can be exploited to approximate, by Equation (68), the expected value \(E_{\pi}[f]\) of any real-valued function on the state space \(S\). The original Metropolis algorithm builds a Markov Chain that is stable on a particular type of distribution \(\pi^{Boltzmann}\) that is the _\"Boltzmann distribution\"_. Indeed, in the context of statistical mechanics, which is the branch of physics concerned with the average behavior of large systems of interacting particles, the Metropolis algorithm was introduced to study the properties of \(\pi^{Boltzmann}\). In statistical mechanics, the state of the particles is described by a configuration \(\omega\) taken from the configuration space \(\Omega\). The physics of a configuration space is described by an energy function \(E:\omega\in\Omega\gets E(\omega)\in\Re^{+}\). Then, the value \(E(\omega)\) is said to be the energy of the configuration \(\omega\). The random organization of molecules in a limited space is governed by the fundamental principle of statistical physics assuming that Nature seeks low-energy configurations. For any \(\omega\in\Omega\), its Boltzmann probability, \(\pi^{Boltzmann}(\omega)\), is  
\[\pi^{Boltzmann}(\omega)=\frac{BoltzmannWeight(\omega)}{Z}, \tag{69}\]  
where \(T\) is the temperature and \(k\) is the Boltzmann's constant,  
\[BoltzmannWeight(\omega)=e^{-\frac{E(\omega)}{kT}} \tag{70}\]  
and where \(Z\) is known as _\"Partition Function\"_, defined as  
\[Z=\sum_{\omega^{\prime}}e^{-\frac{E(\omega^{\prime})}{kT}}. \tag{71}\]The relationship between energy and probability leads to expressions for many interesting physical quantities. For example, the total energy of the system, \(\langle E\rangle\), is the expected value of the energy function \(E(\omega)\) and is defined by  
\[\langle E\rangle=\sum_{\omega\in\Omega}E(\omega)\pi^{Boltzmann}(\omega). \tag{72}\]  
The brilliant idea behind the Metropolis algorithm is that it creates an easily computed Markov Chain that is stable on the Boltzmann distribution. The making of such a chain requires only the evaluation of the ratio between the values of Boltzmann probabilities of two consecutive states (i.e., see algorithm described in Section 6.2.1 where \(g(\cdot)=\pi^{Boltzmann}(\cdot)\)) that is  
\[\frac{\pi^{Boltzmann}(\omega)}{\pi^{Boltzmann}(\omega^{*})}=\frac{ BoltzmannWeight(\omega)}{BoltzmannWeight(\omega^{*})}=e^{-\frac{E(\omega)-E(\omega^{*})}{kT}}\]  
and not the full probabilities \(Z\), avoiding the evaluation of the partition function which is analytically and computationally intractable in any realistic setting.