1
$\begingroup$

Consider a random walk $X_t = \sum_{s=1}^t D_s$ with i.i.d. increments $D_t \in \mathbb{R}^n$,such that $X$ is a martingale $\mathbb{E}[D_t]=\vec{0} \in \mathbb{R}^n$, the support of $D_t$ is bounded, and $D_{t,i}$ has strictly positive variance for all $i \in \{1,\ldots,n\}$.

Is it true that the probability that the random walk eventually pointwise falls below some threshold $k < 0$ equals $1$, i.e. $$ \mathbb{P}[ \exists t \text{ such that } X_{t,i} \leq k \text{ for all } i \in \{1,\ldots,n\} ] = 1 \,. $$ for all $k<0$?

Also posted here the question here

$\endgroup$
8
  • 1
    $\begingroup$ What do you mean by "$D_t$ has strictly positive variance?" Does it mean that the covariance matrix of $D_t$ is positive-definite? $\endgroup$ Feb 11, 2020 at 20:23
  • 2
    $\begingroup$ By the central limit theorem and Borel-Cantelli, the probability that this happens infinitely often is positive, and by Kolmogorov's 0-1 law it is necessarily one. $\endgroup$ Feb 11, 2020 at 23:24
  • 2
    $\begingroup$ If that means component-wise positive variance, it is not enough to capture the dimensionality of your random walk, and so, the answer may be false. For instance, consider the $n=2$ case with the step distribution $$\mathbb{P}(D_t=(1,-1))=\mathbb{P}(D_t=(-1,1))=\frac{1}{2}.$$ Then $\mathbb{E}[D_t]=\vec{0}$ and $\operatorname{Var}(D_{t,i})=1$ for each $i=1,2$, but the walk $(X_t)$ is constrained on the line $x+y=0$, which never touches the region $(-\infty,k)^2$ if $k<0$. $\endgroup$ Feb 12, 2020 at 19:09
  • 1
    $\begingroup$ @MateuszKwaśnicki Indeed. But what happens if only the expectation of the increment exists? (assuming that $D$ is not contained in any hyperplane, of course). $\endgroup$
    – fedja
    Feb 12, 2020 at 23:56
  • 1
    $\begingroup$ @fedja: Good question! Obviously – yes, if $n = 1$ (the random walk is then recurrent). Also – yes, if the distribution of $X_1$ is in the domain of attraction of a stable law, by exactly the same argument as in my previous comment. I bet the answer is the same in the general case, but at this moment I fail to see a proof. $\endgroup$ Feb 13, 2020 at 9:30

1 Answer 1

1
$\begingroup$

An extended comment, answering the question asked by fedja in one of the comments. (Edited: In order to simplify the example I chose to work in dimension two, but this example requires dimension at least three.)

My bet was incorrect: I am very surprised to find that the answer is negative! In order to construct a counterexample (in dimension 3, for simplicity), consider two independent random walks: $A_n$ the simple random walk in $\mathbb{Z}$, and $B_n$ a random walk with symmetric $\alpha$-stable distribution in $\mathbb{R}^2$ for some $\alpha \in (1, 2)$. Fix $\epsilon > 0$. We have $$|B_n| \geqslant n^{1/\alpha - \epsilon}$$ for all $n$ large enough (see Corollary 2 in Takeuchi, doi:10.2969/jmsj/01620109). Furthermore, by LIL, $$A_n \ge -n^{1/2 + \epsilon}$$ for all $n$ large enough. Choosing $\epsilon > 0$ small enough, we find that for an arbitrary constant $p > 0$, $$p A_n + |B_n| \geqslant 0$$ for all $n$ large enough. In other words, with probability one the random walk $(A_n, B_n)$ visits the cone $\{(a, b) \in \mathbb{R} \times \mathbb{R}^2 : p a + |b| < 0\}$ finitely many times.

It remains to choose $p$ and rotate $(A_n, B_n)$ appropriately, so that the above cone fits into the negative octant. To be specific, we set $$X_n = A_n \vec{v}_1 + B_{n,1} \vec{v}_2 + B_{n,2} \vec{v}_3, $$ where $\vec{v}_1 = \tfrac{1}{\sqrt{3}} (1, 1, 1)$ and otherwise $\vec{v}_1, \vec{v}_2, \vec{v}_3$ are arbitrary orthonormal vectors in $\mathbb{R}^3$. Then, by an easy calculation, $$ \max\{X_{n,1}, X_{n,2}, X_{n,3}\} \geqslant \tfrac{1}{\sqrt{3}} A_n + \tfrac{1}{\sqrt{6}} |B_n| \ge 0 $$ for all $n$ large enough (by choosing $p = \sqrt{2}$ above). This means that there is $k < 0$ such that with positive probability we have $X_{n,j} \geqslant k$ for every $j = 1, 2, 3$ and every $n = 0, 1, \ldots$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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