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.

8more comments