Breiman's first exit times from a square root boundary generalization

Question

The paper "First exit times from a square root boundary" by Breiman, generalizes an observation made by Blackwell and Freedman. In summary: given a zero-mean random walk $S_n$ with i.i.d. increments $X_k$ such that $\mathbb{E}(X_k^2) = 1$, they define the stopping time $T_c = \inf\{n\in\mathbb{N}:|S_n|>c\sqrt{n}\}$ and they proved that $\forall c\geq 1$,$\mathbb{E}(T_c) = \infty$.

My question is about a generalization of this work to $d$-dimensional random walk. Let $\vec{X}_k =(X_k^{(1)},\dots,X_k^{(d)})$ be i.i.d. random vectors such that $\vec{\mu} = \vec{0}$, with diagonal covariance matrix and such that $||\vec{\sigma}||^2 = \sum_{r = 1}^{d}\sigma^2_{(r)} = 1$, where $\sigma^2_{(r)} = \mathbb{E}\left((X^{(r)})^2\right)$.

We define the random walk $\vec{S}_n = \sum_{k = 1}^{n}\vec{X}_k$ and we define the stopping time $\tau_c = \inf\left\{n\in\mathbb{N}:\left|\left|\vec{S}_n\right|\right| > c\sqrt{n}\right\}$.

Question

Is it still true that $\mathbb{E}(\tau_c) = \infty$ for all $c\geq 1$? What's a strategy to attack this problem? Thank you for any advice.

Idea

We observe that $T_c = \inf\{n\in\mathbb{N}:S_n^2 > Cn\}$ and similarly $\tau_c = \inf\left\{n\in\mathbb{N}:\left|\left|\vec{S}_n\right|\right|^2 > Cn\right\}$, where $C = c^2$. We further note that: $$ S_n^2 = S_{n-1}^2+X_n^2+2X_nS_{n-1} $$ $$ \left|\left|\vec{S}_n\right|\right|^2 = \left|\left|\vec{S}_{n-1}\right|\right|^2+\left|\left|\vec{X}_n\right|\right|^2+2\langle \vec{X}_n,\vec{S}_{n-1}\rangle $$ where $\mathbb{E}(X_n^2) = 1$,$\mathbb{E}(X_nS_{n-1}) = 0$ and similarly $\mathbb{E}\left(\left|\left|\vec{X}_n\right|\right|^2\right) = 1$, $\mathbb{E}\left(\langle\vec{X}_n,\vec{S}_{n-1}\rangle\right) = 0$.

$T_c$ and $\tau_c$ are essentially of the "same" form. Is this enough to conclude??

Answer 1

This is more of an extended comment rather than an answer.

---

Breiman proves his result by comparing $S_n$ and $T_c$ with the Brownian motion and the corresponding exit time. And the case of the Brownian motion is reduced to the study of the exit time of the Ornstein–Uhlenbeck process and its first exit time from a symmetric interval. One could probably repeat the proof in higher dimensions, at least in the symmetric case. Here is the sketch.

---

Step 1. Consider the standard Brownian motion $B_t$ in $\mathbb R^d$ and $$ \tau_c = \inf\{t > 1 : |B_t| > c \sqrt{t} \} . $$ The process $X_t = e^{-t} B_{e^{2t}-1}$ is the Ornstein--Uhlenbeck process in $\mathbb R^d$, satisfying the SDE $$ dX_t = \sqrt{2} dW_t - X_t dt , $$ where $W_t$ is another standard Brownian motion in $\mathbb R^d$. Let $\sigma_c$ denote the first exit time of $X_t$ from the ball $\|\vec x\| < c$. Then $$ \mathbb P(\tau_c > e^{2 t} - 1) = \mathbb P(\sigma_c > t) . $$

---

Step 2. The first exit time of the $d$-dimensional Ornstein–Uhlenbeck process from the ball was studied by my colleagues Piotr Graczyk and Tomasz Jakubowski. Theorem 3.1 from their paper Exit Times and Poisson Kernels of the Ornstein–Uhlenbeck Diffusion (DOI:10.1080/15326340802009337 states that if $\tilde\sigma_r$ is the first exit time from the ball $\|\vec x\| < r$ for the solution of $$d\tilde X_t = dW_t - \lambda \tilde X_t dt ,$$ then $$ \mathbb E e^{-s \tilde\sigma_r} = \frac{1}{{_1F_1}(\frac{s}{2\lambda}, \frac{d}{2}, \lambda r^2)} \, .$$ We are interested in $r = c$ and $X_t = \tilde X_{2 t}$ with $\lambda = \frac{1}{2}$, and so $\sigma_c = \frac{1}{2} \tilde \sigma_c$. Hence, $$ \mathbb E e^{-s \sigma_c} = \frac{1}{{_1F_1}(\frac{s}{2}, \frac{d}{2}, \frac{1}{2} c^2)} \, .$$

Note: To answer your question, one would need a similar result for exit times from generalised ellipsoids. There are papers on exit times of O–U processes from more general domains (which I do not know well), but I do not think any of them describes the exponential moments of the exit time; see, for example, DOI:10.1088/1751-8113/48/1/013001 and DOI:10.1088/1751-8121/acc559. Finding the Laplace transform of the exit time amounts to solving an appropriate elliptic PDE in an ellipsoid, I doubt any reasonable closed-form expressions are available in these cases.

---

Step 3. Let $-2 \beta = -2 \beta(d, c)$ be the largest zero of $s \mapsto {_1F_1}(\frac{s}{2}, \frac{d}{2}, \frac{1}{2} c^2)$. Then $$ \mathbb P(\sigma_c > t) \sim \alpha e^{-2 \beta t} , $$ and thus $$ \mathbb P(\tau_c > t) \sim \alpha t^{-\beta} . $$ In particular, $\mathbb E \tau_c < \infty$ if and only if $\beta > 1$. By a coincidence that I do not quite understand, the critical value is $c = \sqrt{d}$.

---

Step 4. Let us come back to the original problem. If $\sigma_1 = \ldots = \sigma_d = 1$, then we expect that the answer is the same for the random walk $\vec S_n$ (a rigorous proof of this statement should likely follow Breiman's argument). After normalisation, we would thus get the following ”educated guess”:

If $\sigma_1 = \ldots = \sigma_d = \frac{1}{\sqrt{d}}$, then $\mathbb P(\tau_c > n) \sim C n^{-\beta(d, c \sqrt{d})}$ for some constant $C$. In particular, $\mathbb E \tau_c < \infty$ if and only if $\beta(d, c \sqrt{d}) > 1$, that is, if $c < 1$.

---

The above conjectured result seems to suggest that nothing changes in higher dimensions. However, things seem to be much more delicate when $\sigma_1, \ldots, \sigma_d$ are not all equal. My guess would be that $c \geqslant 1$ is always sufficient, but it is no longer necessary. However, I do not know how to prove this rigorously.

---

One more comment that perhaps sheds some light on the problem: It is possible to find an exact answer if instead of the Euclidean norm $\|\vec S_n\|$, we consider the maximum norm $\|\vec S_n\|_\infty$ (and if we additionally assume that the coordinates of $S_n$ are independent). Denote the first exit time with this modification by $\tilde \tau_c$. By Breiman's result, $$ \mathbb P(\tilde \tau_c > n) \sim C n^{-\beta(1, c/\sigma_1) - \ldots - \beta(1, c/\sigma_d)} $$ Thus, $\mathbb E \tilde \tau_c < \infty$ if and only if $$ \beta(1, c/\sigma_1) + \ldots + \beta(1, c/\sigma_d) > 1 . $$