# 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. – Mateusz Kwaśnicki Oct 20 '19 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. – Mateusz Kwaśnicki Oct 20 '19 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$. – Thomas Dybdahl Ahle Oct 20 '19 at 19:06
• OK, I have a question then. In the statement of the problem, you mention the inequality $\operatorname{Pr}[\cdots] \geqslant 1 / m^d$. Do you insist on the constant $1$ and exponent $d$, or any bound of the form $C / m^\alpha$ would be fine for you? – Mateusz Kwaśnicki Oct 20 '19 at 19:48
• @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. – Thomas Dybdahl Ahle Oct 20 '19 at 21:28

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.