2
$\begingroup$

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$?

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(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})$

( http://mathworld.wolfram.com/PolyasRandomWalkConstants.html )

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.

What might change if we instead consider a Brownian motion?

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.

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.

https://math.stackexchange.com/questions/250735/the-integer-lattice-green-function-and-its-relation-to-hitting-probabilities-t

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.


Absorbing target = {0,0,0}

Fraction of absorbed walks prior to 10^5 steps = 353/1000 = 35.3%

Mean displacement of walker = 279.824

Mean[# steps until absorbance or 10^5 steps] = 64731.3

Mean[# steps conditioned on absorbance] = 88.7


Absorbing target = {0,0,1}

Fraction of absorbed walks prior to 10^5 steps = 335/1000 = 33.5%

Mean displacement of walker = 288.447

Mean[# steps until absorbance or 10^5 steps] = 66628.2

Mean[# steps conditioned on absorbance] = 382.7


Absorbing target = {0,0,2}

Fraction of absorbed walks prior to 10^5 steps = 155/1000 = 15.5%

Mean displacement of walker = 367.702

Mean[# steps until absorbance or 10^5 steps] = 84556.8

Mean[# steps conditioned on absorbance] = 366.5


Absorbing target = {0,0,3}

Fraction of absorbed walks prior to 10^5 steps = 114 / 1000 = 11.4%

Mean displacement of walker = 385.576

Mean[# steps until absorbance or 10^5 steps] = 88642.4

Mean[# steps conditioned on absorbance] = 371.9


Absorbing target = {0,0,15}

Fraction of absorbed walks prior to 10^5 steps = 16 / 1000 = 1.6%

Mean displacement of walker = 430.08

Mean[# steps until absorbance or 10^5 steps] = 98427.1

Mean[# steps conditioned on absorbance] = 1693.8


Absorbing target = {0,0,30}

Fraction of absorbed walks prior to 10^5 steps = 9 / 1000 = 0.9%

Mean displacement of walker = 440.352

Mean[# steps until absorbance or 10^5 steps] = 99161.4

Mean[# steps conditioned on absorbance] = 6822.2

$\endgroup$
6
  • $\begingroup$ You probably know this but just in case: for $d < 3$, $v_b$ = 1 for any $b$ $\endgroup$
    – Vanessa
    Dec 3, 2012 at 12:29
  • $\begingroup$ @Squark, thanks, it makes sense to me that that's true if $L$ is finite. $\endgroup$ Dec 3, 2012 at 12:56
  • $\begingroup$ Could you explain what "scale with L" means exactly? Do you want an asymptotic when $L\to\infty$? $\endgroup$ Dec 3, 2012 at 19:15
  • $\begingroup$ @Alexandre Eremenko I'm most interested in the regime where $L$ is small. I'd like to understand how the MFPT increases with $L$ in this regime. $\endgroup$ Dec 3, 2012 at 20:17
  • $\begingroup$ Can you give the definition of "scale with L". Otherwise the meaning of your question is not clear. $L$ is an integer, after all, so it cannot be too small:-) $\endgroup$ Dec 5, 2012 at 3:55

1 Answer 1

4
$\begingroup$

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

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

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.

$\endgroup$
1
  • 1
    $\begingroup$ @FloatingForest: why are you surprised? the distance of a RW from its point of origin is roughly $\sqrt{t}$ in any dimension. $\endgroup$ Dec 5, 2012 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.