# How to limit the probability that a Martingale crosses a given threshold in any given time?

I'm working on the following problem for my first Stochastic Processes course.

Let $(S_n)_{n \in \mathbb{N}}$ be a random walk starting at $0$ with independent increments $X_n$ that satisfy $\mathbb{E}\big(e^{\delta X_n}\big) = 1, \forall n$ and $\delta > 0$. Show that $\mathbb{P}(S_n > a \text{ for some$n$}) \leq e^{-\delta a}$, where $a > 0$.

I'm having a lot of trouble with the "for some $n$" part. For example, I am able to prove the following: pick any $n$. Now, notice that,

$\{S_n > a\} \iff \{e^{\delta S_n} >e^{\delta a} \}$

From Markov's inequality, it follows that

$\mathbb{P}(e^{\delta S_n} >e^{\delta a}) \leq \frac{1}{e^{\delta a}}$

because $\mathbb{E}(e^{\delta S_n}) = 1$. Hence, $\mathbb{P}(S_n \geq a) \leq e^{-\delta a}$

However, this is not the required result. This was proved for a given $n$. Is there a way to adapt the argument and prove the correct statement. Also, it can be the case in which the professor messed up things with a typo or so on, I don't know. Any ideas on how to follow from here? Thanks in advance!!

• Have you thought about using Borel-Cantelli? I haven’t thought about it much, but this problem has the feel of one where B-C might be useful. – Theoretical Economist Aug 28 '18 at 21:08

a) Proving that $e^{\delta S_n}$ is a martingale.
b) Using Doob's martingale inequality, which states that $P(X_k \geq a$ for some k$\in [n]) \leq \frac{\mathbb{E}(X_n)^+}{a}$ for a submartingale. (where the $(f(x))^+ = \max(0,f(x))$, but in your case since your martingale is non-negative it does not matter.)
c) Now, the right hand side does not depend on $n$, so you should be able to take the limit with dominated convergence theorem.
(You can prove Doob's martingale inequality by using a stopping time where you check when your process exceeds $a$ or reaches time $n$.)