clothes_pins_system.png
A configuration of 15 clothes-pins on a segment of length L

Don't hesitate to ask questions and make remarks on this wiki page.

Introduction

We consider the problem of hard "spheres" in one dimension, so-called "clothe pins". We are interested in sampling configurations from the microcanonical equilibrium distribution, where all allowed configurations have the same probability. The pins are attached on a line of length L, and have a width equal to 2σ. A configuration is allowed when pins do not overlap and lie on the segment [0,L].
clothes_pin_scheme.png
Each clothes-pin has width 2σ

Naive sampling for N clothes-pins

Here is the naive pin-sampling algorithm. It has an extremely high rejection rate, so do not really expect it to terminate in any reasonable time.
import random, pylab
 
N = 15; L = 10; sigma = 0.1; statistics = 2000
data = []
for iter in range(statistics):
    while True:
        x_sorted = sorted([random.uniform(sigma, L - sigma) for k in range(N)])
        min_dist = min(x_sorted[k + 1] - x_sorted[k] for k in range(N - 1))
        if min_dist > 2* sigma: break
    data += x_sorted
pylab.title('Density of '+str(N)+' clothes-pins with sigma='+str(sigma)+' on a line of length L='+str(L))
pylab.hist(data,bins=100,normed=True)
pylab.savefig('clothes_pins.png')
pylab.show()

Interlude: computing the partition function

Let's consider a function

of the positions xi's of the N pins characterising whether or not a configuration is allowed:


The partition function writes (for distinguishable pins)


Explain why

where

is a characteristic function, equal to 1 if

and equal to 0 otherwise.

Show that


Rejection-free sampling algorithm

We thus see that the effective space in which all positions live is the segment [0,L-2]. To sample a configuration, one may thus sample N reals yi (with i running from 0 to N-1) in this segment, sort them, and define the positions of the pins by adding (2σ + 1)i to the ith of them.

Direct_pin: rejection-free sampling of the clothes-pin configurations -- standard loops

The below programs implement the direct-sampling without rejections for the clothes-pins. It directly generates the histogram of the particle positions.
import random, pylab
 
N = 24; L = 30; sigma = 0.5; statistics = 40000
data = []
for stat in range(0, statistics):
    y_unsorted = []
    for i in range(N):
        y_unsorted.append(random.uniform(0, L - 2 * N * sigma))
    y_sorted = sorted(y_unsorted)
    x = []
    for i in range(N):
        x.append(y_sorted[i] + (2 * i + 1)*sigma)
        data.append(x[i])
pylab.title('Density of '+str(N)+' clothes-pins with sigma='+str(sigma)+' on a line of length L='+str(L))
pylab.hist(data,bins=500,normed=True)
pylab.show()

Direct_pin: rejection-free sampling of the clothes-pin configurations -- using list comprehension
Here is a condensed version of the above program using list comprehensions.
import random, pylab
N = 24; L = 30; sigma = 0.5; statistics = 20000
data = []
for stat in range(statistics):
    y_sorted = sorted([random.uniform(0, L - 2 * N * sigma) for k in range(N)])
    data += [(y_sorted[k] + (2 * k + 1) * sigma) for k in range(N)]
pylab.title('Density of '+str(N)+' clothes-pins with sigma='+str(sigma)+' on a line of length L='+str(L))
pylab.hist(data,bins=1000,normed=True)
pylab.savefig('clothes_pins.png')
pylab.show()
Density of clothes-pin centers
Clothes_pins.png
Output of the clothes-pins program.
  • The density of clothes-pin centers presents oscillations. Comment on them.
  • Is this compatible with having a uniform distribution? Determine analytically the histogram for N=2.
  • Propose an algorithm implementing periodic boundary conditions. Do you expect oscillations in this case?
  • Can you extend this algorithm to more than one dimension?

Program for periodic boundary

One can add a fixed random real number between 0 and L (denoted shift below) to the positions found using the rejection-free algorithm above.
import random, pylab
N = 24; L = 30; sigma = 0.5; statistics = 50000
data = []
for stat in range(statistics):
    y_sorted = sorted([random.uniform(0, L - 2 * N * sigma) for k in range(N)])
    shift = random.uniform(0, L)
    data += [(shift+y_sorted[k] + (2 * k + 1) * sigma) % L for k in range(N)]
pylab.title('Density of '+str(N)+' clothes-pins with sigma='+str(sigma)+' on a line of length L='+str(L))
pylab.hist(data,bins=1000,normed=True)
pylab.savefig('clothes_pins.png')
pylab.show()

Print this page.