en>Gryllida: /* Algorithm */ formatting

2013-10-25T03:54:11Z

Algorithm: formatting

New page

In [[mathematics]], '''Doob's martingale inequality''' is a result in the study of [[stochastic processes]]. It gives a bound on the probability that a stochastic process exceeds any given value over a given interval of time. As the name suggests, the result is usually given in the case that the process is a non-negative [[Martingale (probability theory)|martingale]], but the result is also valid for non-negative submartingales.

The inequality is due to the American mathematician [[Joseph L. Doob]].

==Statement of the inequality==
Let ''X'' be a submartingale taking non-negative real values, either in discrete or continuous time. That is, for all times ''s'' and ''t'' with ''s'' < ''t'',

:<math>\mathbf{E} \left[ X_{t} \big| \mathcal{F}_{s} \right] \geq X_{s}.</math>

(For a continuous-time submartingale, assume further that the process is [[càdlàg]].) Then, for any constant ''C'' > 0 and ''p'' ≥ 1,

:<math>\mathbf{P} \left[ \sup_{0 \leq t \leq T} X_{t} \geq C \right] \leq \frac{\mathbf{E} \left[ X_{T}^{p} \right]}{C^{p}}.</math>

In the above, as is conventional, '''P''' denotes the [[probability measure]] on the sample space Ω of the stochastic process

:<math>X : [0, T] \times \Omega \to [0, + \infty)</math>

and '''E''' denotes the [[expected value]] with respect to the probability measure '''P''', i.e. the integral

:<math>\mathbf{E}[X_T] = \int_{\Omega} X_{T} (\omega) \, \mathrm{d} \mathbf{P} (\omega)</math>

in the sense of [[Lebesgue integration]]. <math>\mathcal{F}_{s}</math> denotes the [[sigma algebra|σ-algebra]] generated by all the [[random variable]]s ''Xi'' with ''i'' ≤ ''s''; the collection of such σ-algebras forms a [[filtration (abstract algebra)|filtration]] of the probability space.

==Further inequalities==
There are further (sub)martingale inequalities also due to Doob. With the same assumptions on ''X'' as above, let

:<math>S_{t} = \sup_{0 \leq s \leq t} X_{s},</math>

and for ''p'' ≥ 1 let

:<math>\| X_{t} \|_{p} = \| X_{t} \|_{L^{p} (\Omega, \mathcal{F}, \mathbf{P})} = \left( \mathbf{E} \left[ | X_{t} |^{p} \right] \right)^{\frac{1}{p}}.</math>

In this notation, Doob's inequality as stated above reads

:<math>\mathbf{P} \left[ S_{T} \geq C \right] \leq \frac{\| X_{T} \|_{p}^{p}}{C^{p}}.</math>

The following inequalities also hold: for ''p'' = 1,

:<math>\| S_{T} \|_{p} \leq \frac{e}{e - 1} \left( 1 + \| X_{T} \log X_{T} \|_{p} \right)</math>

and, for ''p'' > 1,

:<math>\| X_{T} \|_{p} \leq \| S_{T} \|_{p} \leq \frac{p}{p-1} \| X_{T} \|_{p}.</math>

==Related inequalities==
Doob's inequality for discrete-time martingales implies [[Kolmogorov's inequality]]: if ''X''1, ''X''2, ... is a sequence of real-valued [[independent random variables]], each with mean zero, it is clear that

:<math>\begin{align}
\mathbf{E} \left[ X_{1} + \dots + X_{n} + X_{n + 1} \big| X_{1}, \dots, X_{n} \right] &= X_{1} + \dots + X_{n} + \mathbf{E} \left[ X_{n + 1} \big| X_{1}, \dots, X_{n} \right] \\
&= X_{1} + \cdots + X_{n},
\end{align}</math>

so ''Mn'' = ''X''1 + ... + ''Xn'' is a martingale. Note that [[Jensen's inequality]] implies that |''Mn''| is a nonnegative submartingale if ''Mn'' is a martingale. Hence, taking ''p'' = 2 in Doob's martingale inequality,

:<math>\mathbf{P} \left[ \max_{1 \leq i \leq n} \left| M_{i} \right| \geq \lambda \right] \leq \frac{\mathbf{E} \left[ M_{n}^{2} \right]}{\lambda^{2}},</math>

which is precisely the statement of Kolmogorov's inequality.

==Application: Brownian motion==
Let ''B'' denote canonical one-dimensional [[Brownian motion]]. Then

:<math>\mathbf{P} \left[ \sup_{0 \leq t \leq T} B_{t} \geq C \right] \leq \exp \left( - \frac{C^2}{2T} \right).</math>

The proof is just as follows: since the exponential function is monotonically increasing, for any non-negative λ,

:<math>\left\{ \sup_{0 \leq t \leq T} B_{t} \geq C \right\} = \left\{ \sup_{0 \leq t \leq T} \exp ( \lambda B_{t} ) \geq \exp ( \lambda C ) \right\}.</math>

By Doob's inequality, and since the exponential of Brownian motion is a positive submartingale,

:<math>\begin{align}
\mathbf{P} \left[ \sup_{0 \leq t \leq T} B_{t} \geq C \right] & = \mathbf{P} \left[ \sup_{0 \leq t \leq T} \exp ( \lambda B_{t} ) \geq \exp ( \lambda C ) \right] \\
& \leq \frac{\mathbf{E} \left[ \exp (\lambda B_{T}) \right ]}{\exp (\lambda C)} \\
& = \exp \left( \tfrac{1}{2}\lambda^{2}T - \lambda C \right) && \mathbf{E} \left[ \exp (\lambda B_{t}) \right] = \exp \left( \tfrac{1}{2}\lambda^{2} t \right)
\end{align}</math>

Since the left-hand side does not depend on λ, choose λ to minimize the right-hand side: λ = ''C''/''T'' gives the desired inequality.

==References==
* {{cite book | author=Revuz, Daniel and Yor, Marc | title=Continuous martingales and Brownian motion | edition=Third | publisher=Springer| location=Berlin | year=1999 | isbn=3-540-64325-7}} (Theorem II.1.7)
* {{springer|id=M/m062570|title=Martingale|author=[[Albert Shiryaev|Shiryaev, Albert N.]]}}

{{Stochastic processes}}

[[Category:Probabilistic inequalities]]
[[Category:Statistical inequalities]]
[[Category:Martingale theory]]

Incomplete Cholesky factorization - Revision history

en>Gryllida: /* Algorithm */ formatting