4
$\begingroup$

Problem: consider a random walk on a 2d square lattice. We start at the origin and each second we move by one unit either up, down, left or right with equal probability (equal to $1/4$). Suppose there is a square surrounding the origin of the plane, centered at $(0,0)$ and whose sides have length $L=4$, i.e. the vertices of the square are located at the four points $(\pm 2,\pm 2)$.

Question: what is the expected time required to hit the square?

Now, we can get an approximation of the expected time by computing the RMS distance, which is given by $$\sqrt{E(D_N^2)} = \sqrt{N}$$ where $D_N$ is the distance from the origin after $N$ seconds. However, this is obviously not the same as the expected distance itself, which would be $E(|D_N|)$. I know that the latter can be at least computed asymptotically (i.e. when $N\rightarrow \infty$), but for the problem in question we expect $N\sim 4$, which is clearly much smaller than infinity, so I would like to find a more accurate value (if possible!).

I have tried using the results from 1.4.2 in this reference, but I am stuck trying to compute $p_n(x,y;A)$, i.e. the probability of being at point $y$ at time $n$ when starting from point $x$, where $x,y \in A$. For example, let's say we want to compute $p_n(0,0)$, that is the probability of returning to the origin after $n$ steps when there is no boundary. It is known that this is equal to $$\begin{cases}p_{2n}(0,0) = 4^{-2n} {2n \choose n}^2\\ p_{2n+1}(0,0)=0 \end{cases}.$$ My issue is that I don't know how to compute this probability when there is a boundary. Clearly we must have $p_n(0,0;A)\le p_n(0,0)$ since some paths are not allowed anymore, but I'm not sure how to compute it exactly. Honestly I'm not even sure this is the right route to solve the problem.

I hope I stated the problem clearly. I have been away from statistics for a few years, so I'm quite rusty. Any help would be greatly appreciated!

$\endgroup$
10
  • 1
    $\begingroup$ If you split the events into $4$ groups, say $A_n$ being at $(0,0)$ after $n$ steps without having hit the square, $B_n$ being at $(\pm1,0)$ or $(0,\pm1)$ after $n$ steps without hit the square, $C_n$ being at $(\pm1,\pm1)$ after $n$ steps without having hit the square, and $D_n$ first hitting the square at the $n$th step, then you get $P(A_{n+1})=\frac14 P(B_n)$ and $P(B_{n+1})=P(A_n)+\frac12 P(C_n)$ and $P(C_{n+1})=\frac12 P(B_n)$ and $P(D_n)=\frac14 P(B_n)+\frac12 P(C_n)$. This will enable you to find $P(D_n)$ and so $\sum n\,P(D_n)$ as the expected time to hit the square $\endgroup$
    – Henry
    Commented Aug 31, 2021 at 15:27
  • 1
    $\begingroup$ Alternatively, after one step you are at $(\pm1,0)$ or $(0,\pm1)$. Then you either (a) hit the square on the next step or (b) hit the square after two steps or (c) are again at $(\pm1,0)$ or $(0,\pm1)$ after two steps. This gives a very easily solved expression for the expected number of steps to hit the square $\endgroup$
    – Henry
    Commented Aug 31, 2021 at 15:29
  • 1
    $\begingroup$ Thanks for your answer! I managed to solve the problem by using the first method you proposed. I find that the expected time to hit the square should be 4.5, which is also what I find by running simulations. However, I'm not sure I understand your second procedure, could you maybe elaborate a bit on that? $\endgroup$
    – Nate Zane
    Commented Aug 31, 2021 at 18:42
  • 2
    $\begingroup$ $4.5$ is correct. With the second method, if $Z$ is the number of steps needed to hit the square from any of the $(\pm1,0)$ or $(0,\pm1)$ points then you get $\mathbb E[Z] = \frac14 \times 1 +\frac 14 \times 2 + \frac12 \times (2+\mathbb E[Z])$ implying $\mathbb E[Z] =\frac72$; then add $1$ for the initial step from $(0,0)$ $\endgroup$
    – Henry
    Commented Aug 31, 2021 at 18:47
  • $\begingroup$ @Henry I really like your solution, in this case, but can you still apply a similar reasoning when the boundary is not symmetrical?. For instance, how would you compute the expected time required to hit the line passing through (1,0) and (0,1)? $\endgroup$
    – Samantha Smith
    Commented Nov 23, 2021 at 14:05

1 Answer 1

Reset to default
5
$\begingroup$

From comments:

If you split the events into $4$ groups, say $A_n$ being at $(0,0)$ after $n$ steps without having hit the square, $B_n$ being at $(±1,0)$ or $(0,±1)$ after $n$ steps without hit the square, $C_n$ being at $(±1,±1)$ after $n$ steps without having hit the square, and $D_n$ first hitting the square at the $n$th step, then you get

  • $P(A_{n+1})=\frac14P(B_n)$
  • $P(B_{n+1})=P(A_n)+\frac12P(C_n)$
  • $P(C_{n+1})=\frac12P(B_n)$
  • $P(D_{n+1})=\frac14P(B_n)+\frac12P(C_n)$.

This will enable you to find $P(D_n)$ and so $∑nP(D_n)$ as the expected time to hit the square. You applied this and found the answer to be $4.5$, which is correct.

Alternatively, after one step you are at $(±1,0)$ or $(0,±1)$. Then you either

  1. hit the square on the next step or
  2. hit the square after two steps or
  3. are again at $(±1,0)$ or $(0,±1)$ after two steps.

This gives a easily solved expression for the expected number of steps to hit the square. If $Z$ is the number of steps needed to hit the square from any of the $(±1,0)$ or $(0,±1)$ points then you get $E[Z]=\frac14×1+\frac14×2+\frac12×(2+E[Z])$ implying $E[Z]=\frac72$; then add $1$ for the initial step from $(0,0)$ to get $\frac92=4.5$ again.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .