Doob's martingale convergence theorems

(Redirected from Lévy's zero-one law)

In mathematics – specifically, in the theory of stochastic processes – Doob's martingale convergence theorems are a collection of results on the limits of supermartingales, named after the American mathematician Joseph L. Doob.[1] Informally, the martingale convergence theorem typically refers to the result that any supermartingale satisfying a certain boundedness condition must converge. One may think of supermartingales as the random variable analogues of non-increasing sequences; from this perspective, the martingale convergence theorem is a random variable analogue of the monotone convergence theorem, which states that any bounded monotone sequence converges. There are symmetric results for submartingales, which are analogous to non-decreasing sequences.

Statement for discrete-time martingales

edit

A common formulation of the martingale convergence theorem for discrete-time martingales is the following. Let   be a supermartingale. Suppose that the supermartingale is bounded in the sense that

 

where   is the negative part of  , defined by  . Then the sequence converges almost surely to a random variable   with finite expectation.

There is a symmetric statement for submartingales with bounded expectation of the positive part. A supermartingale is a stochastic analogue of a non-increasing sequence, and the condition of the theorem is analogous to the condition in the monotone convergence theorem that the sequence be bounded from below. The condition that the martingale is bounded is essential; for example, an unbiased   random walk is a martingale but does not converge.

As intuition, there are two reasons why a sequence may fail to converge. It may go off to infinity, or it may oscillate. The boundedness condition prevents the former from happening. The latter is impossible by a "gambling" argument. Specifically, consider a stock market game in which at time  , the stock has price  . There is no strategy for buying and selling the stock over time, always holding a non-negative amount of stock, which has positive expected profit in this game. The reason is that at each time the expected change in stock price, given all past information, is at most zero (by definition of a supermartingale). But if the prices were to oscillate without converging, then there would be a strategy with positive expected profit: loosely, buy low and sell high. This argument can be made rigorous to prove the result.

Proof sketch

edit

The proof is simplified by making the (stronger) assumption that the supermartingale is uniformly bounded; that is, there is a constant   such that   always holds. In the event that the sequence   does not converge, then   and   differ. If also the sequence is bounded, then there are some real numbers   and   such that   and the sequence crosses the interval   infinitely often. That is, the sequence is eventually less than  , and at a later time exceeds  , and at an even later time is less than  , and so forth ad infinitum. These periods where the sequence starts below   and later exceeds   are called "upcrossings".

Consider a stock market game in which at time  , one may buy or sell shares of the stock at price  . On the one hand, it can be shown from the definition of a supermartingale that for any   there is no strategy which maintains a non-negative amount of stock and has positive expected profit after playing this game for   steps. On the other hand, if the prices cross a fixed interval   very often, then the following strategy seems to do well: buy the stock when the price drops below  , and sell it when the price exceeds  . Indeed, if   is the number of upcrossings in the sequence by time  , then the profit at time   is at least  : each upcrossing provides at least   profit, and if the last action was a "buy", then in the worst case the buying price was   and the current price is  . But any strategy has expected profit at most  , so necessarily

 

By the monotone convergence theorem for expectations, this means that

 

so the expected number of upcrossings in the whole sequence is finite. It follows that the infinite-crossing event for interval   occurs with probability  . By a union bound over all rational   and  , with probability  , no interval exists which is crossed infinitely often. If for all   there are finitely many upcrossings of interval  , then the limit inferior and limit superior of the sequence must agree, so the sequence must converge. This shows that the martingale converges with probability  .

Failure of convergence in mean

edit

Under the conditions of the martingale convergence theorem given above, it is not necessarily true that the supermartingale   converges in mean (i.e. that  ).

As an example,[2] let   be a   random walk with  . Let   be the first time when  , and let   be the stochastic process defined by  . Then   is a stopping time with respect to the martingale  , so   is also a martingale, referred to as a stopped martingale. In particular,   is a supermartingale which is bounded below, so by the martingale convergence theorem it converges pointwise almost surely to a random variable  . But if   then  , so   is almost surely zero.

This means that  . However,   for every  , since   is a random walk which starts at   and subsequently makes mean-zero moves (alternately, note that   since   is a martingale). Therefore   cannot converge to   in mean. Moreover, if   were to converge in mean to any random variable  , then some subsequence converges to   almost surely. So by the above argument   almost surely, which contradicts convergence in mean.

Statements for the general case

edit

In the following,   will be a filtered probability space where  , and   will be a right-continuous supermartingale with respect to the filtration  ; in other words, for all  ,

 

Doob's first martingale convergence theorem

edit

Doob's first martingale convergence theorem provides a sufficient condition for the random variables   to have a limit as   in a pointwise sense, i.e. for each   in the sample space   individually.

For  , let   and suppose that

 

Then the pointwise limit

 

exists and is finite for  -almost all  .[3]

Doob's second martingale convergence theorem

edit

It is important to note that the convergence in Doob's first martingale convergence theorem is pointwise, not uniform, and is unrelated to convergence in mean square, or indeed in any Lp space. In order to obtain convergence in L1 (i.e., convergence in mean), one requires uniform integrability of the random variables  . By Chebyshev's inequality, convergence in L1 implies convergence in probability and convergence in distribution.

The following are equivalent:

 
  • there exists an integrable random variable   such that   as   both  -almost surely and in  , i.e.
 

Doob's upcrossing inequality

edit

The following result, called Doob's upcrossing inequality or, sometimes, Doob's upcrossing lemma, is used in proving Doob's martingale convergence theorems.[3] A "gambling" argument shows that for uniformly bounded supermartingales, the number of upcrossings is bounded; the upcrossing lemma generalizes this argument to supermartingales with bounded expectation of their negative parts.

Let   be a natural number. Let   be a supermartingale with respect to a filtration  . Let  ,   be two real numbers with  . Define the random variables   so that   is the maximum number of disjoint intervals   with  , such that  . These are called upcrossings with respect to interval  . Then

 

where   is the negative part of  , defined by  .[4][5]

Applications

edit

Convergence in Lp

edit

Let   be a continuous martingale such that

 

for some  . Then there exists a random variable   such that   as   both  -almost surely and in  .

The statement for discrete-time martingales is essentially identical, with the obvious difference that the continuity assumption is no longer necessary.

Lévy's zero–one law

edit

Doob's martingale convergence theorems imply that conditional expectations also have a convergence property.

Let   be a probability space and let   be a random variable in  . Let   be any filtration of  , and define   to be the minimal σ-algebra generated by  . Then

 

both  -almost surely and in  .

This result is usually called Lévy's zero–one law or Levy's upwards theorem. The reason for the name is that if   is an event in  , then the theorem says that   almost surely, i.e., the limit of the probabilities is 0 or 1. In plain language, if we are learning gradually all the information that determines the outcome of an event, then we will become gradually certain what the outcome will be. This sounds almost like a tautology, but the result is still non-trivial. For instance, it easily implies Kolmogorov's zero–one law, since it says that for any tail event A, we must have   almost surely, hence  .

Similarly we have the Levy's downwards theorem :

Let   be a probability space and let   be a random variable in  . Let   be any decreasing sequence of sub-sigma algebras of  , and define   to be the intersection. Then

 

both  -almost surely and in  .

See also

edit

References

edit
  1. ^ Doob, J. L. (1953). Stochastic Processes. New York: Wiley.
  2. ^ Durrett, Rick (1996). Probability: theory and examples (Second ed.). Duxbury Press. ISBN 978-0-534-24318-0.; Durrett, Rick (2010). 4th edition. Cambridge University Press. ISBN 9781139491136.
  3. ^ a b "Martingale Convergence Theorem" (PDF). Massachusetts Institute of Tecnnology, 6.265/15.070J Lecture 11-Additional Material, Advanced Stochastic Processes, Fall 2013, 10/9/2013.
  4. ^ Bobrowski, Adam (2005). Functional Analysis for Probability and Stochastic Processes: An Introduction. Cambridge University Press. pp. 113–114. ISBN 9781139443883.
  5. ^ Gushchin, A. A. (2014). "On pathwise counterparts of Doob's maximal inequalities". Proceedings of the Steklov Institute of Mathematics. 287 (287): 118–121. arXiv:1410.8264. doi:10.1134/S0081543814080070. S2CID 119150374.
  6. ^ Doob, Joseph L. (1994). Measure theory. Graduate Texts in Mathematics, Vol. 143. Springer. p. 197. ISBN 9781461208778.