A worm algorithm for random spatial permutations

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. 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.