Chapter 1. Martingale Sequences

1.1. Martingale Sequences: The Concept, Examples, and Basic Patterns^*

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

Y _n = a gambler's “gain” on the nth play of a game
Y ₀ = the original capital or “bankroll”

Set X _n = 0 for . Thus, X_n is the capital after n plays, and

(1.1)

Put and . For any n ∈ N , and or, equivalently, . Hence

If Y_N is an independent class with , the game is considered fair. In this case, we have by (CE5), (CE7), and hypothesis

(1.2)

Also

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

H _k = event of a “head” on the kth component trial
T _k = H _k ^c = 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 be the result of the nth play, where |B _n| is the amount of the bet; B _n > 0 indicates a bet on a head; B _n < 0 indicates a bet on a tail; B = 0 indicates a decision not to bet.

Systems take various forms; here we consider two possibilities.

The amount of the bet is determend by the pattern of outcomes of previous tosses
(1.3)
The amount bet is determined by the pattern of previous payoffs
(1.4)

Let Y ₀ = X ₀ = C , a constant. Since C is independent of any random variable, E[H|C] = E[H]. In either scheme, by (CE8), (CI5), and the fact

(1.5)

It follows that

(1.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,

is the basic sequence
is the incremental sequence

(1.7)

We suppose Z_N is a decision sequence and X _N ∼ Z _N ; that is, .

X _N ∼ Z _N iff Y _N ∼ Z _N
If X _N ∼ H _N and H _N ∼ Z _N , then X _N ∼ Z _N . In particular, if , then X _N ∼ H _N .

Definition. If X_N is integrable and Z_N is a decision sequence, then

X_N is a martingale (MG) relative to Z_N iff
(1.8)
X_N is a submartingale (SMG) relative to Z_N iff
(1.9)
X_N is a supermartingale (SRMG) relative to Z_N iff
(1.10)

Notation. When we write is a martingale (submartingale, supermartingale), we are asserting X_N is integrable, Z_N is a decision sequence, X _N ∼ Z _N , and X_N is a MG (SMG, SRMG) relative to Z_N .

Definition. If Y_N is integrable and Z_N is a decision sequence, then

Y_N is absolutely fair relative to Z_N iff
(1.11)
Y_N is favorable relative to Z_N iff
(1.12)
Y_N is unfavorable relative to Z_N iff
(1.13)

Notation. When we write is absolutely fair (favorable, unfavorable), we are asserting Y_N is integrable, Z_N is a decision sequence, Y _N ∼ Z _N , and Y_N is absolutely fair (favorable, unfavorable) relative to Z_N . IXA2-2

Theorem 1.1. IXA2-1

If X_N is a basic sequence and Y_N is the corresponding incremental sequence, then

is a martingale iff is absolutely fair.
is a submartingale iff is favorable.
is a supermartingale iff is unfavorable.

Proof

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

(1.14)

Remarks

is a SMG iff is a SRMG
We write (S)MG to indicate the same statement can be made for a MG or a SMG with the appropriate choice of = or ≥
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 1.2. IXA3-1

If is a (S)MG and X _N ∼ H _N , with H _N ∼ Z _N , then is a (S)MG.

Proof

Let . By (CE9), the (S)MG definition, monotonicity, and (CE7)

(1.15)

Theorem 1.3. IXA3-2

For integrable X _N ∼ Z _N , the following are equivalent

Proof

b a: as a special case

a b: By (CE9), (a), and monotonicity

(1.16)

k – 1 iterations yield

d c: as a special case

c a: By (CE1) and (c),

. Since

and

, the result follows from the uniqueness property (E5)

b d: By (CE1), (b), and monotonicity

We thus have d ⇒ c ⇒ a ⇔ b ⇒ d

Corollary 1.1. IXA3-3

If is a (S)MG, then

Theorem 1.4. IXA3-4

is a (S)MG iff

Proof

EXERCISE. Note

IXA3-2

Theorem 1.5. IXA3-5

If is an L ² MG, then

Proof

by (CE1b) and Thm IXA3-4
by (CE1b), (CE8), and Thm IXA3-4
As in b, since X _n – X _m ∼ W _n
Suppose p < q . Then, since X _p ∼ W _p , by definition of MG. For q < p , interchange in the argument above.
by d, above
By c, for j ≠ k . Hence,

A variety of weighted sums of increments are useful.

Theorem 1.6. IXA3-6

Suppose is a (S)MG and Y_N is the incremental sequence. Let H₀ be a (nonnegative) constant and let , be bounded (nonnegative). Set

(1.17)

Then is a (S)MG.

Proof

by (CE8)

For MG case: for arbitrary bounded H_n

For SMG case: for H _n ≥ 0, bounded

The conclusion follows from Theorem 1.1. IXA2-1

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

Theorem 1.7. IXA3-7

In Theorem IXA3-6, if and 0 ≤ H _n ≤ 1a.s.∀n ∈ N , then

Proof

, by hypothesis, and , by (CE8). Thus, by monotonicity and (CE1b)

(1.18)

Hence

(1.19)

Some important special cases

Theorem 1.8. IXA3-8

Suppose integrable X _N ∼ Z _N . If X _{n + 1} – X _n( ≥ )0a.s.∀n ∈ N , then is a (S)MG.

Proof

Apply monotonicity and Theorem IXA3-4

Theorem 1.9. IXA3-9

Suppose X_N has independent increments.

If , invariant with n, then X_N is a MG.
If , then is a (S)MG.

Proof

For any n, consider any . By independent increments, is independent. Hence, . The desired result follows from Theorem IXA3-2(c).

Theorem 1.10. IXA3-10

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

, Let ,

If is a MG, then is a SMG.
If g is nondecreasing and is a SMG, then so is

Proof

a. : By Jensen's inequality and the definition of a MG

(1.20)

b. : By Jensen's inequality

(1.21)

Since

and g is nondecreasing, we have

(1.22)

Some commonly utilized convex functions

g ( t ) = | t |
g(t) = t ² g is increasing for t ≥ 0
g(t) = u(t)t g nondecreasing for all t
g nonincreasing for all t
g is increasing for all t

Theorem 1.11. IXA3-11

Consider integrable X _N ∼ Z _N .

If and , then is a MG
If and , then is a SMG

Proof

(1.23)

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

1.2. Martingale Sequences: Examples and Further Patterns^*

Examples and further patterns

Theorem 1.12. A4-1 Sums of Independent Random Variables

Suppose Y_N is an independent, integrable sequence. Set .

If , then X_N is a (S)MG.

Theorem 1.13. A4-2 Products of nonnegative random variables

Suppose Y _N ∼ Z _N,Y _n ≥ 0a.s.∀n . Consider .

If , then is a (S)MG

Proof

X _n ∼ W _n and X _{n + 1} = Y _{n + 1} X _n . Hence,

Theorem 1.14. A4-3 Discrete random walk

Consider Y ₀ = 0 and iid. Set . Suppose . Let

(1.24)

Now . Hence, g _Y(s) = 1 has at most two roots, one of which is s = 1.

s = 1 is a minimum point iff , in which case X_N is a MG (see A4-1)
If g _Y(r) = 1 for 0 < r < 1, then . Let . By A4-2, Z_N is a MG

For the MG case in Theorem IXA3-6, the Y_n are centered at conditional expectation; that is

The following is an extension of that pattern.

Theorem 1.15. A4-4 More general sums

Consider integrable Y _N ∼ Z _N and bounded H _N ∼ Z _N . Let W _n = a constant for n < 0 and H _n = 1 for n < 0. Set

(1.25)

Then is a MG.

Proof

X _n ∼ W _n;∀n ≥ 0 and

IXA4-2

Theorem 1.16. A4-5 Sums of products

Suppose Y_N is absolutely fair relative to Z_N , with , fixed k > 0. For n ≥ k , set

(1.26)

Then is a MG,

Proof

X _{n + 1} = X _n + K _{n + 1} , where

(1.27)

(1.28)

We consider, next, some relationships with homogeneous Markov sequences.

Suppose is a homogeneous Markov sequence with finite state space and transition matrix . A function f on E is represented by a column matrix . Then has value f(k) when X _n = k . Pf is an m × 1 column matrix and P f(j) is the jth element of that matrix. Consider . Now

(1.29)

A nonnegative function f on E is called (super)harmonic for P iff .

Theorem 1.17. A4-6 Positive supermartingales and superharmonic functions.

Suppose is a homogeneous Markov sequence with finite state space and transition matrix . For nonnegative f on E, let . Then is a positive (super)martingale P(SR)MG iff f is (super)harmonic for P.

Proof

As noted above .

If f is (super)harmonic , so that
(1.30)
If is a P(SR)MG, then
(1.31)

IX A4-3

An eigenfunction f and associated eigenvalue λ for P satisfy P f = λ f (i.e., (λ I – P)f = 0). In most cases, |λ| < 1. For real λ, 0 < λ < 1, the eigenfunctions are superharmonic functions. We may use the construction of Theorem IXA3-12 to obtain the associated MG.

Theorem 1.18. A4-7 Martingales induced by eigenfunctions for homogeneous Markov sequences

Let be a homogenous Markov sequence, and f be an eigenfunction with eigenvalue λ. Put . Then, by Theorem IAXA3-12, is a MG.

Theorem 1.19. A4-8 A dynamic programming example.

We consider a horizon of N stages and a finite state space .

Observe the system at prescribed instants
Take action on the basis of previous states and actions.

Suppose the observed state is j and the action is a ∈ A . Two results ensue:

A return r(j,a) is realized
The system moves to a new state

Let:

Y _n = state in nth period,

A _n = action taken on the basis of

[A₀ is the initial action based on the initial state Y₀ ]

A policy π is a set of functions , such that

(1.32)

The expected return under policy π, when Y ₀ = j ₀ is

(1.33)

The goal is to determine π to maximize .

Let and . If is Markov, then use of (CI9) and (CI11) shows that for any policy the Z-process is Markov. Hence

(1.34)

We assume time homogeneity in the sense that

(1.35)

We make a dynamic programming approach

Define recursively f _N , f _{N
–
1} , ⋯ , f ₀ as follows:

f _N(j) = 0,∀j ∈ E . For n = N,N – 1,⋯,2,1, set

(1.36)

Put

(1.37)

Then, by A4-2, is a MG, with and

(1.38)

IX A4-4

We may therefore assert

(1.39)

(1.40)

Hence, . For . If a policy π^* can be found which yields equality, then π^* is an optimal policy.

The following procedure leads to such a policy.

For each j ∈ E , let be the action which maximizes
(1.41)
Thus, .
Now, , which yields equality in the argument above. Thus, and π^* is optimal.

Note that π^* is a Markov policy, . The functions f_n depend on the future stages, but once determined, the policy is Markov.

Theorem 1.20. A4-9 Doob's martingale

Let X be an integrable random variable and Z_N an arbitrary sequence of random vectors. For each n, let . Then is a MG.

Proof

(1.42)

(1.43)

Theorem 1.21. A4-9a Best mean-square estimators

If X ∈ L ² , then is the best mean-square estimator of X, given . is a MG.

Theorem 1.22. A4-9b Futures pricing

Let X_N be a sequence of “spot” prices for a commodity. Let t₀ be the present and t ₀ + T be a fixed future. The agent can be expected to know the past history , and will update as t increases beyond t₀ . Put , the expected futures price, given the history up to t ₀ + k . Then is a Doob's MG, with Y = X _{t
₀ + T} , relative to , where Z ₀ = U _{t
₀} and Z _k = X _{t
₀ + k} for 1 ≤ k ≤ T .

Theorem 1.23. A4-9c Discounted futures

Assume rate of return is r per unit time. Then α = 1 / (1 + r) is the discount factor. Let

(1.44)

Then

(1.45)

Thus is a SMG relative to .

Implication from martingale theory is that all methods to determine profitable patterns of prediction from past history are doomed to failure.

IX A4-5

Theorem 1.24. A4-10 Present discounted value of capital

If α = 1 / (1 + r) is the discount factor, X_n is the dividend at time n, and V_n is the present value, at time n, of all future returns, then

(1.46)

(1.47)

Note that iff . Set . Then so that

(1.48)

Thus, is a (S)MG iff

(1.49)

Summary: Convergence of Submartingales

The submartingale convergence theorem

Theorem 1.25.

If is a SMG with , then there exists X _∞ ∼ W _∞ such that

Uniform integrability and some convergence conditions

Definition. The class is uniformly integrable iff

(1.50)

Theorem 1.26.

Any of the following conditions ensures uniform integrability:

The class is dominated by an integrable random variable Y.
The class is finite and integrable.
There is a u.i. class such that for all t ∈ T .
X integrable implies Doob's MG is u.i.

Definition. The class is uniformly absolutely continuous iff for each ϵ > 0 there is a δ > 0 such that P(A) < δ implies .

Theorem 1.27.

is u.i. iff both (i) X_T is u.a.c., and (ii) .

Definition. iff as n → ∞ for all ϵ > 0.

(1.51)

Theorem 1.28.

implies

Theorem 1.29.

If (i) , (ii) and (iii) exists a.s., then

(1.52)

Theorem 1.30.

Suppose is a (S)MG. Consider the following

(A) :

or, equivalently,

- - - - - - - - - - - -

(a) : X_N is uniformly integrable.

(a ⁺ ) : X ⁺ _N is uniformly integrable.

(b) :

(b ⁺ ) :

(c) : There is an integrable X _∞ ∼ W _∞ such that

(1.53)

(c ^' ) : Condition (c) with ≥ even for a MG.

(d) : There is an integrable X with

(d ^' ) : Condition (d) with ≥ even for a MG.

Then

Each of the propositions (a) through (d ^' ) implies (A), hence SMG convergence.
(a) (a ⁺ )
(a) (b) (c) (d)
(a ⁺ ) (b ⁺ ) (c ^' ) (d ^' )
For a MG, (d) (a), so that (a) (b) (c) (d)

The notion of regularity is characterized in terms of the conditions in the theorem.

Definition. A martingale is said to be martingale regular iff the equivalent conditions (a), (b), (c), (d) in the theorem hold.

A submartingale is said to be submartingale regular iff the equivalent conditions (a ⁺ ), (b ⁺ ), (c ^' ), (d ^' ) in the theorem hold.

Remarks

Since a MG is a SMG, a martingale regular MG is also submartingale regular.
It is not true, in general that a submartingale regular SMG is martingale regular. We do have for SMG (a) ⇔ (b) ⇒ (c) ⇒ (d).
Regularity may be viewed in terms of membership of X_∞ in the (S)MG. The condition is indicated by saying X_∞ belongs to the (S)MG or by saying the (S)MG is closed (on the right) by X_∞ .