2
$\begingroup$

I'm looking at a random walk on a square lattice with a bias toward the origin. Any step away from the origin occurs with probability a probability p, which is less than the unbiased value of 1/4. I'd like to know the average amount of time it would take for the walker to reach a distance d from the origin. Does anyone have an idea how to solve this, or references to look at?

Edit: Some elaboration to my question. I consider a process for which it is only possible to move to neighbouring sites. Let's use (x,y) and (x',y') to denote the co-ordinates for two (of the four) sites neighbouring the site (x_0,y_0), and p(x,y) and p(x',y') to denote the probabilities of moving from (x_0,y_0) to (x,y) and (x',y') respectively. Then

p(x,y)/p(x',y') = exp[ (V(x',y') - V(x,y))/T ]

Where V(x,y) is a potential of the form

V(x,y) = (x^2+y^2)^(alpha/2).

There is also a probability p_s of staying at (x_0,y_0)

p_s/p(x,y) = exp[ - V(x,y)/T ].

I think this should be enough to specify the process.

Ideally I would like an expression for the hitting time to a boundary that lies at a radius l from the origin in terms of d, alpha and T. It would support the arguments I want to make if the hitting time is O(exp[d]) for all positive alpha and T. So I'm quite happy to study a simpler model if it can be expected to behave in an equivalent way. Can anyone give me some idea how to approach this. Or can you argue that what I want to argue is obviously true. Or can you point me toward some resources?

  • 0
    @Didier Done. Sorry about that.2012-01-20

1 Answers 1

1

Let $\mathsf{B}$ denote the set of boundary points, and $\mathsf{D}$ denote the set of interior points. For a given lattice point $x$, let $\kappa_x$ denote the mean number of steps for the random walk to reach $\mathsf{B}$ if started at $x$.

Obviously $\forall y \in \mathsf{D}$, $\kappa_y = 0$. Conditioning on the previous state we have the following set of equations for these means: $ \{ \kappa_x = 1 + \sum_{x^\prime \in \mathsf{D}} p_{x,x^\prime} \kappa_{x^\prime} | x\in \mathsf{D} \} $

Solve this system, $\kappa_\text{origin}$ will give you the solution.

Highly recommended reference on Markov chains, and hitting times, is the book by J.R. Norris, "Markov chains". Its first chapter, which covers hitting times, is available online for free from the author.


I write a little Mathematica code which find the mean to hit the boundary $\mathsf{B} = \{ (x,y) : |x|+|y| \geqslant d \}$. It assumes $p_{(0,0),(\pm 1,0)} = p_{(0,0),(0,\pm 1)} = \frac{1}{4}$, and that moves away from the origin have probability $p$, and that moves towards, are equally probable. Here are mean hitting times for few small values of $d$:

In[229]:= BoundaryMeanHittingTime[2, p]  Out[229]= 2/(3 p)  In[230]:= BoundaryMeanHittingTime[3, p]  Out[230]= 1 + 2/(7 p^2)  In[231]:= BoundaryMeanHittingTime[4, p]  Out[231]= (2 (1 - 3 p + 15 p^2 - 8 p^3 + 16 p^4))/(p^3 (15 - 5 p +     18 p^2)) 

After repeating computations for $2 \leqslant d \leqslant 9$, it seems like mean hitting time is a rational function in $p$ such that $ m_d(p) = p^{1-d} \frac{2}{2^d-1} \left( 1+ \mathcal{o}(p) \right) $

enter image description here

I can make the code available if needed. It's grown a little long to paste it in.

  • 0
    Thanks for this. From your result it seems I can conclude (given my revised question) that m_d = O( exp[d] ) for alpha=1 and all positive T.2012-01-20