Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

http://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

share|improve this question
    
You probably know this but just in case: for $d < 3$, $v_b$ = 1 for any $b$ –  Squark Dec 3 '12 at 12:29
    
@Squark, thanks, it makes sense to me that that's true if $L$ is finite. –  FloatingForest Dec 3 '12 at 12:56
    
Could you explain what "scale with L" means exactly? Do you want an asymptotic when $L\to\infty$? –  Alexandre Eremenko Dec 3 '12 at 19:15
    
@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. –  FloatingForest Dec 3 '12 at 20:17
    
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:-) –  Alexandre Eremenko Dec 5 '12 at 3:55

1 Answer 1

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.

share|improve this answer
1  
@FloatingForest: why are you surprised? the distance of a RW from its point of origin is roughly $\sqrt{t}$ in any dimension. –  Ori Gurel-Gurevich Dec 5 '12 at 1:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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