Page 136 -

2.5 Cluster algorithms 123

went beyond naivepebble-throwing onthe Monte Carlo heliport.In
many fields of statistical mechanics, coordinated cluster moves—the dis-
placement ofmany disks at once, simultaneous flips of spins in a region
of space, collectiveexchange ofbosons, etc.—have overcome the limi-
tations of localMonte Carlo algorithms.The pivotcluster algorithm of
Subsection2.5.2 (Dress and Krauth 1995) is the simplest representative
ofthis class ofmethods.

2.5.1 Avalanches and independent sets
By definition, the local hard-sphere Monte Carlo algorithm rejects all
moves that produce overlaps (see Fig. 2.23). Wenow study an algo-
rithm, which accepts the move of an independent disk even if it gener-
ates overlaps.Itthensimply moves the overlapped particles out ofplace,
and starts an avalanche, where many disks are constrained to move and,
in turn, tip off other disks.Disks that must movebut which entail no
other moves are called “terminal”. Forsimplicity, wesuppose that the
displacement vectoristhe same forall disks (see Fig. 2.48 and Alg. 2.17
(naive-avalanche)).

term.
term.
indep.

a a (+ move) b
indep.
indep.
term.

return move

Fig. 2.48 Avalanche move a → b and its return move, with independent
and terminal disks.

Detailed balance stipulates that, for hard spheres, the return movebe
proposed with the same probability as the forward move.From Fig. 2.48,
it follows that the forward and the return moveswap the labels ofthe
independent and the terminal disks.Inthat example, the return move
has two independent disks, and hence is never proposed byAlg. 2.17
(naive-avalanche),so that a → b must be rejected also. Only avalanche
moves with a singleterminal disk can be accepted.This happens very
rarely:avalanches usually gain breadth when they build up, and do not
taper into asingledisk.
Algorithm 2.17 (naive-avalanche) has a tiny acceptance rate forall
butthe smallest displacement vectors, and wethus need to generalize it,
by allowing more than one independent disk to kick off the avalanche.For