3
$\begingroup$

Let $\lbrace X_n, n \geq 1 \rbrace$ be i.i.d random variables taking values in $\lbrace -1, 1 \rbrace$, and \begin{align*} S_n = \sum_{i = 1}^{n} X_i \end{align*} be a random walk. Let $f$ be a function $\mathbb{N} \to \mathbb{R}^+$. Define a stopping time $J$ as \begin{align*} J=\inf\{n \geq 0\mid S_n \geq f(n) \} \end{align*} Do there exist $a, b$ so that when $f(n) = a\sqrt{n} + b$, we have \begin{align*} \lim_{n \to \infty} Pr[J \leq n] < 1\ ?\end{align*}

This can be proved if $f(n) = 2\sqrt{n\log{n} + b}$, a sketch is as follows

Let $C_i$s be some unimportant constants. We can bound by Hoeffding/Chernoff that $Pr[S_n \geq f(n)] \leq C_1n^{-2}e^{-C_2b}$. Then by union bound it can be shown that $Pr[\lbrace \exists n, S_n \geq f(n) \rbrace] \leq C_3e^{-C_4b}$, then we just need to choose a sufficiently large value for b

This proof do not generalize to the tighter case where $f(n) = O(\sqrt{n})$ though

$\endgroup$
4
  • $\begingroup$ Wht are your thoughts on this? $\endgroup$
    – Did
    Commented Jan 9, 2016 at 8:08
  • $\begingroup$ I think I can prove this if $f(n) = a\sqrt{n}\log{n} + b$. But to tighten it to $\sqrt{n}$ seems quite hard $\endgroup$ Commented Jan 9, 2016 at 8:14
  • $\begingroup$ OK. Then show what you can do. $\endgroup$
    – Did
    Commented Jan 9, 2016 at 8:15
  • $\begingroup$ Added a proof of the simpler case $\endgroup$ Commented Jan 9, 2016 at 8:24

1 Answer 1

4
$\begingroup$

No, there do not exist such $a,b$.

The law of the iterated logarithm for simple random walk states that, almost surely, $$\limsup_{n \to \infty} \frac{S_n}{\sqrt{2 n \log \log n}} = 1.$$ In particular, almost surely, there exist infinitely many $n$ such that $S_n \ge \sqrt{n \log \log n} \ge a\sqrt{n}+b$, since the second inequality holds for all sufficiently large $n$.

$\endgroup$
1
  • $\begingroup$ Wow, thanks a lot! This problem has troubled me for quite a while. $\endgroup$ Commented Jan 9, 2016 at 8:43

You must log in to answer this question.

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