3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (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. $\endgroup$ – Mateusz Kwaśnicki Oct 20 '19 at 18:37
  • $\begingroup$ (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. $\endgroup$ – Mateusz Kwaśnicki Oct 20 '19 at 18:40
  • $\begingroup$ @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$. $\endgroup$ – Thomas Dybdahl Ahle Oct 20 '19 at 19:06
  • $\begingroup$ 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? $\endgroup$ – Mateusz Kwaśnicki Oct 20 '19 at 19:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Thomas Dybdahl Ahle Oct 20 '19 at 21:28
1
$\begingroup$

See Theorem 1 in D. Denisov, V. Wachtel, Random walks in cones, Ann. Probab. 43 (2015), no. 3, 992–1044.

which also has a historical discussion. An earlier somewhat weaker result is in Lemma 10.40 of N. Th. Varopoulos, Potential theory in conical domains, Math. Proc. Cambridge Philos. Soc. 125 (1999), no. 2, 335–384.

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.

$\endgroup$
  • $\begingroup$ Denisov mentions the first paper in the comments above, but in our case we need a non-asymptotic result, more like Berry Esseen, though we don't need it as tight. I got a version of Varopoulos, 1999, but the lemmas aren't numbered, so I'm not sure which one is 10.40, and whether this result the same issue. $\endgroup$ – Thomas Dybdahl Ahle Nov 15 '19 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.