7
$\begingroup$

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: https://mathoverflow.net/questions/68509/bounds-for-submartingale

  • 0
    For simple random walk the probability is 1, so it seems like your assumptions will need to be fairly specific.2011-06-17
  • 0
    Doob's inequality is usually stated for nonnegative **sub** martingales. You could explain the version of this result you have in mind.2011-06-18
  • 0
    @Nate, @Didier: I've replied on your comments by editing the question.2011-06-18
  • 0
    @Nate Eldredge: which kind of random walk did you mean?2011-06-20
  • 0
    @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.2011-06-20
  • 0
    @Nate: yes, e.g. $\mathsf E_x[X_1] -x\geq \alpha>0$ for all $x$. Say, "uniform" submartingale.2011-06-22
  • 0
    Doob's inequality in Peskir and Shiryaev is **not** what you write (and for good reasons).2011-06-22
  • 0
    @Didier: could you please tell me where I did a mistake?2011-06-22
  • 0
    I don't know how Doob's inequality is stated in Peskir and Shiryaev, but what you have there is not correct.2011-06-22
  • 0
    E.g., $Z_0=0$. $Z_1$ uniform on $\{-1,0,1\}$. Conditional on $Z_1=0$ let $Z_2$ be uniform on $\{-1,1\}$. Conditional on $Z_1=1$ let $Z_2=1$. Conditional on $Z_1=-1$ let $Z_2=0$. Also let $Z_n=Z_2$ for $n\ge2$. Then, $\sup_n\vert Z_n\vert=1$ almost surely. But $\sup_n\mathbb{E}[\vert Z_n\vert]=5/6$.2011-06-22
  • 0
    @George: thank you for this example - seems that there is a misprint in the book (at least in of the books).2011-06-23
  • 0
    @Didier Piau: Here the misprint was found - http://math.stackexchange.com/questions/47103/doobs-inequality-in-probability. In fact it doesn't influence the first inequality I've written - so I've just corrected the arguments for it. In fact the inequality for non-negative supermartingales can be also derived with an optimal stopping arguments (which I eventually did once independently of the book I quoted - that's why I was surprised about your statement).2011-06-23

1 Answers 1

4

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.