Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would appreciate any help (answers, pointers to the literature etc.) on the following problem.

Consider a (discrete time) random walk on an N-by-N grid which has two absorbing nodes, namely $(1,1)$ and $(N,N)$. Random walk means that the walker has equal probabilities to move into any neighbor. So if (m,n) is an interior node then he moves equiprobably to any of $(m-1,n)$, $(m+1,n)$, $(m,n-1)$, $(m,n+1)$. But if $(m,n)$ the prob's are different. For instance

(a) from $(1,N)$ he goes equiprobably to $(1,N-1)$ and $(2,N)$.

(b) from $(1,n)$, $1<n<N$ he goes to $(1,n-1)$, $(1,n+1)$, $(2,n)$

(c) etc.

I want to know expected time to absorption. Either an explicit formula or an order estimate is fine.

Thank you for any help you can give


PS: Even better would be an explicit formula for

$T(m,n) = E( \text{time to absorption }| \text{ he starts at node } (m,n) )$

but this is probably too much to ask ... However I understand that $T(m,n)$ satisfies

$$T(m,n)=1+(T(m-1,n)+T(m+1,n)+T(m,n-1)+T(m,n+1))/4$$

in the interior nodes and similar equations on the border. I have also thought of exploiting the connection between absorption time and electrical resistance. In particular, I thought of taking the continuous limit and solving the Laplace equation on a unit square; but this would require applying a unit voltage at the two opposite corners and I do not know how to handle potentials applied to single points.

share|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.