# Probability that random walk stays in quadrant

Let $$S_n = \sum_{i=1}^n X_i$$ where $$X_i \in \mathbb R^d$$ are iid. random vectors with $$E[X_i]=0$$.

We want to lower-bound the probability that \begin{align} \forall_{n=1}^m S_n \le k \end{align} where $$k\in \mathbb R_+^d$$ is some constant vector with all positive terms. In other words, we want each $$S_n$$ to (nearly) stay in the negative quadrant for all $$n$$ up to $$m$$.

Clearly, if $$k\approx\sqrt{m\log\log m}\, \text{Cov}[X_i]$$ we can get this with high probability, however, if $$k$$ is not allowed to grow with $$m$$ we still get from the Central Limit Theorem that roughly $$\Pr[S_m \le 0]\ge 1/2^d$$.

In my work, we are just looking to show that for some $$k\sim\log m$$, we get at least polynomial probability, that is $$\Pr[\forall_{n=1}^m S_n \le k]\ge 1/m^d$$.

It's natural to try Doob's inequality, since $$T_n = \max\{(S_n)_1, \dots, (S_n)_d\}$$ is a sub-martingale, so $$\Pr[\max_{n=1}^m T_n \ge k] \le E[\exp(\lambda T_m)]\exp(-\lambda k)$$. Unfortunately $$E[T_n] > 0$$, and moment based methods are (as far as I am aware) unable to show anything for tresholds smaller than the mean.

Another observation is that $$k$$ must be $$>0$$ since something like the uniform distribution over $$\left(\begin{smallmatrix}1\\-1\end{smallmatrix}\right)$$ and $$\left(\begin{smallmatrix}-1\\1\end{smallmatrix}\right)$$ will clearly never hit the negative quadrant. In this way the case $$d\ge 2$$ differs from $$d=1$$ which is easy to handle.

I'm wondering if something like the reflection principle can be made to work for this case, so one could focus on $$S_m$$ which is easy to handle using CLT.

• (1/2) For the 2-D Brownian motion, the exit time $T$ from the wedge of aperture $\theta$ has finite $p$-th moment if and only if $p < \tfrac{\pi}{2 \theta}$, see [Spitzer, 1958, TAMS 87: 187–197]. His method was to find the expression for the distribution function of $T$. A similar result for some cones in higher dimensions was given in [DeBlassie, 1987, PTRF 74(1): 1–29]. After an appropriate linear transformation, this gives asymptotics for the tail of the exit time from the "quadrant" for the non-isotropic Wiener process. Oct 20, 2019 at 18:37
• (2/2) The asymptotics for the random walk should be essentially the same; however, I do not know a reference for this claim. If true, this would answer your question: the decay is indeed polynomial in $m$. However, the optimal exponent $\alpha$ in $$\operatorname{Pr}[S_n \leqslant k \text{ for } n = 1, 2, \ldots, m] \geqslant C m^{-\alpha}$$ will generally depend on the covariance matrix of your random walk, not just on the dimension. Oct 20, 2019 at 18:40
• @mateusz I should maybe state that I need a non-asymptotic bound, but it certainly doesn't have to be optimal in terms of the exponent on $m$. Oct 20, 2019 at 19:06
• @mateusz Yeah, anything like that would be fine. I realize though that my example is probably a counter example, since it forces a 1d random walk to stay in a window of constant width, which doesn't happen with more than $exp(-Cm)$ probability. So some condition on positive correlation is probably needed. Oct 20, 2019 at 21:28
• You can use the results of the paper below, which proves the polynomial asymptotics for probability of a random walk staying in a cone. Asymptotics will give you a lower bound of the form CV(k)n^{-p/2}. Will it be sufficient? Random walks in cones D Denisov, V Wachtel Ann. Probab. 43 (3), 992-1044 arxiv.org/abs/1110.1254 If covariance between components of a vector is non zero, then first you apply a linear transformation to obtain zero coviarance, as explained in Example 2, page 997. After that Theorem 1, page 996, gives polynomial decay. Oct 21, 2019 at 6:06

In the special case of two dimensions, we get in the Brownian case the tail exponent $$1/3$$ by mapping the complement of the quadrant onto a half plane by the conformal map $$z \mapsto z^{2/3}$$ and using the conformal invariance of planar Brownian motion.