Probability that a 1-D zero mean random walk remains at each step inside a square root boundary

Question

Let $W_n = \sum_{i = 1}^{n}X_i$ be a random walk on $\mathbb{R}$, where the increments $X_i$ are i.i.d., symmetric around the origin ($X\sim -X$), such that $-1\leq |X(\omega)| \leq 1$ $\forall\omega\in\Omega$, $\mathbb{E}(X) = 0$ and $Var(X) = \mathbb{E}(X^2) = \sigma^2 = \frac{1}{2}$. I would like to bound from above the following probability as a function of $k$: $$ P\Bigl(\bigcap_{n = 1}^{k}\Bigl\{|W_n| \leq\sqrt{n}\Bigr\}\Bigr)\leq h(k) \mbox{ ?} $$ where $\lim_{k\to\infty} h(k) =0$, because I manage to prove it using zero-one Kolmogorov's law and the fact that $\frac{W_n}{\sqrt{n}}$ converges in distribution to a normal random variable.

I know that it may be a really simple question, although I just can not find the right bound.. I have tried lots of different techniques but none of them seem to work properly. I think that a useful fact is the simmetry ( since $\forall n\in\mathbb{N},W_n\sim-W_n$ ) and the fact that $W_n$ has zero mean and (in general) bounded moments.

PS: maybe a more simple question could be to bound from above $$ P\Bigl(\bigcap_{n = 1}^{k}\Bigl\{W_n \leq\sqrt{n}\Bigr\}\Bigr)\leq g(k) \mbox{ ?} $$ using a decreasing function $g(k)$ with the same properties of $h(k)$. Also note that in general: $$ P\Bigl(\bigcap_{n = 1}^{k}\Bigl\{|W_n| \leq\sqrt{n}\Bigr\}\Bigr) \leq P\Bigl(\bigcap_{n = 1}^{k}\Bigl\{W_n\leq\sqrt{n}\Bigr\}\Bigr), $$ so $g(k)$ also bounds $P\Bigl(\bigcap_{n = 1}^{k}\Bigl\{|W_n |\leq\sqrt{n}\Bigr\}\Bigr)$.

Note

The existence of such $h(k)$ has already been proven by the fact that $$ \lim_{k\to\infty} P\Bigl(\bigcap_{n = 1}^{k}\Bigl\{|W_n| \leq\sqrt{n}\Bigr\}\Bigr) = 0 $$ although I would like an "analytic" expression for it.

References

Maybe the paper "Darling-Erdős theorems for normalized sums of i.i.d. variables close to a stable law"

https://projecteuclid.org/journals/annals-of-probability/volume-26/issue-2/Darling-Erd%C5%91s-theorems-for-normalized-sums-of-iid-variables-close/10.1214/aop/1022855652.full

may help along with the question

Concentration inequalities for the maximum of the rescaled/normalized sum of iid random variables

In fact

$$ P\Bigl(\bigcap_{n = 1}^{k}\Bigl\{W_n\leq\sqrt{n}\Bigr\}\Bigr)\leq P\Bigl(\max_{1\leq n\leq k}\frac{W_n}{\sqrt{n}} \leq 1\Bigl) $$ which could possibly be bounded from above with some decreasing function $m(k)$ using some of those results.

Answer 1

Let $m:=\lfloor\log_2 k\rfloor$, so that $2^m\le k<2^{m+1}$. Then the probability in question is $$ \begin{aligned} P_k&:=P(|W_n|\le\sqrt n\ \forall n\le k) \\ &\le P(|W_{2^j}|\le2^{j/2}\ \forall j\in\{0,\dots,m\}) \\ &\le P(|W_{2^j}-W_{2^{j-1}}|\le2^{j/2}+2^{(j-1)/2}\ \forall j\in\{1,\dots,m\}) \\ &=\prod_{j=1}^m p_j, \end{aligned} $$ where $$p_j:=P(|W_{2^j}-W_{2^{j-1}}|\le2^{(j-1)/2}(1+\sqrt2)).$$ Noting that here $E|X_1|^3\le EX_1^2=1/2$ and using the Berry–Esseen inequality with Shevtsova's constant $0.4748<1/2$, we get $$p_j\le q_j:=\min(1,q+2^{1-j/2}),$$ where $$q:=P(|B_{2^{j-1}}|/\sqrt2\le2^{(j-1)/2}(1+\sqrt2)) =P(|B_1|\le\sqrt2+2)=0.999360\dots$$ and $B_\cdot$ is a standard Brownian motion. Since $q_j=1$ iff $j\le23$, we conclude that $$ \begin{aligned} P_k&\le Cq^{m-23}\le\frac C{q^{24}}\,q^{\log_2k}=\frac C{q^{24}}\,k^{-t}, \end{aligned} $$ where $$C:=\prod_{j=24}^\infty\Big(1+\frac1q\,2^{1-j/2}\Big)=1.0016\dots$$ (so that $\frac C{q^{24}}=1.017\dots$) and $$t:=-\frac{\ln q}{\ln2}=0.00092313\dots.$$

---

We see that the exponent $t$ is very small. It can be improved with a bit of extra effort, in particular by using $c^j$ instead of $2^j$ with $c>1$ close to $1$. However, the improved exponent will still be small. The reason for that can be seen in the law of the iterated logarithm, which in this case will state that $$\limsup_n\frac{|W_n|}{\sqrt{n\ln\ln n}}=1,$$ and the fact that $\ln\ln n$ grows very slowly, so that $\sqrt{n\ln\ln n}$ will not differ too much from $\sqrt n$; e.g., $\ln\ln(10^{10})=3.13\dots$. So, the bounds $\sqrt n$ on $|W_n|$ are not too confining to cause $P_k$ go to $0$ perceptibly fast.

Answer 2

Consider a similar question for Brownian motion: $$F(T)=\mathbb{P}(|B_t|\leq \sqrt{t}\quad \forall 1\leq t\leq T).$$ Then, we have $$F(2^N)\leq \mathbb{P}(|B_{t}-B_{2^n}|\leq 2\sqrt{2^{n+1}} \quad \forall n=0,\dots,N-1,\, t\in [2^{n},2^{n+1}]),$$ because if the inequality is not satisfied, then at least one of $B_t$ and $B_{2^n}$ is outside the interval $(-\sqrt{2^{n+1}},\sqrt{2^{n+1}})$. Now, $\{B_t-B_{2^{0}}\}_{t\in[2^0,2^1)},\{B_t-B_{2^{1}}\}_{t\in[2^1,2^2)},\dots$ are independent, and by Brownain scaling, for all $n$, we have $$ \mathbb{P}(\max_{t\in[2^n,2^{n+1})}|B_t-B_2^{n}|\leq2\sqrt{2^{n+1}})=\mathbb{P}(\max_{t\in[1,2)}|B_t-B_1|\leq 2\sqrt{2})=:q. $$ Therefore, $F(2^N)\leq q^N$, that is, $F(T)\leq q^{-1}T^\sigma$, where $\sigma=\frac{\log q}{\log 2}.$

For the random walk, the result will be the same, e.g., by KMT or Skorokhod coupling with the Brownian motion, see e.g. Section 5 of Mörters and Peres book.

Answer 3

There are several papers discussing the crossing of square root boundary by a random walk, which seem to be relevant.

1. Breiman (1967). First exit times from a square root boundary. https://projecteuclid.org/ebooks/berkeley-symposium-on-mathematical-statistics-and-probability/Proceedings-of-the-Fifth-Berkeley-Symposium-on-Mathematical-Statistics-and/chapter/First-exit-times-from-a-square-root-boundary/bsmsp/1200513456

2. Greenwood and Perkins (1983). A conditioned limit theorem for a random walks and Brownian local time. https://projecteuclid.org/journals/annals-of-probability/volume-11/issue-2/A-Conditioned-Limit-Theorem-for-Random-Walk-and-Brownian-Local/10.1214/aop/1176993594.full

3. [Edit] Uchiyama (1980). Brownian first exit from and sojourn over one sided moving boundary and application. https://link.springer.com/article/10.1007/BF00535355