Let $S_n = \sum_{k=1}^n X_i$ be a simple random walk, where $X_1, X_2, \dots$ are independent Bernoulli random variables, $\mathbb{P}(X_k = 1) = \mathbb{P}(X_k = -1) = \frac 1 2$.

Let $T_1 = 1, T_{j+1} = \inf \{i > T_j: |S_i| \ge \sqrt{i}, \operatorname{sgn}(S_i) = -\operatorname{sgn}(S_{T_j})\}$ for $j = 1, 2, ...$. Let $N_n = \max \{j: T_j \le n \}$ - the number of times the random walk bounces between the borders $-\sqrt{x}$ and $\sqrt{x}$. For an illustration see the wiki page for the law of iterated logarithm.

What can be said about $N_n$ (its expectation, distribution)? Any suggestions about the literature?

Edit: I can get the following upper bound for the expectation. Call a time $t \ge 2$ critical if $S_t = 0$ and the random walk reaches $\sqrt{t}$ without returning to 0. Then $$\mathbb{P}(t \mbox{ is critical}) = {\mathbb P}(S_t = 0) {\mathbb P}(\exists j: S_j \ge \sqrt{t}, S_1 S_2 ... S_{j-1} \ne 0),$$ which is, using well known facts, equal to $$\frac 1 {2^{2k}} \binom {2k} k \frac 1 2 \frac 1 {\lceil \sqrt {2k} \rceil} \le \frac 1 {2 k \sqrt{2\pi}}$$ if $t = 2k$ and $0$ otherwise. By symmetry $${\mathbb E} N_n \le 1 + \sum_{2 \le t \le n,\, t=2k} \mathbb{P} (t \mbox{ is critical}) = \frac 1 {2 \sqrt{2\pi}} \ln \frac n 2 + O(1).$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.