Monte-Carlo Method

Monte-Carlo Methods

Monte Carlo methods are commonly used by researchers in several areas, but always in view of obtaining results that would, otherwise, be impossible, or, at least, extremely difficult to obtain. A approach we suggest will focus mainly on the use of this methodology to simulate the aforementioned processes that are a part of MBE systems.

MC methods are inherently slow to converge, with convergence times of the order of $1/\sqrt{N}$ . As such, we must take care in order to make the convergence as fast as possible and thus avoid that our algorithm becomes unwieldly slow. These difficulties also impose that this type of methods be used only when no other methods are available¹.

Stochastic models in which the transitions from one given configuration to some other configuration occur spontaneously at a rate of $W_{s\to s'}\ge 0$ , have a probability distribution $P_{t}(s)$ that evolves deterministacly in time according to a partial differential equation (the so called Master Equation) that describes the flux of probabilities to originate and destroy a given system configuration .

$\displaystyle \frac{\partial}{\partial t}P_{t}(s)=\underbrace{\sum_{s'}W_{s'\to... ...{\hbox{creation}}-\underbrace{\sum_{s}W_{s\to s'}P_{t}(s)}_{\hbox{destruction}}$

(1)

The creation and destruction terms balance each other in such a way that the condition $\sum_{s}P_{t}(s)=1$ is always true. Since the time variation of $P_{t}(s)$ is completely determined by the probability distribution at a given time , the master equation desribes a Markov process that by its very nature has no intrinsic memory of previous states.

At equilibrium, $\frac{\partial}{\partial t}P_{t}(s)=0$ and the system obeys the detailed balance condition:

$\displaystyle \sum_{s'}W_{s'\to s}P_{t}(s')=\sum_{s}W_{s\to s'}P_{t}(s)$

(2)

Simple sampling

MC techniques are used to simulate physical system with a number of degrees of freedom of the order of $10^{23}$ , with the purpose of determining the value of some macroscopic quantities. Ideally, those values are average over all configurations that are available to the system at a given temperature. In statistical physics, one usually defines the average of an observable as:

$\displaystyle \langle A(x)\rangle=\frac{1}{Z}\int_S\mathrm{d}xA(x)e^{-\beta H(x)}$

(3)

where,

$\displaystyle Z=\int_S e^{-\beta H(x)}\mathrm{d}{\bf r}$

(4)

is the systems partition function,

is the Hamiltonean and

denotes integration of all phase space. In practice, however, we can never calculate this integral exactly and are forced to settle for sampling just a finite number of phase space points $\{x_1,x_2,\ldots,x_n\}$ .

One can easily see that the naive idea of simply choosing regularly spaced points would lead to an irregular distribution in phase space, with certain areas with too many points and others with too few. However, if we randomly select our points using an uniforme distribution, we obtained what is usually refered to as simple sampling, according to which Eq. 3 becomes, in the limit $M\to\infty$ :

$\displaystyle \langle A(x)\rangle =\frac{\sum_{i=1}^{M}A(x_i)e^{-\beta H(x_i)}}{\sum_{i=1}^{M}e^{-\beta H(x_i)}}$

(5)

By using this procedure to select the phase space point, we increase the quality of our results but only by increasing the computational resources required and the convergence time. In principle, if instead of picking the points uniformly we were to use a given probability istribution that would privilege certain points at the expense of other, our results would converge faster. In this case, our approximation Eq. 5 would take on the form:

$\displaystyle \langle A(x)\rangle =\frac{\sum_{i=1}^{M}A(x_i)e^{-\beta H(x_i)}/P(x)}{\sum_{i=1}^{M}e^{-\beta H(x_i)}/P(x)}$

(6)

Importance sampling

The obvious choice for in Eq. 6 is $P(x)=e^{-\beta H(x)}$ , in order to simplify our expression. With this choice we obtain just the usual arithmetic average:

$\displaystyle \langle A(x)\rangle =\frac{1}{M}\sum_{i=1}^{M}A(x_i)$

(7)

This form of phase space sampling is commonly refered to as importance sampling, since it attributes a certain degree of importance to each system state, in such a way that states that are more likely will be considered more important that less likely states. The problem is know to implement the importance sampling. Metropolis et al.[1] sugested using a Markov chain², with a transistion probability $W_{s\to s'}$ . This implies that in the limit $M\to\infty$ , converges to $P_{eq}(x_l)=e^{-\beta H(x_l)}/Z$ . For this, it is sufficient, although not necessary, to impose the detailed balance condition,

$\displaystyle W_{s'\to s}P_{t}(s')=W_{s\to s'}P_{t}(s)$

(8)

We can now show that,

$\displaystyle \frac{W_(s\to s')}{W_(s'\to s)}=e^{-\beta\delta H}$

(9)

where $\delta H$ represente the variation in Energy between the two different states. Eq. 9 does not uniquely define $W_{s\to s'}$ and, as suchm there existe several posibilities for this transition rate. The two that are most widely known and used are:

$\displaystyle W_{s\to s'}=\left\{ \begin{array}{ll} \frac{1}{\tau_s}e^{-\beta\d... ... H(x_i)>0\\ &\\ \frac{1}{\tau_s} & \hbox{se}~\delta H(x_i)<0 \end{array}\right.$

(10)

$\displaystyle W_{s\to s'}=\frac{1}{2\tau_s}[1-\tanh(\beta\delta H)]$

(11)

Bibliography

1: N. Metropolis et al.
Equation of state calculations by fast computing machines.
The Journal of Chemical Physics, (21):1087, 1957.

Footnotes

... available ¹: Some numerical methods converge much more rapidly as .
... chain ²: A Markov chain is a type of Markov process in which we discretize time and have a finite (although potentially very large) number of phase space points