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
add comment

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.