$G$ Method in Action: Pivot${}^{\text{+}}$ Algorithm for Self-avoiding Walk

Abstract

The pivot algorithm -- we also call it the pivot chain -- is an algorithm for approximately uniform sampling from ${\Omega }_N,$ the set of $N$-step self-avoiding walks on ${\mathbb{Z}}^d$ ($N,$ $d\ge 1$). Based on this algorithm and the $G$ method, we construct another algorithm/chain, called the pivot${}^{\text{+}}$ algorithm/chain, for approximately uniform sampling from ${\Omega }_N,$ here, $N\ge 2$. The pivot${}^{\text{+}}$ algorithm samples the pivot from the set $\left\{1,2,...,N-1\right\}$ according to the uniform probability distribution on this set while the pivot algorithm samples the pivot from the set $\left\{0,1,2,...,N-1\right\}$ according to the uniform probability distribution on this set, so, on the pivot, the pivot${}^{\text{+}}$ algorithm is better than the pivot algorithm. Further, we obtain another important thing, namely, the pivot${}^{\text{+}}$ algorithm/chain enters, at time $1$, a set $2d$ times smaller than ${\Omega }_N,$ and stays forever in this set, so, at times $1,2,...$ we work with a chain having a state space $2d$ times smaller than ${\Omega }_N$. As to the speed of convergence, we conjecture that the pivot${}^{\text{+}}$ algorithm/chain is faster than the pivot algorithm/chain.

v3: minor improvements (Problem 2.4 was replaced with a harder one, a reference was added...)