Page 137 -

124 Hard disks and spheres

procedure naive-avalanche
input {x 1 ,..., x N }
k ← nran(1,N)
δ ←{ran(−δ, δ) , ran(−δ, δ)}
construct move (involving disks {k 1 ,... ,k M })
if (movehas singleterminal disk)then

for l =1,... ,M do

+ δ
x k l ← x k l
output {x 1 ,... , x N }
——
Algorithm 2.17 naive-avalanche. Avalanche cluster algorithm for
hard disks, with a low acceptance rate unless |δ| is small.

concreteness, wesuppose that avalanches must be connected and that
they must have a certain disk l in common.Under this condition, there

disk l

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

k = 7 k = 8 k = 9 k = 10 k = 11 k = 12

Fig. 2.49 The move a → b, and all avalanches containing the disk l for
a displacement δ. The avalanche k = 1 realizes the move.

are now 12connected avalanches containing disk l (see Fig. 2.49). This
means that the a priori probabilityofselecting the frame k =1,rather
than another one, is 1/12.Asinthe studyof the trianglealgorithm, the
use ofapriori probabilities obliges usto analyze the return move.Inthe
configuration b of Fig. 2.48, with a return displacement −δ, 10 connected
avalanches contain disk l, of which one (the frame k = 8) realizes the
return move (see Fig. 2.50). The a priori probabilityofselecting this
return moveis 1/10. Wethus arriveat

1 one ofthe 12avalanches
A(a → b)= ,
12 in Fig. 2.49

1 one ofthe 10 avalanches
A(b → a)= .
10 in Fig. 2.50
These a priori probabilities must be entered into the detailed-balance