Monte Carlo Algorithms

Equiprobability

Equal_probability_disks.jpg
Equal-probability principle for hard disks

The equal-probability principle translates the Boltzmann distribution for a system whose energy is either zero or infinity:



The concept of "equiprobability" often poses problems. Notice that:

  • In the above picture, equiprobability is a statement in 18 dimensions (d N, with d the dimension and N the number of spheres): The 18-dimensional probability distribution, in Cartesian coordinates, is uniform, but not its lower-dimensional projections.
  • The equal-probability principle (= the Boltzmann distribution for hard spheres) is valid independent of the boundary conditions.
  • The equal-probability principle neither contradicts the presence of indirect attraction between particles nor the existence of phase transitions


Random deposition


In random sequential deposition configurations are not equally probable. A simplified one-dimensional discrete hard-rod model allows us to compute deposition probabilities explicitly and show that they are not the same: we suppose that rods may be deposited onto five sites, with a minimum distance of three sites between them. After placing the first rod (with the same probability on all sites), we try again and again until a two rod configuration without overlap is found.

rods.png
Random deposition of discrete hard rods.


The configurations a and b are thus generated with half the probability of their parent, whereas the configuration c, a unique descendant, inherits all the probability of its parent. We obtain



whereas



This counterexample proves that random deposition is incorrect for hard disks and spheres in any dimension, if the aim is to generate configurations with equal probabilities.


Direct-sampling algorithm: the tabula rasa implementation

(Python code)

from random import uniform
 
def dist(x,y):
   return  (x[0] - y[0])**2 + (x[1] - y[1]) ** 2
N = 4
sigma = 0.2; sigma_sq = sigma**2
condition = False
while condition == False:
    L = [(uniform(sigma, 1 - sigma), uniform(sigma, 1 - sigma))]
    for k in range(1,N):
        b = (uniform(sigma, 1 - sigma), uniform(sigma, 1 - sigma))
        min_dist = min(dist(b, x) for x in L)
        if min_dist < 4 * sigma_sq:
            condition = False
            break
        else:
            L.append(b)
            condition = True
print L


Markov-chain sampling: the "adult game"


Local Metropolis algorithm (Python code)


from random import uniform as ran, choice
 
L = [(0.25, 0.25), (0.75, 0.25), (0.25, 0.75), (0.75, 0.75)]
sigma = 0.20; sigma_sq = sigma**2
delta = 0.15
for iter in range(100000):
    a = choice(L)
    L.remove(a)
    b = (a[0] + ran(-delta, delta), a[1] + ran(-delta, delta))
    min_dist = min((b[0] - x[0]) ** 2 + (b[1] - x[1]) ** 2 for x in L)
    box_cond = min(b[0],b[1]) < sigma or max(b[0], b[1]) > 1 - sigma
    if box_cond or min_dist < 4 * sigma ** 2:
        L.append(a)
    else:
        L.append(b)
print L


Acceptance rate

paccept2.png
Acceptance rate for 16 disk in a square box (PBC) as a function of density. Dotted line is the Virial expansion result, applicable at low densities.


Equivalence between Monte Carlo algorithm and molecular dynamics

The Boltzmann distribution describes physical reality, as we all know. But for any decades it was unclear whether this could actually be proven, or was more like an axiom of statistical mechanics. The mentioned mathematical papers by Sinai (1970) and by Simanyi (2003) have proven the exact validity of equipartition for finite hard-disk systems.

References

  1. ^ Y. G. Sinai Dynamical systems with elastic reflections, [http://iopscience.iop.org/0036-0279/25/2/R05 Russian Mathematical Surveys 25, 137-189 (1970)]
  2. ^ N. Simanyi, Proof of the Boltzmann-Sinai ergodic hypothesis for typical hard disk systems[http://www.springerlink.com/content/yf9uw55m3vm6utqx/Inventiones Mathematicae 154, 123-178 (2003)]