Martingale (probability theory)

	Email		Print
	Bookmark		Link

Martingale (probability theory)

In probability theory

Probability theory

Probability theory is the branch of mathematics concerned with analysis of Statistical randomness phenomena. The central objects of probability theory are random variables, stochastic processes, and event s: mathematical abstractions of determinism events or measured quantities that may either be single occurrences or evolve over time in an a...
, a martingale is a stochastic process

Stochastic process

Sequence

In mathematics, a sequence is an ordered list of objects . Like a Set , it contains Element , and the number of terms is called the length of the sequence....
of random variable

Random variable

In mathematics, random variables are used in the study of Randomness and probability. They were developed to assist in the analysis of Game of chance, stochastic events, and the results of experiment by capturing only the mathematical properties necessary to answer probability questions....
s) such that the conditional expected value of an observation at some time t, given all the observations up to some earlier time s, is equal to the observation at that earlier time s.

Discussion

Ask a question about 'Martingale (probability theory)'

Start a new discussion about 'Martingale (probability theory)'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In probability theory

Probability theory

Stochastic process

Sequence

In mathematics, a sequence is an ordered list of objects . Like a Set , it contains Element , and the number of terms is called the length of the sequence....
of random variable

Random variable

History

Originally, martingale
Martingale (betting system)

Originally, martingale referred to a class of betting strategy popular in 18th-century France. The simplest of these strategies was designed for a game in which the gambler wins his stake if a coin comes up heads and loses it if the coin comes up tails....
referred to a class of betting strategies

Betting strategy

A betting strategy or betting system is a structured approach to gambling intended to counter the inherent bias held by the house in casino and card games and by bookmakers in horseracing and sports betting....
that was popular in 18th century France

France

France , officially the French Republic , is a country whose Metropolitan France is located in Western Europe and that also comprises various Overseas departments and territories of France....
. The simplest of these strategies was designed for a game in which the gambler wins his stake if a coin comes up heads and loses it if the coin comes up tails. The strategy had the gambler double his bet after every loss so that the first win would recover all previous losses plus win a profit equal to the original stake. As the gambler's wealth and available time jointly approach infinity, his probability of eventually flipping heads approaches 1, which makes the martingale betting strategy seem like a sure thing

Almost surely

In probability theory, one says that an event happens almost surely if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory....
. However, the exponential growth

Exponential growth

Exponential growth occurs when the growth rate of a mathematical function is proportionality to the function's current value. In the case of a discrete domain of definition with equal intervals it is also called geometric growth or geometric decay ....
of the bets eventually bankrupts its users.

The concept of martingale in probability theory was introduced by Paul Pierre Lévy

Paul Pierre Lévy

Paul Pierre L?vy was a France mathematician who was active especially in probability theory, introducing martingale s and L?vy flights. L?vy processes, L?vy measures, L?vy's constant, the L?vy distribution, the L?vy skew alpha-stable distribution, the L?vy area and the fractal L?vy C curve are also named after him....
, and much of the original development of the theory was done by Joseph Leo Doob

Joseph Leo Doob

Joseph Leo Doob was an United States of America mathematician, specializing in Mathematical analysis and probability theory.The theory of Martingale s was developed by Doob....
. Part of the motivation for that work was to show the impossibility of successful betting strategies.

Definitions

A discrete-time martingale is a discrete-time

Discrete time

Discrete time is non-continuous time. Sampling at non-continuous times results in discrete-time samples. For example, a newspaper may report the price of crude oil once every 24 hours....
stochastic process

Stochastic process

Sequence

In mathematics, a sequence is an ordered list of objects . Like a Set , it contains Element , and the number of terms is called the length of the sequence....
of random variable

Random variable

In mathematics, random variables are used in the study of Randomness and probability. They were developed to assist in the analysis of Game of chance, stochastic events, and the results of experiment by capturing only the mathematical properties necessary to answer probability questions....
s) X₁, X₂, X₃, ... that satisfies for all n

i.e., the conditional expected value

Expected value

In probability theory and statistics, the expected value of a random variable is the Lebesgue integral of the random variable with respect to its probability measure....
of the next observation, given all the past observations, is equal to the last observation.

Somewhat more generally, a sequence Y₁, Y₂, Y₃ ... is said to be a martingale with respect to another sequence X₁, X₂, X₃ ... if for all n

The sequence Xi is sometimes known as the filtration.

Similarly, a continuous-time martingale with respect to the stochastic process

Stochastic process

A stochastic process, or sometimes random process, is the counterpart to a deterministic process in probability theory. Instead of dealing with only one possible 'reality' of how the process might evolve under time , in a stochastic or random process there is some indeterminacy in its future evolution described by probability distribu...
Y_t such that for all t

This expresses the property that the conditional expectation of an observation at time t, given all the observations up to time , is equal to the observation at time s (of course, provided that s = t).

In full generality, a stochastic process Y : T × O ? S is a martingale with respect to a filtration S_* and probability measure P if

S_* is a filtration
Filtration (abstract algebra)

In mathematics, a filtration is an indexed set Si of subobjects of a given algebraic structure S, with the index i running over some index set I that is a totally ordered set, subject to the condition that if i ≤ j in I then Si ⊆ Sj....
of the underlying probability space
Probability space

A probability space, in probability theory, is the conventional mathematical model of randomness. This mathematical object, sometimes called also probability triple, formalizes three interrelated ideas by three mathematical notions....
(O, S, P);
Y is adapted
Adapted process

In the study of stochastic processes, an adapted process is one that cannot "see into the future". An informal interpretation is that X is adapted if and only if, for every realisation and every n, Xn is known at time n....
to the filtration S_*, i.e., for each t in the index set
Index set

In mathematics, the elements of a Set A may be indexed or labeled by means of a set J that is on that account called an index set....
T, the random variable Y_t is a S_t-measurable function
Measurable function

In mathematics, measurable functions are well-behaved function s between sigma-algebra. Functions studied in mathematical analysis that are not measurable are generally considered Pathological ....
;
for each t, Y_t lies in the L^p space
Lp space

In mathematics, the Lp and lp spaces are spaces of p-integrable function, and corresponding sequence spaces....
L¹(O, S_t, P; S), i.e.

for all s and t with s < t and all F ? S_s,

where χ_F denotes the indicator function

Indicator function

In mathematics, an indicator function or a characteristic function is a Function defined on a Set that indicates membership of an element in a subset of ....
of the event F. In Grimmett and Stirzaker's Probability and Random Processes, this last condition is denoted as

which is a general form of conditional expectation

Conditional expectation

In probability theory, a conditional expectation is the expected value of a real random variable with respect to a conditional probability probability distribution....
.

It is important to note that the property of being a martingale involves both the filtration and the probability measure (with respect to which the expectations are taken). It is possible that Y could be a martingale with respect to one measure but not another one; the Girsanov theorem

Girsanov theorem

In probability theory, the Girsanov theorem tells how stochastic processes change under changes in measure . The theorem is especially important in the theory of financial mathematics as it tells how to convert from the physical measure which describes the probability that an underlying instrument will take a particular value or values to t...
offers a way to find a measure with respect to which an Ito process is a martingale.

Examples of martingales

Suppose X_n is a gambler's fortune after n tosses of a "fair" coin, where the gambler wins $1 if the coin comes up heads and loses $1 if the coin comes up tails. The gambler's conditional expected fortune after the next trial, given the history, is equal to his present fortune, so this sequence is a martingale. This is also known as D'Alembert system.

Let Y_n = X_n² − n where X_n is the gambler's fortune from the preceding example. Then the sequence is a martingale. This can be used to show that the gambler's total gain or loss varies roughly between plus or minus the square root
Square root

In mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x....
of the number of steps.

(de Moivre's
Abraham de Moivre

Abraham de Moivre was a France mathematician famous for de Moivre's formula, which links complex numbers and trigonometry, and for his work on the normal distribution and probability theory....
martingale) Now suppose an "unfair" or "biased" coin, with probability p of "heads" and probability q = 1 − p of "tails". Let

with "+" in case of "heads" and "−" in case of "tails". Let

Then is a martingale with respect to .

(Polya's
George Pólya

George P?lya was a Hungary mathematician....
urn) An urn initially contains r red and b blue marbles. One is chosen randomly. Then it is put back in the urn along with another marble of the same colour. Let X_n be the number of red marbles in the urn after n iteration
Iterative method

In computational mathematics, an iterative method attempts to solve a problem by finding successive approximations to the solution starting from an initial guess....
s of this procedure, and let Y_n = X_n/(n + r + b). Then the sequence is a martingale.

(Likelihood-ratio test
Likelihood-ratio test

The likelihood ratio, often denoted by , is the ratio of the maximum probability of a result under two different hypotheses. A likelihood-ratio test is a statistical test for making a decision between two hypotheses based on the value of this ratio....
ing in statistics
Statistics

Statistics is a Mathematics pertaining to the collection, analysis, interpretation or explanation, and presentation of data. It also provides tools for prediction and forecasting based on data....
) A population is thought to be distributed according to either a probability density f or another probability density g. A random sample
Random sample

A sample is a subject chosen from a population for investigation. A random sample is one chosen by a method involving an unpredictable component....
is taken, the data being X₁, ..., X_n. Let Y_n be the "likelihood ratio"

. If the population is actually distributed according to the density f rather than according to g, then is a martingale with respect to .

Suppose each amoeba either splits into two amoebas, with probability p, or eventually dies, with probability 1 − p. Let X_n be the number of amoebas surviving in the nth generation (in particular X_n = 0 if the population has become extinct by that time). Let r be the probability of eventual extinction. (Finding r as function of p is an instructive exercise. Hint: The probability that the descendants of an amoeba eventually die out is equal to the probability that either of its immediate offspring dies out, given that the original amoeba has split.) Then

is a martingale with respect to .

The number of individuals of any particular species in an ecosystem of fixed size is a function of (discrete) time, and may be viewed as a sequence of random variables. This sequence is a martingale under the unified neutral theory of biodiversity
Unified neutral theory of biodiversity

The unified neutral theory of biodiversity and biogeography is a theory and the title of a monograph by ecology Stephen Hubbell. The theory aims to explain the diversity and relative abundance of species in ecological communities, although like other neutral theory of ecology, Hubbell's theory assumes that the differences between members of...
.

If is a Poisson process
Poisson process

A Poisson process, named after the French mathematician Sim?on-Denis Poisson , is the stochastic process in which events occur continuously and memorylessness ....
with intensity ?, then the Compensated Poisson process is a continuous-time martingale with right-continuous/left-limit
Classification of discontinuities

Continuous functions are of utmost importance in mathematics and applications. However, not all function are continuous. If a function is not continuous at a point in its domain , one says that it has a discontinuity there....
sample paths.

An example martingale series can easily be produced with Microsoft's Excel program or similar spreadsheet software. Enter 0.0 in the A1 (top left) cell, and in the cell below it (A2) enter =a$1+NORMINV(RAND,0,1). Now copy that cell by dragging and create 300 or so copies. This will create a martingale series with a mean of 0 and standard deviation of 1. (The $ in "a$1" locks cell 1 so when you drag down it always refers to the top cell). With the cells still highlighted go to the chart creation tool and create a chart of these values. Now every time a recalculation happens (in Excel the F9 key does this) the chart will display another martingale series.

Martingales and stopping times

A stopping time with respect to a sequence of random variables X₁, X₂, X₃, ... is a random variable t with the property that for each t, the occurrence or non-occurrence of the event t = t depends only on the values of X₁, X₂, X₃, ..., X_t. The intuition behind the definition is that at any particular time t, you can look at the sequence so far and tell if it is time to stop. An example in real life might be the time at which a gambler leaves the gambling table, which might be a function of his previous winnings (for example, he might leave only when he goes broke), but he can't choose to go or stay based on the outcome of games that haven't been played yet.

Some mathematician

Mathematician

A mathematician is a person whose primary area of study and/or research is the field of mathematics....
s defined the concept of stopping time by requiring only that the occurrence or non-occurrence of the event t = t be probabilistically independent

Statistical independence

In probability theory, to say that two event s are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other occurs....
of X_t + 1, X_t + 2, ... but not that it be completely determined by the history of the process up to time t. That is a weaker condition than the one appearing in the paragraph above, but is strong enough to serve in some of the proofs in which stopping times are used.

The optional stopping theorem (or optional sampling theorem) says that, under certain conditions, the expected value of a martingale at a stopping time is equal to its initial value. We can use it, for example, to prove the impossibility of successful betting strategies for a gambler with a finite lifetime and a house limit on bets.

Submartingales and supermartingales

A (discrete-time) submartingale is a sequence of integrable

Integrable function

In mathematics, an integrable function is a function whose integral exists. Unless specifically stated, the integral in question is usually the Lebesgue integral....
random variables satisfying

Analogously a (discrete-time) supermartingale satisfies

The more general definitions of both discrete-time and continuous-time martingales given earlier can be converted into the corresponding definitions of sub/supermartingales in the same way by replacing the equality for the conditional expectation by an inequality.

Here is a mnemonic for remembering which is which: "Life is a supermartingale; as time advances, expectation decreases."

Examples of submartingales and supermartingales

Every martingale is also a submartingale and a supermartingale. Conversely, any stochastic process that is both a submartingale and a supermartingale is a martingale.
Consider again the gambler who wins $1 when a coin comes up heads and loses $1 when the coin comes up tails. Suppose now that the coin may be biased, so that it comes up heads with probability p.

If p is equal to 1/2, the gambler on average neither wins nor loses money, and the gambler's fortune over time is a martingale.
If p is less than 1/2, the gambler loses money on average, and the gambler's fortune over time is a supermartingale.
If p is greater than 1/2, the gambler wins money on average, and the gambler's fortune over time is a submartingale.

A convex function
Convex function

In mathematics, a real-valued function f defined on an interval is called convex, concave upwards, concave up or convex cup, if for any two points x and y in its domain C and any t in [0,1], we have...
of a martingale is a submartingale, by Jensen's inequality
Jensen's inequality

In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function....
. For example, the square of the gambler's fortune in the fair coin game is a submartingale (which also follows from the fact that X_n² − n is a martingale). Similarly, a concave function
Concave function

In mathematics, a concave function is the additive inverse of a convex function. A concave function is also synonymously called concave downwards, concave down, convex cap or upper convex....
of a martingale is a supermartingale.

A more general definition

One can define a martingale which is an uncountable family of random variables. Also, those random variables may take values in a more general space than just the real numbers.

Let be a directed set

Directed set

In mathematics, a directed set is a nonempty Set A together with a reflexive relation and transitive relation binary relation = , with the additional property that every pair of elements has an upper bound....
, be a real topological vector space

Topological vector space

In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. As the name suggests the space blends a topology with the algebraic concept of a vector space....
, and its topological dual

Dual pair

In functional analysis and related areas of mathematics a dual pair or dual system is a pair of vector spaces with an associated bilinear form....
(denote by this duality). Moreover, let be a filtered probability space

Probability space

A probability space, in probability theory, is the conventional mathematical model of randomness. This mathematical object, sometimes called also probability triple, formalizes three interrelated ideas by three mathematical notions....
, that is a probability space equipped with a family of sigma-algebras with the following property: for each with , one has .

A family of random variables :

is called a martingale if for each and with , the three following properties are satisfied:

is -measurable.

If the directed set is a real interval (or the whole real axis, or a semiaxis) then a martingale is called a continuous time martingale. If is the set of natural numbers it is called a discrete time martingale.

Martingale (probability theory)

History

Definitions

Examples of martingales

Martingales and stopping times

Submartingales and supermartingales

Examples of submartingales and supermartingales

A more general definition

See also