Skip to content Skip to navigation

OpenStax_CNX

You are here: Home » Content » Martingale Sequences: The Concept, Examples, and Basic Patterns

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This module is included in aLens by: Digital Scholarship at Rice UniversityAs a part of collection: "Topics in Applied Probability"

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

  • NSF Partnership display tagshide tags

    This module is included inLens: NSF Partnership in Signal Processing
    By: Sidney BurrusAs a part of collection: "Topics in Applied Probability"

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content display tagshide tags

    This module is included inLens: Connexions Featured Content
    By: ConnexionsAs a part of collection: "Topics in Applied Probability"

    Click the "Featured Content" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Topics in Applied Probability"

    Click the "UniqU content" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Martingale Sequences: The Concept, Examples, and Basic Patterns

Module by: Paul E Pfeiffer. E-mail the author

Summary: The notion of martingales and related concepts seem to have originated in studies of games of chance. Certain patterns were identified and extended to more general sequences of random variables. The resulting abstract theory provides a basis for many applications, both theoretical and practical.

The concept, examples, and basic patterns

A classical example

The notion of martingales and related concepts seem to have originated in studies of games of chance similar to the following.  Suppose

  •       Yn=Yn= a gambler's “gain” on the nth play of a game
  •       Y0=Y0= the original capital or “bankroll”

Set Xn=0Xn=0 for n<0,Xn=k=0nYkn0n<0,Xn=k=0nYkn0.  Thus, Xn is the capital after n plays, and

Y 0 = X 0 Y n = X n - X n - 1 n 0 Y 0 = X 0 Y n = X n - X n - 1 n 0
(1)

Put Un=(X0,X1,,Xn)Un=(X0,X1,,Xn) and Vn=(Y0,Y1,,Yn)Vn=(Y0,Y1,,Yn).   For any nNnN, Un=gn(Vn)Un=gn(Vn) and Vn=hn(Un)Vn=hn(Un) or, equivalently, σ(Un)=σ(Vn)σ(Un)=σ(Vn).  Hence E[H|Un]=E[H|Vn]a.s.E[H|Un]=E[H|Vn]a.s.

If YN is an independent class with E[Yn]=0n1E[Yn]=0n1, the game is considered fair.  In this case, we have by (CE5), (CE7), and hypothesis

E [ X n + 1 | U n ] = E [ Y n + 1 | V n ] + E [ X n | U n ] = E [ Y n + 1 ] + X n = X n a . s . E [ X n + 1 | U n ] = E [ Y n + 1 | V n ] + E [ X n | U n ] = E [ Y n + 1 ] + X n = X n a . s .
(2)

Also  E[Xn+1-Xn|Un]=E[Yn+1|Vn]=0a.s.E[Xn+1-Xn|Un]=E[Yn+1|Vn]=0a.s.

Gamblers seek to develop a “system” to improve expected earnings.  We examine some typical approaches and show their futility.  To keep the analysis simple, consider a simple coin-flipping game.  Let

  •       Hk=Hk= event of a “head” on the kth component trial
  •       Tk=Hkc=Tk=Hkc= event of a “tail” on the kth component trial

The player has a system.  He decides how much to bet on each play from the pattern of previous events.  Let Bn[IHn-ITn]=BnZnBn[IHn-ITn]=BnZn be the result of the nth play, where  |Bn||Bn| is the amount of the bet;  Bn>0Bn>0 indicates a bet on a head;  Bn<0Bn<0 indicates a bet on a tail;  B=0B=0 indicates a decision not to bet.

Systems take various forms;  here we consider two possibilities.

  1. The amount of the bet is determend by the pattern of outcomes of previous tosses
    Bn=gn-1(IH1,IH2,,IHn-1)Yn=BnZnZn=IHn-ITn=2IHn-1Bn=gn-1(IH1,IH2,,IHn-1)Yn=BnZnZn=IHn-ITn=2IHn-1
    (3)
  2. The amount bet is determined by the pattern of previous payoffs
    Bn=gn-1(Y1,Y2,,Yn-1)=hn-1(B1,IH1,,Bn-1IHn-1)Yn=BnZnBn=gn-1(Y1,Y2,,Yn-1)=hn-1(B1,IH1,,Bn-1IHn-1)Yn=BnZn
    (4)

Let Y0=X0=CY0=X0=C, a constant.  Since C is independent of any random variable, E[H|C]=E[H]E[H|C]=E[H]. In either scheme, by (CE8), (CI5), and the fact E[Zk]=0E[Zk]=0

E [ Y n + 1 | V n ] = E [ B n + 1 Z n + 1 | φ n ( B 1 , I H 1 , , B n I H n ) ] = B n + 1 E [ Z n + 1 ] = 0 a . s . E [ Y n + 1 | V n ] = E [ B n + 1 Z n + 1 | φ n ( B 1 , I H 1 , , B n I H n ) ] = B n + 1 E [ Z n + 1 ] = 0 a . s .
(5)

It follows that

E [ X n + 1 | U n ] = E [ Y n = 1 | v n ] + E [ X n | U n ] = 0 + X n a . s . E [ X n + 1 | U n ] = E [ Y n = 1 | v n ] + E [ X n | U n ] = 0 + X n a . s .
(6)

The “fairness” of the game is not altered by the betting scheme, since decisions must be based on past performance.   In spite of simple beginnings, the extension and analysis of these patterns form a major thrust of modern probability theory.

Formulation of the concept

In the following treatment,

  • XN={Xn:nN}XN={Xn:nN} is the basic sequence   N={0,1,}N={0,1,}
  • YN={Yn:nN}YN={Yn:nN} is the incremental sequence
Y n = X n - X n - 1 X n = k = 0 n Y k n 0 , [ X n = 0 n < 0 ] Y n = X n - X n - 1 X n = k = 0 n Y k n 0 , [ X n = 0 n < 0 ]
(7)

We suppose ZN is a decision sequence and XNZNXNZN; that is, Xn=gn(Wn)=gn(Z0,Z1,,Zn)Xn=gn(Wn)=gn(Z0,Z1,,Zn).

  • XNZNXNZN iff YNZNYNZN
  • If XNHNXNHN and HNZNHNZN, then XNZNXNZN.  In particular, if Hn=kn(Un)=kn(X0,X1,,Xn)Hn=kn(Un)=kn(X0,X1,,Xn), then XNHNXNHN.

Definition.  If XN is integrable and ZN is a decision sequence, then

  1. XN is a martingale (MG) relative to ZN iff
    XNZNandE[Xn+1|Wn]=Xna.s.nNXNZNandE[Xn+1|Wn]=Xna.s.nN
    (8)
  2. XN is a submartingale (SMG) relative to ZN iff
    XNZNandE[Xn+1|Wn]Xna.s.nNXNZNandE[Xn+1|Wn]Xna.s.nN
    (9)
  3. XN is a supermartingale (SRMG) relative to ZN iff
    XNZNandE[Xn+1|Wn]Xna.s.nNXNZNandE[Xn+1|Wn]Xna.s.nN
    (10)

Notation.  When we write (XN,ZN)(XN,ZN) is a martingale (submartingale, supermartingale), we are asserting XN is integrable, ZN is a decision sequence, XNZNXNZN, and XN is a MG (SMG, SRMG) relative to ZN.

Definition.  If YN is integrable and ZN is a decision sequence, then

  1. YN is absolutely fair relative to ZN iff
    YNZNandE[Yn+1|Wn]=0a.s.nNYNZNandE[Yn+1|Wn]=0a.s.nN
    (11)
  2. YN is favorable relative to ZN iff
    YNZNandE[Yn+1|Wn]0a.s.nNYNZNandE[Yn+1|Wn]0a.s.nN
    (12)
  3. YN is unfavorable relative to ZN iff
    YNZNandE[Yn+1|Wn]0a.s.nNYNZNandE[Yn+1|Wn]0a.s.nN
    (13)

Notation.  When we write (YN,ZN)(YN,ZN) is absolutely fair (favorable, unfavorable), we are asserting YN is integrable, ZN is a decision sequence, YNZNYNZN, and YN is absolutely fair (favorable, unfavorable) relative to ZN.   IXA2-2

Theorem 1: IXA2-1

If XN is a basic sequence and YN is the corresponding incremental sequence, then

  1. (XN,ZN)(XN,ZN) is a martingale iff (YN,ZN)(YN,ZN) is absolutely fair.
  2. (XN,ZN)(XN,ZN) is a submartingale iff (YN,ZN)(YN,ZN) is favorable.
  3. (XN,ZN)(XN,ZN) is a supermartingale iff (YN,ZN)(YN,ZN) is unfavorable.

Proof

Let * be any one of the symbols =,=,, or .  Then by linearity and (CE7)

E [ X n + 1 | W n ] = E [ Y n + 1 | W n ] + E [ X n | W n ] = E [ Y n + 1 | W n ] + X n * X n a . s . iff E [ Y n + 1 | W n ] * 0 a . s . E [ X n + 1 | W n ] = E [ Y n + 1 | W n ] + E [ X n | W n ] = E [ Y n + 1 | W n ] + X n * X n a . s . iff E [ Y n + 1 | W n ] * 0 a . s .
(14)

Remarks

  1. (XN,ZN)(XN,ZN) is a SMG iff (-XN,ZN)(-XN,ZN) is a SRMG
  2. We write (S)MG to indicate the same statement can be made for a MG or a SMG with the appropriate choice of = or
  3. We write ()() to indicate simultaneously two cases:
    • ()() read as = in all places (for a MG)
    • ()() read as in all places (for a SMG)

Some Basic Patterns

Theorem 2: IXA3-1

If (XN,ZN)(XN,ZN) is a (S)MG and XNHNXNHN, with HNZNHNZN,  then (XN,HN)(XN,HN) is a (S)MG.

Proof

Let Kn=(H0,H1,,Hn)Kn=(H0,H1,,Hn).  By (CE9), the (S)MG definition, monotonicity, and (CE7)

E [ X n + 1 | K n ] = E { E [ X n + 1 | W n ] | K n } ( ) E [ X n | K n ] = X n a . s . E [ X n + 1 | K n ] = E { E [ X n + 1 | W n ] | K n } ( ) E [ X n | K n ] = X n a . s .
(15)

Theorem 3: IXA3-2

For integrable XNZNXNZN, the following are equivalent

a ( X N , Z N ) is a (S)MG b E [ X n + k | W n ] ( ) X n a . s . n , k N c E [ I C X n + 1 ] ( ) E [ I C X n ] C σ ( W n ) n N d E [ I C X n + k ] ( ) E [ I C X n ] C σ ( W n ) n , k N a ( X N , Z N ) is a (S)MG b E [ X n + k | W n ] ( ) X n a . s . n , k N c E [ I C X n + 1 ] ( ) E [ I C X n ] C σ ( W n ) n N d E [ I C X n + k ] ( ) E [ I C X n ] C σ ( W n ) n , k N

Proof

  • b a: as a  special case
  • a b: By (CE9), (a), and monotonicity
    E[Xn+k|Wn]=E{E[Xn+k|Wn+k-1]|Wn}()E[Xn+k-1|Wn]a.s.E[Xn+k|Wn]=E{E[Xn+k|Wn+k-1]|Wn}()E[Xn+k-1|Wn]a.s.
    (16)
    k-1k-1 iterations yield  E[Xn+k|Wn]()Xna.s.E[Xn+k|Wn]()Xna.s.
  • d c: as a  special case
  • c a: By (CE1) and (c),  E[ICXn+1]=E{ICE[Xn+1|Wn]}()E[ICXn]a.s.E[ICXn+1]=E{ICE[Xn+1|Wn]}()E[ICXn]a.s..   Since XnWna.s.XnWna.s. and E[Xn+1|Wn]Wna.s.E[Xn+1|Wn]Wna.s., the result follows from the uniqueness property (E5)
  • b d: By (CE1), (b), and monotonicity E[ICXn+k]=E{ICE[Xn+k|Wn]}()E[ICXn]E[ICXn+k]=E{ICE[Xn+k|Wn]}()E[ICXn]

We thus have dcabddcabd

Corollary 1: IXA3-3

If (XN,ZN)(XN,ZN) is a (S)MG, then E[Xn+k]()E[Xn]()E[X0]E[Xn+k]()E[Xn]()E[X0]

Theorem 4: IXA3-4

(XN,ZN)(XN,ZN) is a (S)MG iff E[Xq-Xp|Wn]()0a.s.np<qNE[Xq-Xp|Wn]()0a.s.np<qN

Proof

EXERCISE.  Note Xq-Xp=Yp+1++YqXq-Xp=Yp+1++Yq

IXA3-2

Theorem 5: IXA3-5

If (XN,ZN)(XN,ZN) is an L2L2 MG, then

E [ X q - X p ] = 0 p < q N E [ X n ( X q - X p ) ] = 0 n p < q N E [ ( X n - X m ) ( X q - X p ) ] = 0 m < n p < q N E [ X p X q ] = E [ X p q 2 ] p , q N E [ ( X q - X p ) 2 ] = E [ X q 2 ] - E [ X p 2 ] 0 p < q N E [ X p 2 ] = k = 0 p E [ Y k 2 ] p N E [ X q - X p ] = 0 p < q N E [ X n ( X q - X p ) ] = 0 n p < q N E [ ( X n - X m ) ( X q - X p ) ] = 0 m < n p < q N E [ X p X q ] = E [ X p q 2 ] p , q N E [ ( X q - X p ) 2 ] = E [ X q 2 ] - E [ X p 2 ] 0 p < q N E [ X p 2 ] = k = 0 p E [ Y k 2 ] p N

Proof

  1. E[Xq-Xp]=E{E[Xq-Xp|Wn]}=0E[Xq-Xp]=E{E[Xq-Xp|Wn]}=0 by (CE1b) and Thm IXA3-4
  2. E[Xn(Xq-Xp)]=E{XnE[Xq-Xp|Wn]}=0E[Xn(Xq-Xp)]=E{XnE[Xq-Xp|Wn]}=0 by (CE1b), (CE8), and Thm IXA3-4
  3. As in b, since Xn-XmWnXn-XmWn
  4. Suppose p<qp<q.  Then, since XpWpXpWp, E[XpXq]=E{XpE[Xq|Wp]}=E[Xp2]E[XpXq]=E{XpE[Xq|Wp]}=E[Xp2] by definition of MG.   For q<pq<p, interchange p,qp,q in the argument above.
  5. E[(Xq-Xp)2]=E[Xq2]-2E[XpXq]+E[Xp2]=E[Xq2]-2E[Xp2]+E[Xp2]E[(Xq-Xp)2]=E[Xq2]-2E[XpXq]+E[Xp2]=E[Xq2]-2E[Xp2]+E[Xp2] by d, above
  6. By c, E[YjYk]=0E[YjYk]=0 for jkjk.  Hence, E[Xp2]=E[(k=0pYk)2]=jkE[YjYk]=k=0pE[Yk2]E[Xp2]=E[(k=0pYk)2]=jkE[YjYk]=k=0pE[Yk2]

A variety of weighted sums of increments are useful.

Theorem 6: IXA3-6

Suppose (XN,ZN)(XN,ZN) is a (S)MG and YN is the incremental sequence. Let H0 be a (nonnegative) constant and let HnWn-1,n1HnWn-1,n1, be bounded (nonnegative).  Set

X n * = k = 0 n H k Y k = k = 0 n Y k * n N X n * = k = 0 n H k Y k = k = 0 n Y k * n N
(17)

Then (XN*,ZN)(XN*,ZN) is a (S)MG.

Proof

E[Yn+1*|Wn]=E[Hn+1Yn+1|Wn]=Hn+1E[Yn+1|Wn]a.s.E[Yn+1*|Wn]=E[Hn+1Yn+1|Wn]=Hn+1E[Yn+1|Wn]a.s. by (CE8)

For MG case: E[Yn+1*|Wn]=0a.s.E[Yn+1*|Wn]=0a.s. for arbitrary bounded Hn

For SMG case:  E[Yn+1*|Wn]0a.s.E[Yn+1*|Wn]0a.s. for Hn0Hn0, bounded

The  conclusion follows from Theorem 1

Remark.  This result extends the pattern in the introductory gambling example.  Theorem 4 IXA3-3

Theorem 7: IXA3-7

In Theorem IXA3-6, if E[X0]0E[X0]0 and 0Hn1a.s.nN0Hn1a.s.nN, then 0E[Xn*]E[Xn]nN0E[Xn*]E[Xn]nN

Proof

E[Yn+1|Wn]Hn+1E[Yn+1|Wn]()0a.s.E[Yn+1|Wn]Hn+1E[Yn+1|Wn]()0a.s., by hypothesis, and Hn+1E[Yn+1|Wn]=E[Yn+1*|Wn]a.s.Hn+1E[Yn+1|Wn]=E[Yn+1*|Wn]a.s., by (CE8).   Thus, by monotonicity and (CE1b)

E [ Y n + 1 ] ( ) E [ Y n + 1 * ] ( ) 0 n N and E [ Y 0 ] = E [ X 0 ] H 0 E [ Y 0 ] = E [ Y 0 * ] E [ Y n + 1 ] ( ) E [ Y n + 1 * ] ( ) 0 n N and E [ Y 0 ] = E [ X 0 ] H 0 E [ Y 0 ] = E [ Y 0 * ]
(18)

Hence

E [ X n ] = k = 0 n E [ Y k ] k = 0 n E [ Y k * ] = E [ X n * ] 0 E [ X n ] = k = 0 n E [ Y k ] k = 0 n E [ Y k * ] = E [ X n * ] 0
(19)

Some important special cases

Theorem 8: IXA3-8

Suppose integrable XNZNXNZN. If Xn+1-Xn()0a.s.nNXn+1-Xn()0a.s.nN, then (XN,ZN)(XN,ZN) is a (S)MG.

Proof

Apply monotonicity and Theorem IXA3-4

Theorem 9: IXA3-9

Suppose XN has independent increments.

  1. If E[Xn]=cE[Xn]=c, invariant with n, then XN is a MG.
  2. If E[Xn+1-Xn]()0,nNE[Xn+1-Xn]()0,nN,   then (XN(XN is a (S)MG.

Proof

  1. For any n, consider any Cσ(Un)Cσ(Un).  By independent increments, {IC,(Xn+1-Xn)}{IC,(Xn+1-Xn)} is independent.  Hence, E[ICXn+1]-E[ICXn]=E[IC(Xn+1-Xn)]=E[IC]E[(Xn+1-Xn)]()0E[ICXn+1]-E[ICXn]=E[IC(Xn+1-Xn)]=E[IC]E[(Xn+1-Xn)]()0. The desired result follows from Theorem IXA3-2(c).

Theorem 10: IXA3-10

Suppose g is a convex Borel function on an interval I which contains the range of all Xn and

E[|g(Xn)|]<nNE[|g(Xn)|]<nN,  Let Hn=g(Xn)nNHn=g(Xn)nN,

  1. If (XN,ZN)(XN,ZN) is a MG, then (HN,ZN)(HN,ZN) is a SMG.
  2. If g is nondecreasing and (XN,ZN)(XN,ZN) is a SMG, then so is (HN,ZN)(HN,ZN)

Proof

  • a.  : By Jensen's inequality and the definition of a MG
    E[g(Xn+1)|Wn]gE[Xn+1|Wn]=g(Xn)a.s.E[g(Xn+1)|Wn]gE[Xn+1|Wn]=g(Xn)a.s.
    (20)
  • b.  : By Jensen's inequality
    E[g(Xn+1)|Wn]gE[Xn+1|Wn]a.s.E[g(Xn+1)|Wn]gE[Xn+1|Wn]a.s.
    (21)
    Since E[Xn+1|Wn]Xna.s.E[Xn+1|Wn]Xna.s. and g is nondecreasing, we have
    gE[Xn+1|Wn]g(Xn)a.s.gE[Xn+1|Wn]g(Xn)a.s.
    (22)

Some commonly utilized convex functions

  1. g ( t ) = | t | g ( t ) = | t |
  2. g(t)=t2g(t)=t2g is increasing for t0t0
  3. g(t)=u(t)tg(t)=u(t)tg(Xn)=Xn+g(Xn)=Xn+g nondecreasing for all t
  4. g(t)=-u(-t)tg(t)=-u(-t)tg(Xn)=Xn-g(Xn)=Xn-g nonincreasing for all t
  5. g(t)=eat,a>0g(t)=eat,a>0g is increasing for all t

Theorem 11: IXA3-11

Consider integrable XNZNXNZN.

  1. If  E[Xn+1|Wn]=aXna.s.nE[Xn+1|Wn]=aXna.s.n and Xn*=1anXnnXn*=1anXnn, then (XN*,ZN)(XN*,ZN) is a MG
  2. If  E[Xn+1|Wn]aXna.s.,a>0,nE[Xn+1|Wn]aXna.s.,a>0,n and Xn*=1anXnnXn*=1anXnn, then (XN*,ZN)(XN*,ZN) is a SMG

Proof

E [ X n + 1 * | W n ] = 1 a n + 1 E [ X n + 1 | W n ] ( ) 1 a n + 1 a X n = X n * a . s . E [ X n + 1 * | W n ] = 1 a n + 1 E [ X n + 1 | W n ] ( ) 1 a n + 1 a X n = X n * a . s .
(23)

The restrictionl a>0a>0 is needed in the case.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks