The Hamiltonian is H(π) =

Models of random spatial permutations arise in the study of Bose-Einstein condensation. Namely, permutations of sites occur with probabilities depending on lengths of permutation jumps, as well as on interactions between jumps. Below a critical temperature, one observes the onset of long permutation cycles in spite of short individual jump lengths. We have devised several Markov chain Monte Carlo algorithms for sampling from this probability distribution. In this note, we present one particularly promising technique: a worm algorithm. It admits an elegant correctness theory, asymptotically in the number of completed Metropolis sweeps. However, it suffers from a stopping-time problem: the CPU time needed to complete a sweep is strongly quadratic in the number of lattice points N. 1 The probability model The model of random spatial permutations arises from consideration of the Bose gas [Sütő1, Sütő2, GRU, U07, BU07, BU08, SU09]. See also [BBHLV, SU09] for the contentious history of studies of the shift in critical temperature as a function of interaction strength. The state space is ΩΛ,N = Λ N × SN, where Λ = [0, L]3 with periodic boundary conditions. Point positions are X = (x1,...,xN) for x1,...,xN ∈ Λ