Page 138 -

2.5 Cluster algorithms 125

condition
A(a → b) P(a → b) = A(b → a) P(b → a) .

propose accept propose accept
Detailed balance is realized byuse of the generalized Metropolis algo-
rithm
12
P(a → b)= min 1, =1.
10
Itfollows that the move a → b in Fig. 2.48 must be accepted with
probability1.

k = 1 k = 2 k = 3 k = 4 k = 5 k = 6

k = 7 k = 8 k = 9 k = 10

Fig. 2.50 Return move b → a and all avalanches containing disk l for a
displacement −δ. The avalanche k = 8 realizes the return move.

The algorithm wehavediscussed in this subsection needs to count
avalanches, and to samplethem.Forsmall systems, this can be done by
enumerationmethods.Itis unclear, however, whether a general efficient
implementationexists forcounting and sampling avalanches, because
this problem is related to the task ofenumerating the number of inde-
pendent sets of a graph, a notoriously difficultproblem.(The application
to the special graphs that arise in ourproblem has not been studied.)
Weshall find a simpler solutionin Subsection2.5.2.

2.5.2 Hard-sphere cluster algorithm

The avalanche cluster algorithm of Subsection2.5.1 suffers froman im-
balance between forward and return moves because labels of indepen-
dent and terminal disks are swapped between the two displacements, and
because their numbers are notnormally the same.In the present subsec-
tion, weshow how to avoid imbalances, rejections, and the complicated
calculations of Subsection2.5.1 byuse ofapivot: rather than displacing
each particleby aconstant vector δ, wechoose a symmetryoperation
that, when applied twice to the same disk, brings it back to the original
position.Forconcreteness, weconsider reflections abouta verticalline,
but other pivots (symmetry axes orreflectionpoints) couldalso be used.