How to find a general formula for random walking with a certain well-defined boundary?

Question

Recently, I have been considering random walking on $\mathbb{Z}^2$, with equal probabilities $p$ for all $4$ directions.

More specifically, I have been looking at the expected time $\mathbb{E}_{n} [T]$ for $n\in\mathbb{N}$ required for a point starting at the origin to reach a specific boundary curve defined as the set of all ordered pairs $(x,y)\in\mathbb{Z}^2$ such that $|x|+|y|=n$.

I have manually calculated for and verified by computation that $\mathbb{E}_{1} [T]=1$, $\mathbb{E}_{2} [T]=\frac{8}{3}$, $\mathbb{E}_{3} [T]=\frac{39}{7}$, and $\mathbb{E}_{4} [T]=\frac{1152}{119}$.

I was wondering if there was a way to obtain a general formula for $\mathbb{E}_{n} [T]$?

Answer 1

Not an answer -- just feels too long to be a comment.

We use Misha's comment about rotating the square and consider two i.i.d random walks. Note, on any move, our $x$ coordinate moves by $\pm \frac{1}{\sqrt{2}}$, as does our $y$ coordinate. The game ends when either the $x$ or the $y$ coordinate reaches $\frac{N}{\sqrt{2}}$. Therefore, this is equivalent to the following.

Let $X_n = R_1 + \dots R_n$ and $Y_n = S_1 + \dots S_n$ where $R_i, S_i \sim \{-1, 1\}$ with the stopping time defined as $\min\{t: |X_t| = N \text{ or } |Y_t| = N\}.$ Therefore, we have $$\mathbb{E}[\min\{t: |X_t| = N \text{ or } |Y_t| = N\}] $$$$ = \sum_{n \in \mathbb{N}}\mathbb{P}(\min\{t: |X_t| = N \text{ or } |Y_t| = N\} > n) $$$$ = \sum_{n \in \mathbb{N}} \mathbb{P}(|X_t| \text{ and } |Y_t| < N \ \forall \ 0\leq t \leq n) $$$$ = \sum_{n \in \mathbb{N}} \mathbb{P}(|X_t| < N \ \forall \ 0\leq t \leq n) \mathbb{P}(|Y_t| < N \ \forall \ 0\leq t \leq n) . $$

Define $f(l,b)$ as the probability the absolute value of a random walk of length $l$ never exceeds a boundary $b$. Then, our final answer is $$\sum_{n \in \mathbb{N}} f(n, N)^2 .$$ I tried my hand at finding a closed form for $f$. If it exists I can't find it. Maybe the asymptotics will be easier to find.

Answer 2

Define $$ \omega_j = \frac{(2j+1)\pi}{2N} $$ for $j\in\mathbb{N}$. Then the expected time to escape is $$ \mathbb{E}_{N} [T] = \frac{1}{N^2}\sum_{j=0}^{N-1}\sum_{k=0}^{N-1}\frac{(-1)^{j+k}\sin \omega_j \sin\omega_k}{(1-\cos\omega_j)(1-\cos\omega_j\cos\omega_k)(1-\cos\omega_k)}. $$ This can be derived from the survival probability at time $t$ in the 1D walk, which is $$ f_N(t)=\frac{1}{N}\sum_{j=0}^{N-1}\frac{(-1)^j\sin\omega_j\left(\cos\omega_j\right)^t}{1-\cos\omega_j}; $$ as described in the other answer, $\mathbb{E}_{N} [T]=\sum_t f_N(t)^2$, and after squaring $f$, the sum over $t$ becomes a geometric series in $\cos \omega_j \cos\omega_k$.

---

Update:

Interestingly, the expected escape time for the 1D walk ($N^2$) can be obtained exactly by taking a leading-order approximation (in small $\omega$) to the summand and letting the sum go to $\infty$:

$$ \frac{1}{N}\sum_{j=0}^{N-1}\frac{(-1)^j \sin\omega_j}{(1-\cos\omega_j)^2} \approx \frac{1}{N}\sum_{j=0}^{\infty}\frac{(-1)^j \omega_j}{(\omega_j^2 / 2)^2} = \frac{4}{N} \sum_{j=0}^{\infty}\frac{(-1)^j}{\omega_j^3} = N^2 \left[ \frac{32}{\pi^3}\sum_{j=0}^{\infty}\frac{(-1)^j}{(2j+1)^3}\right ] = N^2. $$

This doesn't work in 2D. But the leading-order behavior does seem to be correct:

$$ \begin{eqnarray} \mathbb{E}_{N} [T] &=& \frac{1}{N^2}\sum_{j,k}\frac{(-1)^{j+k} \sin\omega_j \sin\omega_k}{(1-\cos\omega_j)(1-\cos\omega_j\cos\omega_k)(1-\cos\omega_k)} \\ &\approx& \frac{1}{N^2}\sum_{j,k}\frac{(-1)^{j+k} \omega_j \omega_k}{(\omega_j^2 / 2)(\omega_j^2/2+\omega_k^2/2)(\omega_k^2/2)} \\ &=& \frac{8}{N^2} \sum_{j,k}\frac{(-1)^{j+k}}{\omega_j (\omega_j^2+\omega_k^2)\omega_k} \\ &=& N^2 \left[ \frac{128}{\pi^4}\sum_{j,k}\frac{(-1)^{j+k}}{(2j+1)\left((2j+1)^2+(2k+1)^2\right)(2k+1)}\right ] \\ &\approx& 0.589371 N^2. \end{eqnarray} $$