# Scaling of First-passage times for Random Walk on integer lattices

Consider simple symmetric random walk $S_{n} = (S_{n}^{(1)},\dots, S_{n}^{(d)})$ on the d-dimensional integer lattice with starting point the origin.

Let $\tau_{N}$ be the first time $S_{n}$ exits the box $[-N,N] \times \dots \times [-N,N]$. For $d \geq 2$, is anything known about the behaviour of $E(\tau_{N})$ as $N\rightarrow \infty$ ?

Pointers about the corresponding results for Brownian motion also very welcome.

• Define $T_N$ as the time for $S_n^{(1)}$ to leave $[-N,N]$. Define $Z_N$ as the time for a 1-d symmetric random walk to leave $[-N,N]$ (the symmetric random walk can change every step and hence has distribution different from $S_n^{(1)}$). Define $Z_N^{(i)}$ as independent versions of $Z_N$. Then: $$\min[Z_N^{(1)}, \ldots, Z_N^{(d)}] \leq_{st} \tau_N \leq_{st} T_N$$ where $\leq_{st}$ denotes “stochastically less than or equal to.” I think expectations of both upper and lower bounds are proportional to $N^2$. – Michael May 25 '15 at 6:06
• Thanks for your reply. I think the joint distribution (and the expectation) of your lower bound depend on $d$ and it is not easy to calculate the expectation due to the dependency you refer to. – Jack Martin May 25 '15 at 18:48
• Well, I think the upper bound is exactly computable as $E[T_N] = d(N+1)^2$. Do you agree that the lower bound is proportional to $N^2$? It would have expectation $\int_{0}^{\infty} Pr[Z_N^{(1)}>x]^ddx$, I think this can be used to show $N^2$ behavior (though the coefficient multiplier would be loose). – Michael May 25 '15 at 22:20
• Another observation is that the system is similar to a continuous time system of $d$ independent 1-dimensional Markov random walks with forward step rate $\lambda$ and backward step rate $\lambda$. Your discrete-time walk is in fact the embedded chain of this continuous time system. – Michael May 25 '15 at 22:22
• the last question has now been posted in extended for here: mathoverflow.net/questions/207665/… – Jack Martin May 26 '15 at 18:03

You can obtain quickly bounds from above and below by considering the martingale $$Y_n-dn:=\sum_{i=1}^d (S_n^{(i)})^2- dn.$$ Then, at time $\tau_N$ we have the following estimate from below $$Y_{\tau_N}\ge N^2,$$ as one of the components is greater than $N^2$ than by the definition of $N$. The bound from above follows from the representation $$Y_{\tau_N}=Y_{\tau_N-1}+2\sum_{i=1}^d\xi_{\tau_N}^{(d)}S_{\tau_N-1}^{(d)}+\sum_{i=1}^d (\xi_{\tau_N}^{(d)})^2$$ Now note that $|S_{\tau_N-1}^{(d)}|\le N$ by the definition of $\tau_N$. Hence, $$Y_{\tau_N} \le dN^2+2dN+d=d(N+1)^2$$ Now we can apply the optional stopping theorem to obtain $$d\mathbf E[\tau_N]=\mathbf E[Y_{\tau_N}],$$ which we can combine with the above estimates to obtain $$N^2\le d\mathbf E[\tau_N]\le d(N+1)^2.$$ The upper and lower bounds have the same order. It is possible to get sharp asymptotics as well by using the approach in my answer to Stopping time of two dimensional random walk