2Martingales in discrete time
III Advanced Probability
2.2 Stopping time and optimal stopping
The optional stopping theorem says the definition of a martingale in fact implies
an a priori much stronger property. To formulate the optional stopping theorem,
we need the notion of a stopping time.
Definition
(Stopping time)
.
A stopping time is a random variable
T
: Ω
→
N
≥0
∪ {∞} such that
{T ≤ n} ∈ F
n
for all n ≥ 0.
This means that at time
n
, if we want to know if
T
has occurred, we can
determine it using the information we have at time n.
Note that
T
is a stopping time iff
{t
=
n} ∈ F
n
for all
n
, since if
T
is a
stopping time, then
{T = n} = {T ≤ n} \ {T ≤ n − 1},
and {T ≤ n − 1} ∈ F
n−1
⊆ F
n
. Conversely,
{T ≤ n} =
n
[
k=1
{T = k} ∈ F
n
.
This will not be true in the continuous case.
Example. If B ∈ B(R), then we can define
T = inf{n : X
n
∈ B}.
Then this is a stopping time.
On the other hand,
T = sup{n : X
n
∈ B}
is not a stopping time (in general).
Given a stopping time, we can make the following definition:
Definition
(
X
T
)
.
For a stopping time
T
, we define the random variable
X
T
by
X
T
(ω) = X
T (ω)
(ω)
on {T < ∞}, and 0 otherwise.
Later, for suitable martingales, we will see that the limit
X
∞
=
lim
n→∞
X
n
makes sense. In that case, We define X
T
(ω) to be X
∞
(ω) if T = ∞.
Similarly, we can define
Definition (Stopped process). The stopped process is defined by
(X
T
n
)
n≥0
= (X
T (ω)∧n
(ω))
n≥0
.
This says we stop evolving the random variable X once T has occurred.
We would like to say that
X
T
is “
F
T
-measurable”, i.e. to compute
X
T
, we
only need to know the information up to time
T
. After some thought, we see
that the following is the correct definition of F
T
:
Definition (F
T
). For a stopping time T , define
F
T
= {A ∈ F
∞
: A ∩ {T ≤ n} ∈ F
n
}.
This is easily seen to be a σ-algebra.
Example. If T ≡ n is constant, then F
T
= F
n
.
There are some fairly immediate properties of these objects, whose proof is
left as an exercise for the reader:
Proposition.
(i) If T, S, (T
n
)
n≥0
are all stopping times, then
T ∨ S, T ∧ S, sup
n
T
n
, inf T
n
, lim sup T
n
, lim inf T
n
are all stopping times.
(ii) F
T
is a σ-algebra
(iii) If S ≤ T, then F
S
⊆ F
T
.
(iv) X
T
1
T <∞
is F
T
-measurable.
(v)
If (
X
n
) is an adapted process, then so is (
X
T
n
)
n≥0
for any stopping time
T
.
(vi)
If (
X
n
) is an integrable process, then so is (
X
T
n
)
n≥0
for any stopping time
T .
We now come to the fundamental property of martingales.
Theorem
(Optional stopping theorem)
.
Let (
X
n
)
n≥0
be a super-martingale
and S ≤ T bounded stopping times. Then
EX
T
≤ EX
S
.
Proof. Follows from the next theorem.
What does this theorem mean? If
X
is a martingale, then it is both a
super-martingale and a sub-martingale. So we can apply this to both
X
and
−X, and so we have
E(X
T
) = E(X
S
).
In particular, since 0 is a stopping time, we see that
EX
T
= EX
0
for any bounded stopping time T .
Recall that martingales are supposed to model fair games. If we again think
of
X
n
as the wealth at time
n
, and
T
as the time we stop gambling, then this
says no matter how we choose
T
, as long as it is bounded, the expected wealth
at the end is the same as what we started with.
Example. Consider the stopping time
T = inf{n : X
n
= 1},
and take
X
such that
EX
0
= 0. Then clearly we have
EX
T
= 1. So this tells us
T is not a bounded stopping time!
Theorem. The following are equivalent:
(i) (X
n
)
n≥0
is a super-martingale.
(ii) For any bounded stopping times T and any stopping time S,
E(X
T
| F
S
) ≤ X
S∧T
.
(iii) (X
T
n
) is a super-martingale for any stopping time T .
(iv) For bounded stopping times S, T such that S ≤ T , we have
EX
T
≤ EX
S
.
In particular, (iv) implies (i).
Proof.
–
(ii)
⇒
(iii): Consider (
X
T
0
n
)
≥0
for a stopping time
T
0
. To check if this is a
super-martingale, we need to prove that whenever m ≤ n,
E(X
n∧T
0
| F
m
) ≤ X
m∧T
0
.
But this follows from (ii) above by taking S = m and T = T
0
∧ n.
– (ii) ⇒ (iv): Clear by the tower law.
– (iii) ⇒ (i): Take T = ∞.
– (i) ⇒ (ii): Assume T ≤ n. Then
X
T
= X
S∧T
+
X
S≤k<T
(X
k+1
− X
k
)
= X
S∧T
+
n
X
k=0
(X
k+1
− X
k
)1
S≤k<T
(∗)
Now note that
{S ≤ k < T }
=
{S ≤ k} ∩ {T ≤ k}
c
∈ F
k
. Let
A ∈ F
S
.
Then A ∩ {S ≤ k} ∈ F
k
by definition of F
S
. So A ∩ {S ≤ k < T } ∈ F
k
.
Apply E to to (∗) × 1
A
. Then we have
E(X
T
1
A
) = E(X
S∧T
1
A
) +
n
X
k=0
E(X
k+1
− X
k
)1
A∩{S≤k<T }
.
But for all k, we know
E(X
k+1
− X
k
)1
A∩{S≤k<T }
≤ 0,
since X is a super-martingale. So it follows that for all A ∈ F
S
, we have
E(X
T
· 1
A
) ≤ E(X
S∧T
1
A
).
But since
X
S∧T
is
F
S∧T
measurable, it is in particular
F
S
measurable. So
it follows that for all A ∈ F
S
, we have
E(E(X
T
| F
S
)1
A
) ≤ E(X
S∧T
1
A
).
So the result follows.
– (iv) ⇒ (i): Fix m ≤ n and A ∈ F
m
. Take
T = m1
A
+ 1
A
C
.
One then manually checks that this is a stopping time. Now note that
X
T
= X
m
1
A
+ X
n
1
A
C
.
So we have
0 ≥ E(X
n
) − E(X
T
)
= E(X
n
) − E(X
n
1
A
c
) − E(X
m
1
A
)
= E(X
n
1
A
) − E(X
m
1
A
).
Then the same argument as before gives the result.