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
    Commented Dec 3, 2012 at 12:29
  • $\begingroup$ @Squark, thanks, it makes sense to me that that's true if $L$ is finite. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Dec 5, 2012 at 1:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .