Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $x$ be a positive number and $X_n$ be real-valued submartingale such that $X_0 = x$. I am interested in upper bounds on probability $$ \psi(x) = \mathsf{P}_x\left\{\inf\limits_{n\geq 0}X_n \leq 0\right\}. $$

You are welcome to discuss this question with any assumptions you like - maybe, not too strict.

One of my ideas was the following. If $Y_n = \frac{1}{X_n}$ is a supermartingale, then Doob's inequality can be used: $$ \mathsf{P}_y\left\{\sup\limits_{n\geq 0}Y_n \geq N\right\}\leq \frac{y}{N}, $$ but here we need to have $Y$ a non-negative process, which is not our case.

Edited: The formulation of Doob's inequality [Shiryaev: Probability, p. 492]. If $Z$ is a supermartingale then $$ \mathsf P\{\sup\limits_{n\geq 0} |Z_n|\geq \delta\}\leq\frac{C}{\delta}\sup\limits_{n\geq 0} \mathsf E[|Z_n|] $$ for some $C\leq 3$.

If $Z$ is a non-negative supermartingale then $C$ can be taken equal to $1$ and the expectation on the right-hand side attains its maximum at the time moment $n=0$. That leads to the inequality I've formulated in the first version of the question.

With regards to random walks: I am not quite sure in you statement since for the Lundberg inequality there exists such a bound. More precisely, if random walk is given by $$ X_n = X_{n-1}+A_n $$ where $A_n$ are i.i.d. such that $\mathsf E A_n >0$ and there exists $r>0$ such that $\mathsf E\mathrm e^{-rA_1} = 1$, then $\psi(x)\leq \mathrm e^{-rx}$.

I've just eventually faced such inequality from Financial Mathematics and wonder if there are known bounds for supermartingales (since $X_n$ is a supermartingale in the latter example) - they have not to be exponential of course.

P.S. I put this question also here:

share|cite|improve this question
For simple random walk the probability is 1, so it seems like your assumptions will need to be fairly specific. – Nate Eldredge Jun 17 '11 at 13:25
Doob's inequality is usually stated for nonnegative sub martingales. You could explain the version of this result you have in mind. – Did Jun 18 '11 at 5:35
@Nate, @Didier: I've replied on your comments by editing the question. – Ilya Jun 18 '11 at 11:36
@Nate Eldredge: which kind of random walk did you mean? – Ilya Jun 20 '11 at 8:18
@Gortaur: Just the symmetric simple random walk on $\mathbb{Z}$, which goes from $n$ to $n+1$ or $n-1$ with probability $1/2$. Of course this does not satisfy the Lundberg conditions since $E A_n = 0$. So I suppose your process should be a "strict" submartingale in some sense. – Nate Eldredge Jun 20 '11 at 19:05
up vote 4 down vote accepted

Ideas coming from Skorokhod embedding theorem may help. Let $U_n=\mathrm{e}^{-rX_n}$ for a given nonnegative $r$ and assume that $(U_n)$ is a supermartingale, that is, that $E(\mathrm{e}^{-rX_{n+1}}|\mathcal{F}_n^X)\le\mathrm{e}^{-rX_n}$ (Dubins and Savage call this condition the existence of an exponential house).

Then $U_0=\mathrm{e}^{-rx}$ and the stopping time theorem applied to the first time when $U_n\ge1$ yields $\psi(x)=P(\sup_nU_n\ge1)\le\mathrm{e}^{-rx}$ for every nonnegative $x$.

This extends the result you mentioned about sums of i.i.d. increments.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.