Timeline for Probability that random walk stays in quadrant
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2019 at 13:29 | comment | added | Thomas Dybdahl Ahle | @TOM I assume you mean very large anti-diagonal entries. This would fit with the (-1,1), (1,-1) example in the question. If the variables have standard deviation = 1, I think we should be able to get something for constant $k$ (or maybe $k=O(log n)$ independent of the distribution, but for $k=0$ we probably need to assume covariance > -1. | |
| Nov 15, 2019 at 3:14 | answer | added | Yuval Peres | timeline score: 2 | |
| Nov 8, 2019 at 0:32 | comment | added | TOM | Please ignore the sentence starting with "Otherwise...", replace it with "Otherwise, if I formally interpret your question - you are looking for a uniform bound for all distributions satisfying the constrains, then just taking independent normal random variables with very large diagonal entries shows that this probability is arbitrary small. In which parameters of the distributions would you like the bounds?". | |
| Nov 8, 2019 at 0:14 | comment | added | TOM | Dear Thomas, to put the question in the correct framework it could make sense to actually state the restrictions on the random vectors $X_i$ that should also be there probably (like boundedness, moment conditions, tail conditions on components). Otherwise, if I formally interpret your question - you are looking for a uniform bound for all distributions satisfying the constrains you have listed, the best lower bound is $0$, since if the $X_i$'s have the degenerate distributions, this bound is realized. But, of course, it is useless. | |
| S Nov 7, 2019 at 21:03 | history | bounty ended | CommunityBot | ||
| S Nov 7, 2019 at 21:03 | history | notice removed | CommunityBot | ||
| Oct 30, 2019 at 19:53 | history | edited | Thomas Dybdahl Ahle | CC BY-SA 4.0 |
deleted 3 characters in body
|
| S Oct 30, 2019 at 19:33 | history | bounty started | Thomas Dybdahl Ahle | ||
| S Oct 30, 2019 at 19:33 | history | notice added | Thomas Dybdahl Ahle | Draw attention | |
| Oct 22, 2019 at 12:46 | comment | added | Thomas Dybdahl Ahle | @DenisDenisov I'm mostly interested in $d=2$, and currently we're looking at simple 0-1 random walks (shifted to mean 0). I'd like to be able to handle Gaussian steps as well though. | |
| Oct 22, 2019 at 8:20 | comment | added | Denis Denisov | This is an interesting question. Do you have any further specific details about the random walk, or you are interested in a general random walk? | |
| Oct 21, 2019 at 11:45 | comment | added | Thomas Dybdahl Ahle | @DenisDenisov This is essentially what we want. I only wonder if it is possible to get a (possible weaker) non-assymptotic version? | |
| Oct 21, 2019 at 6:06 | comment | added | Denis Denisov | 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 20, 2019 at 21:34 | comment | added | Mateusz Kwaśnicki | Yes, that's right: one needs to assume $X_i$ are not concentrated on a hyperplane disjoint from the negative orthant. | |
| Oct 20, 2019 at 21:28 | comment | added | Thomas Dybdahl Ahle | @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 19:48 | comment | added | Mateusz Kwaśnicki | 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? | |
| Oct 20, 2019 at 19:06 | comment | added | Thomas Dybdahl Ahle | @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 18:40 | comment | added | Mateusz Kwaśnicki | (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:37 | comment | added | Mateusz Kwaśnicki | (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 17:52 | history | edited | Thomas Dybdahl Ahle | CC BY-SA 4.0 |
notation
|
| Oct 20, 2019 at 17:34 | history | asked | Thomas Dybdahl Ahle | CC BY-SA 4.0 |