In probability theory, a (discrete-time) martingale is a discrete-time stochastic process (i.e., a sequence of random variables) X₁, X₂, X₃, ... that satisfies the identity Probability theory is the mathematical study of probability. ... Discrete time is non-continuous time. ... In the mathematics of probability, a stochastic process is a random function. ... This is a page about mathematics. ... A random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. ... In syntax, the concept of restrictiveness applies to a variety of syntactical constructions. ...

i.e., the conditional expected value of the next observation, given all of the past observations, is equal to the last observation. As is frequent in probability theory, the term was adopted from the language of gambling. In probability theory (and especially gambling), the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects to win per bet if bets with identical... Gambling (or betting) is any behavior involving risking money or property (making a wager or placing a stake) on the outcome of a game, contest, or other event in which the outcome of that activity depends partially or totally upon chance or upon ones ability to do something. ...

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

for every n.

A continuous-time martingale is a zero-drift stochastic process. That is, a random variable θ follows a continuous-time martingale iff Continuous time occurs when time is sampled continuously. ... In the mathematics of probability, a stochastic process is a random function. ... A random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. ... Continuous time occurs when time is sampled continuously. ... ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P...

where dz is a Wiener process and the variable σ is a constant or a stochastic process that may depend on θ or other stochastic variables. In mathematics, the Wiener process, so named in honor of Norbert Wiener, is a continuous-time Gaussian stochastic process with independent increments used in modelling Brownian motion and some random phenomena observed in finance. ...

History

Originally, martingale referred to a class of betting strategies 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. 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. Since as a gambler's wealth and available time jointly approach infinity his probability of eventually flipping heads approaches 1, the martingale betting strategy was seen as a sure thing by those who practiced it. Of course in reality the exponential growth of the bets would quickly bankrupt those foolish enough to use the martingale after even a moderately long run of bad luck. A separate article treats the topic of martingales in probability theory. ... Betting strategies or betting systems are approaches to gambling intended to increase the odds of winning. ... (17th century - 18th century - 19th century - more centuries) As a means of recording the passage of time, the 18th century refers to the century that lasted from 1701 through 1800. ... In mathematics—specifically, in probability theory—the phrase almost surely is a subtle, precise way to say that something is certain except for cases that almost never happen, though still possible. ... In mathematics, a quantity that grows exponentially is one that grows at a rate proportional to its size. ...

The concept of martingale in probability theory was introduced by Paul Pierre Lévy, and much of the original development of the theory was done by Joseph Leo Doob. Part of the motivation for that work was to show the impossibility of successful betting strategies. Paul Pierre Lévy (September 15, 1886 - December 15, 1971) was a French mathematician who was active especially in probability theory, introduced martingales and Lévy flights. ... Joseph Leo Doob (February 27, 1910-June 7, 2004) was an American mathematician, specializing in analysis and probability theory. ...

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 { Y_n : n = 1, 2, 3, ... } is a martingale. This can be used to show that the gambler's total gain or loss grows roughly as the square root of the number of steps.

• (de Moivre's 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 { Y_n : n = 1, 2, 3, ... } is a martingale with respect to { X_n : n = 1, 2, 3, ... }.

• Let Y_n = P(A | X₁, ..., X_n). Then { Y_n : n = 1, 2, 3, ... } is a martingale with respect to { X_n : n = 1, 2, 3, ... }.

• (Polya's urn) An urn initially contains r red and b blue marbles. One is chosen randomly. Then it is put back together with another one of the same colour. Let X_n be the number of red marbles in the urn after n iterations of this procedure, and let Y_n = X_n/(n+r+b). Then the sequence { Y_n : n = 1, 2, 3, ... } is a martingale.

• (Likelihood-ratio testing in statistics) A population is thought to be distributed according to either a probability density f or another probability density g. A random sample is taken, the data being X₁, ..., X_n. Let Y_n be the "likelihood ratio"

(which, in applications, would be used as a test statistic). If the population is actually distributed according to the density f rather than according to g, then { Y_n : n = 1, 2, 3, ... } is a martingale with respect to { X_n : n = 1, 2, 3, ... }.

• 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 { X_n: n = 1, 2, 3, ... }.

• 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.

The basic meaning of gamblers ruin is a gamblers loss of the last of his bank of gambling money and consequent inability to continue gambling. ... In mathematics, the principal square root of a non-negative real number is denoted and represents the non-negative real number whose square (the result of multiplying the number by itself) is For example, since This example suggests how square roots can arise when solving quadratic equations such as or... Abraham de Moivre Abraham de Moivre (May 26, 1667 in Vitry-le-François, Champagne, France – November 27, 1754 in London, England) was a French mathematician famous for de Moivres formula, which links complex numbers and trigonometry, and for his work on the normal distribution and probability theory. ... George Pólya (December 13, 1887 - September 7, 1985, in Hungarian Pólya György) was an American mathematician of Hungarian origin. ... An iterative method attempts to solve a problem (for example an equation or system of equations) by finding successive approximations to the solution starting from an initial guess. ... A likelihood-ratio test is a statistical test relying on a test statistic computed by taking the ratio of the maximum value of the likelihood function under the constraint of the null hypothesis to the maximum with that constraint relaxed. ... Statistics is a broad mathematical discipline which studies ways to collect, summarize and draw conclusions from data. ... It has been suggested that this article or section be merged with Simple random sample. ... The Galton-Watson process is a stochastic process arising from Francis Galtons statistical investigation of the extinction of surnames. ... The unified neutral theory of biodiversity and biogeography (here Unified Theory or UNTB) is a theory and the title of a monograph[1] by ecologist Stephen Hubbell. ...

Martingales and stopping times

A stopping time with respect to a sequence of random variables X₁, X₂, ... is a random variable τ with the property that for each t, the occurrence or non-occurrence of the event τ = t depends only on the values of 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 can't choose to go or stay based on the outcome of games that haven't been played yet. A separate article treats the device for fastening horses bridles or dogs collars called a martingale. ...

Some mathematicians defined the concept of stopping time by requiring only that the occurrence or non-occurrence of the event τ = t be probabilistically independent of X_t+1, X_t+2, X_t+3, ...., 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. A mathematician is a person whose area of study and research is mathematics. ... In probability theory, to say that two events are independent intuitively means that knowing whether or not one of them occurs makes it neither more probable nor less probable that the other occurs. ... Look up Up to on Wiktionary, the free dictionary In mathematics, the phrase up to xxxx indicates that members of an equivalence class are to be regarded as a single entity for some purpose. ...

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. One version of the theorem is given below:

Let X₁, X₂, ... be a martingale and τ a stopping time with respect to X₁, X₂, .... If (a) Pr[τ < ∞] = 1, (b) E[τ] < ∞, and (c) there exists a constant c such that |X_i+1 − X_i| ≤ c for all i; then E[X_τ] = E[X₁].

Some applications of the theorem: A mathematical constant is a quantity, usually a real number or a complex number, that arises naturally in mathematics and does not change. ...

• We can use it to prove the impossibility of successful betting strategies for a gambler with a finite lifetime (which gives conditions (a) and (b)) and a house limit on bets (condition (c)). Suppose that the gambler can wager up to c dollars on a fair coin flip at times 1, 2, 3, etc., winning his wager if the coin comes up heads and losing it if the coin comes up tails. Suppose further that he can quit whenever he likes, but cannot predict the outcome of gambles that haven't happened yet. Then the gambler's fortune over time is a martingale, and the time τ at which he decides to quit (or goes broke and is forced to quit) is a stopping time. So the theorem says that E[X_τ] = E[X₁]. In other words, the gambler leaves with the same amount of money on average as when he started.

• Suppose we have a random walk that goes up or down by one with equal probability on each step. Suppose further that the walk stops if it reaches 0 or m; the time at which this first occurs is a stopping time. If we happen to know that the expected time that the walk ends is finite (say, from Markov chain theory), the optional stopping theorem tells us that the expected position when we stop is equal to the initial position a. Solving a = pm + (1−p)0 for the probability p that we reach m before 0 gives p = a/m.

• Now consider a random walk that starts at 0 and stops if we reach −m or +m, and use the Y_n = X_n² − n martingale from the examples section. If τ is the time at which we first reach ±m, then 0 = E[Y₁] = E[Y_τ] = m²  − E[τ]. We immediately get E[τ] = m².

In mathematics and physics, a random walk is a formalization of the intuitive idea of taking successive steps, each in a random direction. ... In mathematics, a (discrete-time) Markov chain, named after Andrei Markov, is a discrete-time stochastic process with the Markov property. ...

Submartingales and supermartingales

A submartingale is like a martingale, except that the current value of the random variable is always less than or equal to the expected future value. Formally, this means

Similarly, in a supermartingale, the current value is always greater than or equal to the expected future value:

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 of a martingale is a submartingale, by Jensen's inequality. 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 of a martingale is a supermartingale.

A convex function is a real-valued function f defined on an interval (or on any convex subset C of some vector space), if for any two points x and y in its domain C and any t in [0,1], we have Convex function on interval I.e. ... In mathematics, Jensens 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. ... In geometry, concavity is a property of certain geometric figures, and in calculus, a property of certain graphs of functions. ...

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, V be a real topological vector space, and its topological dual (denote by this duality). Moreover, let be a filtered probability space, that is a probability space equipped with a family of sigma-algebras with the following property: for each with , one has . In mathematics, a directed set is a set A together with a binary relation ≤ having the following properties: a ≤ a for all a in A (reflexivity) if a ≤ b and b ≤ c, then a ≤ c (transitivity) for any two a and b in A, there exists a c in A... In mathematics, a topological vector space X is a real or complex vector space which is endowed with a Hausdorff topology such that vector addition X × X → X and scalar multiplication K × X → X are continuous (where the product topologies are used and the base field K carries its standard... 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. ... In mathematics, a probability space or probability measure is a set S, together with a σ-algebra X on S and a measure P on that σ-algebra such that P(S) = 1. ... In mathematics, a σ-algebra (or σ-field) X over a set S is a family of subsets of S which is closed under countable set operations; σ-algebras are mainly used in order to define measures on S. The concept is important in mathematical analysis and probability theory. ...

A family of random variables : A random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. ...

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

• is -measurable.

• .

• .

If the directed is a real interval (or the whole real axis, or a semiaxis) then a martingale is called a continuos time martingale. If is the set of natural number is called a discrete time martingale. In mathematics, a measure is a function that assigns a number, e. ...

See also

• Azuma's inequality

In probability theory, Azumas inequality gives a concentration result for the values of martingales that have bounded differences. ...

References

• David Williams, Probability with Martingales, Cambridge University Press, 1991, ISBN 0521406056