{"id":4899,"date":"2012-05-27T11:40:50","date_gmt":"2012-05-27T09:40:50","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=4899"},"modified":"2014-06-17T08:52:00","modified_gmt":"2014-06-17T06:52:00","slug":"simulating-random-walks-bridges","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2012\/05\/27\/simulating-random-walks-bridges\/","title":{"rendered":"Simulating random walks bridges"},"content":{"rendered":"

\"A<\/a><\/p>\n

Let us fix \\( {d\\geq1} \\). Let \\( {E_{d,n}} \\) be the set of paths of the simple random walk of \\( {\\mathbb{Z}^d} \\), with \\( {2n} \\) steps, starting and ending at the origin of \\( {\\mathbb{Z}^d} \\). In other words, \\( {\\gamma=(\\gamma_0,\\ldots,\\gamma_{2n})\\in(\\mathbb{Z}^d)^{2n}} \\) belongs to \\( {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. We have<\/p>\n

\\[ \\mathrm{Card}(E_{d,n}) = \\sum_{2k_1+\\cdots+2k_d=2n}\\binom{2n}{k_1,k_1,\\ldots,k_d,k_d} =\\binom{2n}{n}\\sum_{k_1+\\cdots+k_d=n}\\binom{n}{k_1,\\ldots,k_d}^2. \\]<\/p>\n

How to simulate the uniform law on the finite set \\( {E_{d,n}} \\)?<\/p>\n

Case \\( {d=1} \\)<\/b>. The cardinal of \\( {E_{1,n}} \\) is huge:<\/p>\n

\\[ \\mathrm{Card}(E_{1,n})=\\binom{2n}{n}\\sim\\frac{2^{2n}}{\\sqrt{n\\pi}}. \\]<\/p>\n

To simulate the uniform law on \\( {E_{1,n}} \\), it suffices to generate uniformly \\( {n} \\) positions among \\( {2n} \\) positions, which can be done by using a random uniform permutation<\/a> on the vector \\( {V=(1,\\ldots,1,-1,\\ldots,-1)} \\) which contains \\( {n} \\) symbols \\( {+1} \\) and \\( {n} \\) symbols \\( {-1} \\). This produces a random element \\( {\\Gamma} \\) of \\( {E_{1,n}} \\), and for every \\( {\\gamma\\in E_{1,n}} \\), denoting \\( {\\Sigma} \\) the set of permutations of \\( {\\{1,\\ldots,2n\\}} \\) sending the \\( {\\pm 1} \\)'s of \\( {V} \\) to the positions of the \\( {\\pm 1} \\)'s in the edges of \\( {\\gamma} \\),<\/p>\n

\\[ \\mathbb{P}(\\Gamma=\\gamma) =\\sum_{\\sigma\\in\\Sigma}\\frac{1}{(2n)!} =\\frac{n!n!}{(2n)!}=\\frac{1}{\\mathrm{Card}(E_{1,n})}. \\]<\/p>\n

The complexity of this algorithm is linear in \\( {n} \\). Here is the pseudo-code:<\/p>\n

V = [ones(1,n),-ones(1,n)]
\nGAMMA = cumsum([0,V(randperm(2n))])<\/p>\n

Case \\( {d=2} \\).<\/b> Using the Vandermonde binomial convolution formula, we find<\/p>\n

\\[ \\mathrm{Card}(E_{2,n}) =\\binom{2n}{n}\\sum_{k}\\binom{n}{k}^2 =\\binom{2n}{n}^2\\sim\\frac{4^{2n}}{n\\pi}. \\]<\/p>\n

Let us use the fact that \\( {{(Z_n)}_{n\\geq0}={(X_n,Y_n)}_{n\\geq0}} \\) is a simple random walk on \\( {\\mathbb{Z}^2} \\) iff \\( {{(X_n-Y_n)}_{n\\geq0}} \\) and \\( {{(X_n+Y_n)}_{n\\geq0}} \\) are two independent simple random walks on \\( {2\\mathbb{Z}} \\). Moreover, \\( {Z_n=(0,0)} \\) iff \\( {X_n-Y_n=0} \\) and \\( {X_n+Y_n=0} \\). Thus, if \\( {\\gamma_1} \\) and \\( {\\gamma_2} \\) are independent and uniform on \\( {E_{1,n}} \\) then \\( {(\\gamma_1-\\gamma_2,\\gamma_1+\\gamma_2)\/2} \\) is uniform on \\( {E_{2,n}} \\). This gives again an algorithm with a linear complexity in \\( {n} \\). Here is the pseudo-code:<\/p>\n

V = [ones(1,n),-ones(1,n)]
\nA = cumsum([0,V(randperm(2n))\/2])
\nB = cumsum([0,V(randperm(2n))\/2])
\nGAMMA = [A-B;A+B]<\/p>\n

General case \\( {d\\geq1} \\).<\/b> One may compute \\( {C_{d,n}=\\mathrm{Card}(E_{d,n})\/\\binom{2n}{n}} \\) recursively:<\/p>\n

\\[ C_{d,n}=\\sum_{k=0}^n\\binom{n}{k}^2C_{d-1,n-k}. \\]<\/p>\n

For \\( {d\\geq3} \\), no simple closed formula seems to be known for \\( {C_{d,n}} \\), see the book Problems in applied mathematics<\/a> (problem 87-2 page 149). Let \\( {\\gamma} \\) be an element of \\( {E_{d,n}} \\), and let \\( {k_1,\\ldots,k_d} \\) be the number of \\( {e_1,\\ldots,e_d} \\) steps. Since the path starts and ends at the same point, this is also the number of \\( {-e_1,\\ldots,-e_d} \\) steps, and \\( {k_1+\\cdots+k_d=n} \\). To make \\( {\\gamma} \\) random and uniform, we may first generate \\( {(k_1,\\ldots,k_d)} \\) with probability<\/p>\n

\\[ p_{k_1,\\ldots,k_d} =\\frac{\\binom{n}{k_1,\\ldots,k_d}^2}{C_{d,n}} \\]<\/p>\n

then create the vector<\/p>\n

\\[ V=(e_1,\\ldots,e_1,\\ldots,e_d,\\ldots,e_d,-e_1,\\ldots,-e_1,\\ldots,-e_d,\\ldots,-e_d) \\]<\/p>\n

where for each \\( {1\\leq i\\leq d} \\), both \\( {e_i} \\) and \\( {-e_i} \\) appear \\( {k_i} \\) times, and finally permute this vector with a random uniform permutation<\/a>. This gives a random \\( {\\Gamma} \\) in \\( {E_{d,n}} \\) such that for every \\( {\\gamma\\in E_{d,n}} \\) with \\( {k'_i} \\) the number of \\( {e_i} \\) in \\( {\\gamma} \\), and \\( {\\Sigma} \\) the set of permutations of \\( {\\{1,\\ldots,2n\\}} \\) sending the \\( {\\pm e_i} \\)'s of \\( {V} \\) to the positions of the \\( {\\pm e_i} \\)'s in the edges of \\( {\\gamma} \\),<\/p>\n

\\[ \\mathbb{P}(\\Gamma=\\gamma) =\\sum_{\\sigma\\in\\Sigma}\\frac{p_{k_1',\\ldots,k_d'}}{(2n)!} =\\frac{k_1'!^2\\cdots k_d'!^2}{(2n)!}p_{k_1',\\ldots,k_d'} =\\frac{1}{\\mathrm{Card}(E_{d,n})}. \\]<\/p>\n

This algorithm, valid for any \\( {d\\geq1} \\), coincides with the one used above for \\( {d=1} \\), but differs from the one used above for \\( {d=2} \\) (which was based on a special property). Here is the pseudo-code (does not include the implementation of randk):<\/p>\n

K = randk(n,d)
\nt = 0
\nfor i=1 to d do
\nif K(i)\\( {>} \\)0 then
\nV(t+1:t+K(i),i) = ones(K(i),1)
\nt = t+K(i)
\nendif
\nendfor
\nV = [V;-V]
\nGAMMA = cumsum([zeros(1,d);V(randperm(2n),:)])<\/p>\n

Note.<\/b> This algorithm reduces the problem to the implementation of randk, for which I do not have an elegant solution for now when \\( {d\\geq3} \\), apart using the classical algorithm for discrete laws<\/a>, or a rejection method, or a Metropolis-Hastings approximate algorithm. It is maybe possible to reduce the problem to the simulation of the standard multinomial distribution. The vector \\( {(k_1,\\ldots,k_d)} \\) belongs to the discrete simplex<\/p>\n

\\[ \\{(k_1,\\ldots,k_d)\\in\\{0,1,\\ldots,n\\}:k_1+\\cdots+k_d=n\\}, \\]<\/p>\n

and the cardinal of this set is \\( {\\binom{n+d-1}{n}} \\) (the number of multinomial coefficients). As for the standard multinomial distribution, the largest value of \\( {p_{k_1,\\ldots,k_d}} \\) is achieved when \\( {k_1,\\ldots,k_d} \\) are such that \\( {\\lfloor n\/d\\rfloor \\leq k_i\\leq \\lceil n\/d\\rceil} \\) for every \\( {1\\leq i\\leq d} \\) (central multinomial coefficients).
\nNote.<\/b> The analysis of the coupon collector problem<\/a> indicates that when \\( {d\\gg1} \\) and \\( {n\\gg d\\log(d)} \\) then almost all the \\( {k_i} \\)'s are non zero.
\nNote.<\/b> To solve the more general random walk bridge problem in which the starting point \\( {x} \\) and the ending point \\( {y} \\) are not the same, one may think of adding \\( {|y_i-x_i|} \\) occurrences of \\( {\\mathrm{sign}(y_i-x_i)e_i} \\) in the recipe.
\nProblem.<\/b> Solve the non symmetric case (step \\( {e_i} \\) with probability \\( {p_{e_i}} \\)).<\/p>\n","protected":false},"excerpt":{"rendered":"

Let us fix \\( {d\\geq1} \\). Let \\( {E_{d,n}} \\) be the set of paths of the simple random walk of \\( {\\mathbb{Z}^d} \\), with…<\/p>\n

Continue readingSimulating random walks bridges<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":187},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4899"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=4899"}],"version-history":[{"count":105,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4899\/revisions"}],"predecessor-version":[{"id":7394,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/4899\/revisions\/7394"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=4899"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=4899"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=4899"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}