6
$\begingroup$

Consider a random walk on the real time, starting from $0$. But this time assume that we can decide, for each step $i$, a step size $t_i>0$ to the left or the right with equal probabilities.

To formalize this, we have $(X_n)_{n\geq 0}$ such that $X_0=0$, $Pr[X_n=t_n]=0.5$ and $Pr[X_n=-t_n]=0.5$ (hence still $E(X_i)=0$). Let $I=[-1,1]$ and $$p=Pr[\sum_{i=1}^n X_i \in I. \forall n\geq 0]$$

The question is: does there exist a sequence $(t_i)$ such that $t_i>0$ and $\sum_{i=0}^\infty=\infty$ (i.e. $(t_i)$ diverges), to ensure $p>0$.

Clearly such a sequence does not exist to let $p=1$, and intuitively it seems to me that neither exists $(t_i)$ to force $p>0$, but I am looking for a rigorous proof or disproof. Moreover, I am not exactly sure whether this kind of questions has been studied, so references would be appreciated.

$\endgroup$

2 Answers 2

10
$\begingroup$

Yes. Indeed, if $s = \sum_{i \geq 1} t_i^2 <1$, then $$ \mathbb{P}[ \ \ \forall n, \sum_{i=1}^n X_i \in [-1,1] \ \ ] \geq 1-s > 0. $$ To see this, note that $M_n = |\sum_{i=1}^n X_i|$ is a nonnegative submartingale, so that Doob's martingale inequality yields $$ \mathbb{P}[ \max_{1 \leq j \leq n} M_j > 1 ] \leq \mathbb{E}[M_n^2] = \sum_{i=1}^n t_i^2 \leq s. $$ Letting $n$ tends to infinity, one gets $$ \mathbb{P}[ \sup_{j \geq 1} M_j > 1 ] \leq s, $$ hence the result by taking the complement.

Remark : In the other direction, one can show that if $$ \mathbb{P}[ \ \ \forall n, \sum_{i=1}^n X_i \in [-1,1] \ \ ] \geq c > 0, $$ then $$ s = \sum_{i \geq 1} t_i^2 \leq \frac{14}{c^2}. $$ One first note that one must have $|t_i| \leq 2$ for all $i$. One has $|\cos(2 \pi \xi)| \leq e^{-2 \pi^2 \xi^2 }$ whenever $|\xi| \leq 2 \delta$, with $\delta = 0.14$, hence $$ |\mathbb{E}[e^{-2i \pi \xi \sum_{j=1}^n X_j} ]| = \prod_{j=1}^n |\cos(2 \pi \xi t_j)| \leq e^{-2 \pi^2 \xi^2 \sum_{i=1}^n t_i^2} $$ whenever $|\xi| \leq \delta$. Let $\chi$ be the Beurling-Selberg majorant of $\mathbb{1}_{[-1,1]}$ with parameter $\delta$ : one has $\chi \geq \mathbb{1}_{[-1,1]}$, $||\chi||_{L^1}= 2 + \delta^{-1}$, and its Fourier transform $\hat{\chi}$ is supported on $[-\delta,\delta]$. In particular : $$ c \leq \mathbb{E}[\chi(\sum_{i=1}^n X_i)] = \int_{\mathbb{R}} \hat{\chi}(\xi) \mathbb{E}[e^{-2i \pi \xi \sum_{j=1}^n X_j} ] d \xi \leq (2 + \delta^{-1}) \int_{\mathbb{R}} e^{-2 \pi^2 \xi^2 \sum_{i=1}^n t_i^2} d \xi, $$ and thus $$ c \leq \frac{2 + \delta^{-1}}{\sqrt{2 \pi \sum_{i=1}^n t_i^2}}. $$ This implies $$ \sum_{i=1}^n t_i^2 \leq \frac{(2 + \delta^{-1})^2}{2 \pi c^2} \leq \frac{14}{c^2}, $$ hence the result.

$\endgroup$
7
$\begingroup$

The crucial requirement is that $\sum_{i=0}^\infty t_i^2 < \infty$. See Kolmogorov's two-series theorem and also the more general Kolmogorov's three-series theorem.

$\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.