Here is a question on martingales (given after third graduate lecture on the subject).
Let $X_n$ a martingale with respect to the natural filtration and such that $X_0 = 0$, assume that $\frac{1}{2} \leq |X_{n+1} - X_n| \leq 1$. Show that there exists $c,C >0$ so that $$ \frac{c}{\sqrt{n}} \leq P(X_1 \geq 0, \ldots, X_n \geq 0 ) \leq \frac{C}{\sqrt{n}} $$
I was not able to solve this question. So far I had no clues except a very vague intuition that I try to outline below. Any comments are welcome.
I try to use the following two intuitions:
- Appearance of $\sqrt{n}$ might suggest a Central Limit Theorem.
- If $S_n$ is a simple random walk, then using reflection principle one can show that $P(S_1 \geq 0, \ldots, S_{2n} \geq 0 )$ is proportional to $P(S_{2n} = 0)$.
So for the problem at hand,
$$P(X_1 \geq 0, \ldots, X_n \geq 0 ) = P(\max\limits_{k\leq n} (-X_k) = 0)$$
suppose, there is some correspondence of $ P(\max\limits_{k\leq n} (-X_n) = 0 )$ to $P((-X_n) = 0 )$. So I look at $P((-X_n) = 0)$.
Now, let $\xi := x_{i+1} - x_i$ then $P(X_n = 0)= P\left(\sum_{1}^{n} \xi_i = 0\right) $ by our assumpotion $\xi_i$ are bounded, suppose there is CLT taking place, then for large $n$
$$X_n = \sum_{i=1}^{n} \xi_i \sim N\left(0, \sum_{i=1}^{n} \mathbb{E}\xi^2_i\right)$$
which implies
$$P\left(\sum_{i=1}^{n} \xi_i \in [-\varepsilon, \varepsilon]\right) \propto \frac{1}{\sqrt{n}}$$