Demon algorithm

Last updated

The demon algorithm is a Monte Carlo method for efficiently sampling members of a microcanonical ensemble with a given energy. An additional degree of freedom, called 'the demon', is added to the system and is able to store and provide energy. If a drawn microscopic state has lower energy than the original state, the excess energy is transferred to the demon. For a sampled state that has higher energy than desired, the demon provides the missing energy if it is available. The demon can not have negative energy and it does not interact with the particles beyond exchanging energy. Note that the additional degree of freedom of the demon does not alter a system with many particles significantly on a macroscopic level.

Contents

In thermodynamical systems, equal macroscopic properties (e. g. temperature) can result from different microscopic properties (e. g. velocities of individual particles). Computer simulations of the full equations of motion for every individual particle to simulate microscopic properties is computationally very expensive. Monte Carlo methods can overcome this problem by sampling microscopic states according to stochastic rules instead of modeling the complete microphysics.

The microcanonical ensemble is a collection of microscopic states which have fixed energy, volume and number of particles. In an enclosed system with a certain number of particles, energy is the only macroscopic variable affected by the microphysics. The Monte Carlo simulation of a microcanonical ensemble thus requires sampling different microscopic states with the same energy. When the number of possible microscopic states of thermodynamical systems is very large, it is inefficient to randomly draw a state from all possible states and accept it for the simulation if it has the right energy, since many drawn states would be rejected.

The demon algorithm

The full procedure can be summarized by the following steps:

  1. Perform a random change in the state of a randomly chosen particle (e. g. change velocity or position).
  2. Calculate the change in energy of the thermal system.
  3. Negative , i. e. excess energy, is given to the demon by adding to the demon. This case () is always accepted.
  4. The demon provides positive to keep the total energy constant only if it has sufficient energy, i. e. . In this case the change is accepted, otherwise the randomly chosen change in velocity is rejected and the algorithm is restarted from the original microscopic state.
  5. If the change is accepted, repeat the algorithm for the new configuration.

Since energy fluctuations per degree of freedom are only of order 1/N, the presence of the demon has little effect on macroscopic properties of systems with high numbers of particles. After many iterations of the algorithm, the interplay of demon and random energy changes equilibrates the system. Assuming that a particular system approaches all possible states over very long times (quasi-ergodicity), the resulting Monte Carlo dynamics realistically sample microscopic states that correspond to the given energy value. This is only true if macroscopic quantities are stable over many Monte Carlo steps, i. e. if the system is at equilibrium.

See also

Related Research Articles

In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic behavior of nature from the behavior of such ensembles.

In physics, specifically statistical mechanics, an ensemble is an idealization consisting of a large number of virtual copies of a system, considered all at once, each of which represents a possible state that the real system might be in. In other words, a statistical ensemble is a probability distribution for the state of the system. The concept of an ensemble was introduced by J. Willard Gibbs in 1902.

In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain a sample of the desired distribution by recording states from the chain. The more steps are included, the more closely the distribution of the sample matches the actual desired distribution. Various algorithms exist for constructing chains, including the Metropolis–Hastings algorithm.

Internal energy Energy contained in a system, excluding energy due to its position as a body in external force fields or its overall motion

The internal energy of a thermodynamic system is the energy contained within it. It is the energy necessary to create or prepare the system in any given internal state. It does not include the kinetic energy of motion of the system as a whole, nor the potential energy of the system as a whole due to external force fields, including the energy of displacement of the surroundings of the system. It keeps account of the gains and losses of energy of the system that are due to changes in its internal state. The internal energy is measured as a difference from a reference zero defined by a standard state. The difference is determined by thermodynamic processes that carry the system between the reference state and the current state of interest.

Granular material Conglomeration of discrete solid, macroscopic particles

A granular material is a conglomeration of discrete solid, macroscopic particles characterized by a loss of energy whenever the particles interact. The constituents that compose granular material are large enough such that they are not subject to thermal motion fluctuations. Thus, the lower size limit for grains in granular material is about 1 μm. On the upper size limit, the physics of granular materials may be applied to ice floes where the individual grains are icebergs and to asteroid belts of the Solar System with individual grains being asteroids.

In statistical mechanics, the microcanonical ensemble is a statistical ensemble that represents the possible states of a mechanical system whose total energy is exactly specified. The system is assumed to be isolated in the sense that it cannot exchange energy or particles with its environment, so that the energy of the system does not change with time.

Microstate (statistical mechanics)

In statistical mechanics, a microstate is a specific microscopic configuration of a thermodynamic system that the system may occupy with a certain probability in the course of its thermal fluctuations. In contrast, the macrostate of a system refers to its macroscopic properties, such as its temperature, pressure, volume and density. Treatments on statistical mechanics define a macrostate as follows: a particular set of values of energy, the number of particles, and the volume of an isolated thermodynamic system is said to specify a particular macrostate of it. In this description, microstates appear as different possible ways the system can achieve a particular macrostate.

The concept entropy was first developed by German physicist Rudolf Clausius in the mid-nineteenth century as a thermodynamic property that predicts that certain spontaneous processes are irreversible or impossible. In statistical mechanics, entropy is formulated as a statistical property using probability theory. The statistical entropy perspective was introduced in 1870 by Austrian physicist Ludwig Boltzmann, who established a new field of physics that provided the descriptive linkage between the macroscopic observation of nature and the microscopic view based on the rigorous treatment of a large ensembles of microstates that constitute thermodynamic systems.

The kinetic Monte Carlo (KMC) method is a Monte Carlo method computer simulation intended to simulate the time evolution of some processes occurring in nature. Typically these are processes that occur with known transition rates among states. It is important to understand that these rates are inputs to the KMC algorithm, the method itself cannot predict them.

Fundamental thermodynamic relation

In thermodynamics, the fundamental thermodynamic relation are four fundamental equations which demonstrate how four important thermodynamic quantities depend on variables that can be controlled and measured experimentally. Thus, they are essentially equations of state, and using the fundamental equations, experimental data can be used to determine sought-after quantities like G or H. The relation is generally expressed as a microscopic change in internal energy in terms of microscopic changes in entropy, and volume for a closed system in thermal equilibrium in the following way.

Monte Carlo in statistical physics refers to the application of the Monte Carlo method to problems in statistical physics, or statistical mechanics.

Path integral Monte Carlo (PIMC) is a quantum Monte Carlo method in the path integral formulation of quantum statistical mechanics.

In molecular dynamics (MD) simulations, the flying ice cube effect is an artifact in which the energy of high-frequency fundamental modes is drained into low-frequency modes, particularly into zero-frequency motions such as overall translation and rotation of the system. The artifact derives its name from a particularly noticeable manifestation that arises in simulations of particles in vacuum, where the system being simulated acquires high linear momentum and experiences extremely damped internal motions, freezing the system into a single conformation reminiscent of an ice cube or other rigid body flying through space. The artifact is entirely a consequence of molecular dynamics algorithms and is wholly unphysical, since it violates the principle of equipartition of energy.

In computer simulations of mechanical systems, energy drift is the gradual change in the total energy of a closed system over time. According to the laws of mechanics, the energy should be a constant of motion and should not change. However, in simulations the energy might fluctuate on a short time scale and increase or decrease on a very long time scale due to numerical integration artifacts that arise with the use of a finite time step Δt. This is somewhat similar to the flying ice cube problem, whereby numerical errors in handling equipartition of energy can change vibrational energy into translational energy.

Thermodynamic integration is a method used to compare the difference in free energy between two given states whose potential energies and have different dependences on the spatial coordinates. Because the free energy of a system is not simply a function of the phase space coordinates of the system, but is instead a function of the Boltzmann-weighted integral over phase space, the free energy difference between two states cannot be calculated directly from the potential energy of just two coordinate sets. In thermodynamic integration, the free energy difference is calculated by defining a thermodynamic path between the states and integrating over ensemble-averaged enthalpy changes along the path. Such paths can either be real chemical processes or alchemical processes. An example alchemical process is the Kirkwood's coupling parameter method.

The Wang and Landau algorithm, proposed by Fugao Wang and David P. Landau, is a Monte Carlo method designed to estimate the density of states of a system. The method performs a non-Markovian random walk to build the density of states by quickly visiting all the available energy spectrum. The Wang and Landau algorithm is an important method to obtain the density of states required to perform a multicanonical simulation.

The Bennett acceptance ratio method (BAR) is an algorithm for estimating the difference in free energy between two systems . It was suggested by Charles H. Bennett in 1976.

The Monte Carlo method for electron transport is a semiclassical Monte Carlo(MC) approach of modeling semiconductor transport. Assuming the carrier motion consists of free flights interrupted by scattering mechanisms, a computer is utilized to simulate the trajectories of particles as they move across the device under the influence of an electric field using classical mechanics. The scattering events and the duration of particle flight is determined through the use of random numbers.

In computational physics and statistics, the Hamiltonian Monte Carlo algorithm, is a Markov chain Monte Carlo method for obtaining a sequence of random samples which converge to being distributed according to a target probability distribution for which direct sampling is difficult. This sequence can be used to estimate integrals with respect to the target distribution.

In statistics and physics, multicanonical ensemble is a Markov chain Monte Carlo sampling technique that uses the Metropolis–Hastings algorithm to compute integrals where the integrand has a rough landscape with multiple local minima. It samples states according to the inverse of the density of states, which has to be known a priori or be computed using other techniques like the Wang and Landau algorithm. Multicanonical sampling is an important technique for spin systems like the Ising model or spin glasses.

References