59.2 Discrete Martingales
Definition 59.2.1 Let Sk be an increasing sequence of σ algebras which are subsets of
S and Xk be a sequence of real-valued random variables with E
< ∞ such that Xk
is Sk measurable. Then this sequence is called a martingale if
a submartingale if
and a supermartingale if
Saying that Xk is Sk measurable is referred to by saying
is adapted to Sk.
Note that if
is a martingale, then
is a submartingale and that if
is a submartingale and
is convex and increasing,
An upcrossing occurs when a sequence goes from a up to b. Thus it crosses the
in the up direction, hence upcrossing. More precisely,
Definition 59.2.2 Let
i=1I be any sequence of real numbers, I ≤∞. Define
an increasing sequence of integers
as follows. m1 is the first integer ≥
such that xm1 ≤ a, m2 is the first integer larger than m1 such that xm2 ≥ b, m3
is the first integer larger than m2 such that xm3 ≤ a, etc. Then each sequence,
, is called an upcrossing of
Here is a picture of an upcrossing.
Proposition 59.2.3 Let
i=1n be a finite sequence of real random variables
is a probability space. Let U
denote the number
of upcrossings of Xi
of the interval
. Then U
is a random variable.
Proof: Let X0
+ 1, let Y 0
and let Y k
remain 0 for
. When this happens (if ever), Y l+1
1. Then let Y i
when Y r+1
0. Let Y k
k ≥ r
+ 1 until Xk
when Y k
1 and continue in this way.
Thus the upcrossings of Xi
are identified as unbroken strings of ones for
with a zero at each end, with the possible exception of the last string of ones
which may be missing the zero at the upper end and may or may not be an
Note also that Y 0 is measurable because it is identically equal to 0 and that if Y k is
measurable, then Y k+1 is measurable because the only change in going from k to k + 1 is
a change from 0 to 1 or from 1 to 0 on a measurable set determined by Xk. In
This set is in S by induction. Of course, Y k+1−1
is just the complement of this set.
measurable since 0,
1 are the only two values possible. Now
if k < n and
= 1 exactly when an upcrossing has been completed and each
is a random variable as claimed.
The following corollary collects some key observations found in the above
Corollary 59.2.4 U
≤ the number of unbroken strings of ones in the sequence,
there being at most one unbroken string of ones which produces no upcrossing.
where ψi is some function of the past values of Xj
Lemma 59.2.5 Let ϕ be a convex and increasing function and suppose
is a submartingale. Then if E
< ∞, it follows
is also a submartingale.
Proof: It is given that E
by Jensen’s inequality.
The following is called the upcrossing lemma.