Simulating random walks bridges again

Let \( {E_{d,n}} \) be the set of paths of the simple random walk on \( {\mathbb{Z}^d} \) with \( {2n} \) steps starting and ending at the origin. That is, \( {\gamma=(\gamma_0,\ldots,\gamma_{2n})\in E_{d,n}} \) iff \( {\gamma_0=\gamma_{2n}=0} \) and \( {\gamma_i-\gamma_{i-1}\in\{\pm e_1,\ldots,\pm e_d\}} \) for every \( {1\leq i\leq 2n} \), where \( {e_1,\ldots,e_d} \) is the canonical basis. The uniform law on \( {E_{d,n}} \) is the law induced by the simple random walk \( {{(X_k)}_{k\geq0}} \) on \( {\mathbb{Z}^d} \) conditional on \( {\{X_0=0,X_{2n}=0\}} \). We have already discussed the simulation problem of the uniform law on \( {E_{d,n}} \) in a previous post.

It is quite natural to ask about the simulation of the uniform law on the subset \( {F_{d,n}} \) of \( {E_{d,n}} \) constituted by the paths of the simple random walk on \( {\mathbb{Z}^d} \) with \( {2n} \) steps touching the origin only at times \( {0} \) and \( {2n} \). That is, \( {\gamma=(\gamma_0,\ldots,\gamma_{2n})\in F_{d,n}} \) iff \( {\gamma\in E_{d,n}} \) and \( {\gamma_i\neq0} \) for every \( {1\leq i\leq 2n-1} \). Here again, the uniform law on \( {F_{d,n}} \) is the law induced by the simple random walk \( {{(X_k)}_{k\geq0}} \) on \( {\mathbb{Z}^d} \) conditional on \( {\{X_0=0,X_1\neq0,\ldots,X_{2n-1}\neq0,X_{2n}=0\}} \). We have of course \( {F_{1,n}=E_{1,n}} \) while \( {F_{d,n}\varsubsetneq E_{d,n}} \) if \( {d>1} \).

One may observe that if \( {\gamma\in E_{d,n}} \) and if \( {\left\Vert\gamma_i\right\Vert_1=r} \), then \( {\left\Vert\gamma_{i+1}\right\Vert_1=r\pm 1} \), meaning that \( {\gamma} \) follows a one-dimensional random walk on \( {\ell^1} \) spheres. Actually, when \( {\gamma} \) runs over \( {F_{d,n}} \) then \( {\left\Vert\gamma\right\Vert_1} \) runs over the non negative part of \( {F_{1,n}} \). This observation provides an algorithm producing all the elements of \( {F_{d,n}} \). Unfortunately, this does not help to simulate the uniform law on \( {F_{d,n}} \) since the law of \( {\left\Vert\gamma\right\Vert_1} \) is complicated. This is due to the special role of the corners of the \( {\ell^1} \) spheres (these points with some null coordinates), from which the path has more possibilities to increase his \( {\ell^1} \) norm, and the importance of this phenomenon increases with \( {d} \) (we see here clearly the transcient behavior in action).

The method used to simulate the uniform law on \( {E_{d,n}} \) does not work for the uniform law on \( {F_{d,n}} \). One may of course cook up a Metropolis-Hastings algorithm but this will not produce an exact simulation. The best after all is probably to proceed using the rejection method: simulate random elements of \( {E_{d,n}} \) according to the uniform law on \( {E_{d,n}} \) until we fall into \( {F_{d,n}} \). The number of rejections is then random and follows a geometric distribution with parameter

\[ p_{d,n} =\frac{\mathrm{card}(F_{d,n})}{\mathrm{card}(E_{d,n})} =\frac{\mathbb{P}_0(\tau_d=2n)}{\mathbb{P}_0(X_{2n}=0)} =\mathbb{P}_0(\tau_d=2n|X_{2n}=0) \]

where \( {\tau_d=\inf\{k>0:X_k=0\}} \) and \( {\mathbb{P}_0=\mathbb{P}(\cdot|X_0=0)} \). For a fixed \( {n} \), we have \( {p_{d,n}\rightarrow1} \) as \( {d\rightarrow\infty} \), and this is in favor of the rejection algorithm.

Note. The sequences \( {{(\mathrm{card}(F_{2,n}))}_{n\geq1}} \) and \( {{(\mathrm{card}(F_{3,n}))}_{n\geq1}} \) are known as sequences A054474 and A049037 in The On-Line Encyclopedia of Integer Sequences. There are formulas for the generating function, expressing essentially the fact that the elements of \( {F_{d,n}} \) can be extracted from the elements of \( {E_{d,n}} \). It is unclear that these sequences satisfy to an algebraic recursion.

Note. This post benefited from informal discussions with Charles Bordenave, Mireille Bousquet-Mélou, Pietro Caputo, and Pierre Del Moral at various occasions. The rejection method is also at the heart of the best algorithm for the simulation of the uniform law on the set of \( {d} \)-regular graphs (the so called configuration model based on random permutations).