2

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

$$\frac{p(x,y)}{p(x',y')} = \exp\left[ \frac{V(x',y') - V(x,y)}{T} \right]$$

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)$

$$\frac{p_s}{p(x,y)} = \exp\left[ - \frac{V(x,y)}{T} \right]$$.

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?

loonatick
  • 113
Matthew Matic
  • 457
  • Not exactly what you're looking for, but have you considered simulation? – assumednormal Jan 19 '12 at 15:17
  • How do you define the distance to the origin ? Euclidean, Manhattan, something else ? – Sasha Jan 19 '12 at 15:20
  • @Sasha I guess Manhattan would be easier, so let's go with that. – Matthew Matic Jan 19 '12 at 15:35
  • @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 ? – Sasha Jan 19 '12 at 17:43
  • @Sasha: I would answer "yes" to all. But let us wait and see what Matthew says. – Did Jan 19 '12 at 18:17
  • @Sasha. Sorry for the ambiguity. I have edited my question to specify exactly what my problem is and what I want to know. – Matthew Matic Jan 20 '12 at 11:29
  • @Matthew: You completely modified your post, to the point where every comment and Sasha's answer, all based on the original version, simply do not apply anymore. DO NOT DO THAT. Please revert the post to the previous version, numbered #2 in the list of revisions. – Did Jan 20 '12 at 13:33
  • @Didier Done. Sorry about that. – Matthew Matic Jan 20 '12 at 13:59

1 Answers1

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.

Sasha
  • 70,631
  • 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$. – Did Jan 19 '12 at 17:19
  • @DidierPiau I agree, although I am not sure what technique can be used to establish large $d$ behavior. – Sasha Jan 19 '12 at 18:03
  • 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). – Did Jan 19 '12 at 18:20
  • @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}$. – Sasha Jan 19 '12 at 18:23
  • 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? – Did Jan 19 '12 at 19:48
  • @DidierPiau Computing mean hitting times for $d$ from 2 to 8, the small $p$ leading terms is $p^{1-d} \left(\frac{2}{2^d-1} + \mathcal{o}(p) \right)$ – Sasha Jan 19 '12 at 20:06
  • Whose main term is $(2p)^{1−d}$, which grows geometrically for small $p$... Ha! I knew it! :-) Thanks, Sasha. – Did Jan 19 '12 at 20:56
  • 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. – Matthew Matic Jan 20 '12 at 11:45