2d random walk: expected time to hit enclosing square

Question

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!

Answer 1

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.