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.

Improve this question
$\endgroup$
13
  • $\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
    Commented Oct 20, 2019 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
    Commented Oct 20, 2019 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
    Commented Oct 20, 2019 at 19:06
  • 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
    Commented Oct 20, 2019 at 21:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Denis Denisov
    Commented Oct 21, 2019 at 6:06

1 Answer 1

Reset to default
2
$\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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Nov 15, 2019 at 14:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .