Manhattan distance vs. absorption time on an unbounded integer lattice - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T12:46:17Z http://mathoverflow.net/feeds/question/115277 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115277/manhattan-distance-vs-absorption-time-on-an-unbounded-integer-lattice Manhattan distance vs. absorption time on an unbounded integer lattice FloatingForest 2012-12-03T11:59:15Z 2012-12-05T17:25:39Z <p>Imagine I have unbounded $d$-dimensional integer lattice where I take two vertices, $v_a$ and $v_b$, separated by a fixed Manhattan distance $L$, and I release a random walker at $v_a$ and allow for absorption (with a probability of unity) at $v_b$. How does the probability of absorption and the mean first passage time (MFPT) for absorption at $v_b$ scale with $L$?</p> <p>Polya demonstrated the the origin recurrence probability, $p(d)$, of a random walker on a $d$-dimensional integer lattice is unity for $d = {1,2}$ and that: </p> <p>$p(3) = \frac{6^{\frac{1}{2}}}{32*\pi^3} * \Gamma(\frac{1}{24}) * \Gamma(\frac{5}{24}) * \Gamma(\frac{7}{24}) * \Gamma(\frac{11}{24})$ </p> <p>( <a href="http://mathworld.wolfram.com/PolyasRandomWalkConstants.html" rel="nofollow">http://mathworld.wolfram.com/PolyasRandomWalkConstants.html</a> )</p> <p>From Polya's result I would guess that if $L \approx 1$, the probability of absorption at $v_b$ would be $\approx p(3)$. However, that's simply a guess, and offers little information on the MFPT for absorption.</p> <p>What might change if we instead consider a Brownian motion? </p> <p>Update :: I am most interested in a good estimate for how the absorption probability and MFPT scales as $L$ goes from $1$ to $\infty$, rather than an asymptotic.</p> <p>Update 2 :: I have written a post on mathematics stackexchange asking for further explanation of Omer's answer. My concern was that such a discussion might be too low level for this forum. I hope this is an appropriate thing to do.</p> <p><a href="http://math.stackexchange.com/questions/250735/the-integer-lattice-green-function-and-its-relation-to-hitting-probabilities-t" rel="nofollow">http://math.stackexchange.com/questions/250735/the-integer-lattice-green-function-and-its-relation-to-hitting-probabilities-t</a></p> <p>Update 3 :: I'm simulated random walks on an infinite $Z^3$ integer lattice, where $10^5$ steps without absorbence at a target vertex (near the origin) counts as the walker diverging to infinity. Walks are initialized at the origin, (0,0,0), and values for means-square-displacement (MSD) and the number of steps prior to absorption are averages over $10^3$ iterations. </p> <hr> <p>Absorbing target = {0,0,0}</p> <p>Fraction of absorbed walks prior to 10^5 steps = 353/1000 = 35.3%</p> <p>Mean displacement of walker = 279.824</p> <p>Mean[# steps until absorbance or 10^5 steps] = 64731.3</p> <p>Mean[# steps conditioned on absorbance] = 88.7</p> <hr> <p>Absorbing target = {0,0,1}</p> <p>Fraction of absorbed walks prior to 10^5 steps = 335/1000 = 33.5%</p> <p>Mean displacement of walker = 288.447</p> <p>Mean[# steps until absorbance or 10^5 steps] = 66628.2</p> <p>Mean[# steps conditioned on absorbance] = 382.7</p> <hr> <p>Absorbing target = {0,0,2}</p> <p>Fraction of absorbed walks prior to 10^5 steps = 155/1000 = 15.5%</p> <p>Mean displacement of walker = 367.702</p> <p>Mean[# steps until absorbance or 10^5 steps] = 84556.8</p> <p>Mean[# steps conditioned on absorbance] = 366.5</p> <hr> <p>Absorbing target = {0,0,3}</p> <p>Fraction of absorbed walks prior to 10^5 steps = 114 / 1000 = 11.4%</p> <p>Mean displacement of walker = 385.576</p> <p>Mean[# steps until absorbance or 10^5 steps] = 88642.4</p> <p>Mean[# steps conditioned on absorbance] = 371.9</p> <hr> <p>Absorbing target = {0,0,15}</p> <p>Fraction of absorbed walks prior to 10^5 steps = 16 / 1000 = 1.6%</p> <p>Mean displacement of walker = 430.08</p> <p>Mean[# steps until absorbance or 10^5 steps] = 98427.1</p> <p>Mean[# steps conditioned on absorbance] = 1693.8</p> <hr> <p>Absorbing target = {0,0,30}</p> <p>Fraction of absorbed walks prior to 10^5 steps = 9 / 1000 = 0.9%</p> <p>Mean displacement of walker = 440.352</p> <p>Mean[# steps until absorbance or 10^5 steps] = 99161.4</p> <p>Mean[# steps conditioned on absorbance] = 6822.2</p> http://mathoverflow.net/questions/115277/manhattan-distance-vs-absorption-time-on-an-unbounded-integer-lattice/115346#115346 Answer by Omer for Manhattan distance vs. absorption time on an unbounded integer lattice Omer 2012-12-04T01:13:03Z 2012-12-05T01:35:11Z <p>The probability that a random walk on $Z^d$ from $x$ hits a vertex $y$ is proportional to the Green function $G(x,y)$, which is well known to decay as $c|x-y|^{2-d}$ (using Euclidean distance).</p> <p>The expected time to hit $y$ conditioned on hitting it at all is of order $|x-y|^2$. One way to see this is to compute $\sum_n n p^n_{xy}$, which using the local CLT is of order $\sum n^{1-d/2} e^{-|x-y|^2/2n} \approx |x-y|^{4-d}$. Divide by $G(x,y)$ to get the expected time to hit conditioned on hitting $y$. (Subsequent hits do not have a significant effect.)</p> <p>You can find these in any book dealing with random walks, e.g. Spitzer. You can prove these from the local CLT among other methods.</p>