59.5.3 The Upcrossing Estimate
A very interesting example of stopping times is next. It has to do with upcrossings. First
here is a lemma.
Lemma 59.5.5 Let
be an increasing sequence of σ algebras and let
be adapted to this sequence. Suppose that X
has all values in
σ is a stopping time with the property that X
a. Let τ
be the first k > σ
such that X
b. If no such k exists, then τ ≡∞. Then τ is a stopping time.
Also, you can switch a,b in the above and obtain the same conclusion that τ is a
Proof: Let I be an interval and consider X
Is k → X
be an interval. Is
We know that this set is in ℱk∨σ.
Consider the second set in ♠. There are two cases, a ∈ I and a
First suppose a
Then if ω ∈
it follows that X
Therefore, in this case, the
set on the right in ♠
is empty and the empty set is in ℱk
. Next suppose a ∈ I.
and so each ω ∈
is in the set
and so, in this case, the set on the
Now consider the first set in ♠,
by the definition of what it means for the set A to be in ℱk∨σ. The argument proceeds in
the same way when you switch a,b. ■
Definition 59.5.6 Let
be a sequence of random variables adapted to the
increasing sequence of σ algebras,
be an interval. An upcrossing is
a sequence Xn
such that Xn
< b for i < p, and
Example 59.5.7 Let
be an increasing sequence of σ algebras contained in ℱ
is a probability space and let
be a sequence of real valued random
variables such that Xn is ℱn measurable. Also let a < b. Define
is never in the desired interval for any n > Tj
, then define Tj+1
Then this is an increasing sequence of stopping times.
It happens that the above gives an increasing sequence of stopping times.
Lemma 59.5.8 The above example gives an increasing sequence of stopping times.
Proof: You could consider the modified random variables
Then these new random variables stay in
and if you replace
in the above with
you get the same sequence of stopping times. Now apply Lemma 59.5.5
Now there is an interesting application of these stopping times to the concept of
be a submartingale such that
measurable and let a < b.
The function, x →
is increasing and convex so
is also a submartingale. Furthermore,
to ≥ b
goes from 0 to
≥ b − a.
That is, a subsequence of the form
equal to either X
starts out below a
(0) and ends up above b
Such a sequence is called an upcrossing of
The idea is to estimate the expected number of upcrossings for n ≤ N.
stopping times defined in Example 59.5.7
, let Tk′ ≡
a continuous function of the stopping time, is also a stopping time which is
bounded. Moreover, Tk′≤ Tk+1′
. Now pick n
such that 2n > N.
Then for each
must equal the sum of all successive terms of the form
for k = 1,2,
This is because
is a strictly increasing sequence
which starts with 0 due to the assumption
and ends with N <
Now denote by U
N the number of upcrossings. When Tk′ is such that k is odd,
is above b − a
and when k
is even, it equals 0. Therefore, in the first sum
XT2k+1′− XT2k′ ≥ b − a
and there are U
terms which are nonzero in this sum.
(Note this might not be n
because many of the terms in the sum could be 0 due to the
definition of Tk′
N is a random variable. To see this, let Zk
= 1 if
T2k+1′ > T2k′
otherwise. Thus U
Therefore, it makes sense to take
the expected value of both sides of 59.5.15
. By the optional sampling theorem,
is a submartingale and so
This proves most of the following fundamental upcrossing estimate.
Theorem 59.5.9 Let
be a real valued submartingale such that Xn is ℱn
measurable. Then letting U
N denote the upcrossings of
from a to b for
n ≤ N,
Proof: The estimate 59.5.16 was based on the assumption that X0
If this is
not so, modify X0
. Change it to min
Then the inequality holds for the modified
submartingale which has at least as many upcrossings. Therefore, the inequality remains.
Note this theorem holds if the submartingale starts at the index 1 rather than 0. Just
adjust the argument.