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?

  • $\begingroup$ Not exactly what you're looking for, but have you considered simulation? $\endgroup$ – Max Jan 19 '12 at 15:17
  • $\begingroup$ How do you define the distance to the origin ? Euclidean, Manhattan, something else ? $\endgroup$ – Sasha Jan 19 '12 at 15:20
  • $\begingroup$ @Sasha I guess Manhattan would be easier, so let's go with that. $\endgroup$ – Matthew Matic Jan 19 '12 at 15:35
  • $\begingroup$ @MatthewMatic The information provided does not specify the Markov chain completely though. Suppose one is at the origin. Does one move away equi-probably, and bias is only present away from the origin ? Suppose one is at $(x,0)$, then there are 3 moves away, and 1 move toward the origin, with probability $1-3p$. If at $(x,y)$, then two moves are away, and two moves are towards. Are their probabilities $p$ and $(1/2-p)$ respectively ? $\endgroup$ – Sasha Jan 19 '12 at 17:43
  • $\begingroup$ @Sasha: I would answer "yes" to all. But let us wait and see what Matthew says. $\endgroup$ – Did Jan 19 '12 at 18:17

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.

  • $\begingroup$ Sasha: What you write is true in such a general setting (i.e. for every finite Markov chain) that more is needed to determine the growth of the hitting time of distance $d$ when $d\to\infty$. $\endgroup$ – Did Jan 19 '12 at 17:19
  • $\begingroup$ @DidierPiau I agree, although I am not sure what technique can be used to establish large $d$ behavior. $\endgroup$ – Sasha Jan 19 '12 at 18:03
  • $\begingroup$ The problem is that on both axis, if $p$ is not small enough, the move is $+1$ with probability $3p\geqslant\frac12$ (elsewhere, the move is $+1$ with probability $2p\lt\frac12$ hence there is a drift to the origin). $\endgroup$ – Did Jan 19 '12 at 18:20
  • $\begingroup$ @DidierPiau Yes, I realized that, and replaced by original plot with $p=\frac{1}{3}$ with two plots, one for $p=\frac{1}{4}$ (unbiased) and $p=\frac{1}{5}$. $\endgroup$ – Sasha Jan 19 '12 at 18:23
  • $\begingroup$ Haaa... the joys of simulation! And what about smaller values of $p$, like $p=\frac1{10}$? In fact I was expecting to see geometric growths and I am rather surprised by their apparent (sub)linearity. Or the analogy with birth-and-death chains biased towards the origin is wrong? $\endgroup$ – Did Jan 19 '12 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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