Doob martingale

A Doob martingale (also known as a Levy martingale) is a mathematical construction of a stochastic process which approximates a given random variable and has the martingale property with respect to the given filtration. It may be thought of as the evolving sequence of best approximations to the random variable based on information accumulated up to a certain time.

When analyzing sums, random walks, or other additive functions of independent random variables, one can often apply the central limit theorem, law of large numbers, Chernoff's inequality, Chebyshev's inequality or similar tools. When analyzing similar objects where the differences are not independent, the main tools are martingales and Azuma's inequality.

Definition

A Doob martingale (named after J. L. Doob)^{[citation needed]} is a generic construction that is always a martingale. Specifically, consider any set of random variables

$\vec{X}=X_1, X_2, ..., X_n$

taking values in a set A for which we are interested in the function $f:A^n \to \Bbb{R}$ and define:

$B_i=E_{X_{i+1},X_{i+2},...,X_{n}}[f(\vec{X})|X_{1},X_{2},...X_{i}]$

where the above expectation is itself a random quantity since the expectation is only taken over

X_{i + 1},X_{i + 2},...,X_n,

and

X₁,X₂,...X_i

are treated as random variables. It is possible to show that B_i is always a martingale regardless of the properties of X_i. Thus if one can bound the differences

| B_{i + 1} − B_i | ,

one can apply Azuma's inequality and show that with high probability $f(\vec{X})$ is concentrated around its expected value

$E[f(\vec{X})]=B_0.$

McDiarmid's inequality

One common way of bounding the differences and applying Azuma's inequality to a Doob martingale is called McDiarmid's inequality.^{[citation needed]} Suppose $X_1, X_2, \dots, X_n$ are independent and assume that f satisfies

$\sup_{x_1,x_2,\dots,x_n, \hat x_i} |f(x_1,x_2,\dots,x_n) - f(x_1,x_2,\dots,x_{i-1},\hat x_i, x_{i+1}, \dots, x_n)| \le c_i \qquad \text{for} \quad 1 \le i \le n \; .$

(In other words, replacing the i-th coordinate x_i by some other value changes the value of f by at most c_i.)

It follows that

$|B_{i+1}-B_i| \le c_i$

and therefore Azuma's inequality yields the following McDiarmid inequalities for any ε > 0:

$\Pr \left\{ f(X_1, X_2, \dots, X_n) - E[f(X_1, X_2, \dots, X_n)] \ge \varepsilon \right\} \le \exp \left( - \frac{2 \varepsilon^2}{\sum_{i=1}^n c_i^2} \right)$

and

$\Pr \left\{ E[f(X_1, X_2, \dots, X_n)] - f(X_1, X_2, \dots, X_n) \ge \varepsilon \right\} \le \exp \left( - \frac{2 \varepsilon^2}{\sum_{i=1}^n c_i^2} \right)$

and

$\Pr \left\{ |E[f(X_1, X_2, \dots, X_n)] - f(X_1, X_2, \dots, X_n)| \ge \varepsilon \right\} \le 2 \exp \left( - \frac{2 \varepsilon^2}{\sum_{i=1}^n c_i^2} \right). \;$

See also

• Markov inequality
• Chebyshev's inequality
• Bernstein inequalities (probability theory)

References

• McDiarmid, Colin (1989). "On the Method of Bounded Differences". Surveys in Combinatorics 141: 148–188. http://www.stats.ox.ac.uk/__data/assets/pdf_file/0009/4113/bdd-diffs89.pdf. 

This probability-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Probabilistic inequalities Statistical inequalities Martingale theory Probability stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем написать курсовую Buyuk ada Chip Lohmiller Look at other dictionaries: Doob — may refer to several things: Joseph Leo Doob, an American mathematician Doob martingale Doob s martingale inequality Doob–Meyer decomposition theorem The Doobie Brothers band A slang for cannabis See also Boob (disambiguation) …   Wikipedia Martingale (probability theory) — For the martingale betting strategy , see martingale (betting system). Stopped Brownian motion is an example of a martingale. It can be used to model an even coin toss betting game with the possibility of bankruptcy. In probability theory, a… …   Wikipedia Doob's martingale convergence theorems — In mathematics specifically, in stochastic analysis Doob s martingale convergence theorems are a collection of results on the long time limits of supermartingales, named after the American mathematician Joseph Leo Doob. Contents 1 Statement of… …   Wikipedia Doob's martingale inequality — 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… …   Wikipedia Doob–Meyer decomposition theorem — The Doob–Meyer decomposition theorem is a theorem in stochastic calculus stating the conditions under which a submartingale may be decomposed in a unique way as the sum of a martingale and a continuous increasing process. It is named for J. L.… …   Wikipedia Martingale (calcul stochastique) — Pour les articles homonymes, voir martingale (homonymie). En calcul stochastique, une martingale désigne un type de processus stochastique, c est à dire un processus aléatoire et dynamique. Ce type de processus X est tel que sa valeur espérée… …   Wikipédia en Français Doob — Joseph Leo Doob (* 27. Februar 1910 in Cincinnati; † 7. Juni 2004 in Urbana (Illinois) ) war ein US amerikanischer Mathematiker, der sich mit Analysis und Wahrscheinlichkeitstheorie (stochastische Prozesse) beschäftigte. Doob zog mit seinen… …   Deutsch Wikipedia Doob decomposition theorem — In the theory of discrete time stochastic processes, a part of the mathematical theory of probability, the Doob decomposition theorem gives a unique decomposition of any submartingale as the sum of a martingale and an increasing predictable… …   Wikipedia Doob-Meyer decomposition theorem — The Doob Meyer decomposition theorem is a theorem in stochastic calculus stating the conditions under which a submartingale may be decomposed in a unique way as the sum of a martingale and a continuous increasing process. It is named for J. L.… …   Wikipedia Joseph Leo Doob — Infobox Scientist name = Joseph Doob image width = 300px caption = Joseph Leo Doob birth date = birth date|1910|2|27|mf=y birth place = Cincinnati, Ohio, U.S. residence = nationality = death date = death date and age|2004|6|7|1910|2|27|mf=y death …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”