Chapter 4
Conditioning and Martingale
Aithus C. Mao on 12th March 2024
The martingale replace the process of completely independence with similar repetition.
4.1 Conditioning
Let X be a random variable on a probability space (E,
E
, P) with E|X| ≤ ∞.
Denition 4.1.1 (Conditional Expectation w.r.t. a σ-algebra). Let
E
′
be a sub-σ-algebra
w.r.t.
E
, the conditional expectation E[X|
E
′
] is any random variable Y on
E
′
such that
for all A ∈
E
′
,
A
XdP =
A
Y dP.
Denition 4.1.2 (Conditional Expectation w.r.t. a Random Variable). Given two random
variables X and Y on (E,
E
, P), the conditional expectation E[X|Y ] is any random variable
Z on (E, σ(Y ), P) such that for all A ∈ σ(Y ),
A
XdP =
A
ZdP.
Lemma 4.1.1 (Uniqueness). All conditional expectations of one r.v. on a σ-algebra (or
on another r.v.) is a.s. equal.
Proof. We will only prove the case of conditioning on a σ-algebra, and the case of r.v. would
be straightforward. Let
E
′
be a sub-σ-algebra w.r.t.
E
, Y and Z be two r.v.s that are X
conditioning on
E
′
.
11
12 Martingale
Let A
:
= {x|Y (x) > Z(x)}. It can be easily veried that A is
E
′
-measurable. Thus,
A
Y dP =
A
ZdP, i.e.,
A
(Y − Z)dP = 0. As Y (x) > Z(x) for all x in A, we must have
that P(A) = 0. Similarly, we can also prove that P({x|Y (x) < Z(x)}) = 0. Consequently,
P({x|Y (x) = Z(x)}) = 0, and this completes the proof.
Remark 4.1.1. As stated in math stackexchange: The existence of conditional expectation
is more dicult. The proofs I’ve seen either use the Radon-Nikodym theorem, or the Riesz
representation theorem in Hilbert space. Any measure-theoretic probability book will have
a proof.
Lemma 4.1.2. Two random variables are independent i the σ-algebras generated by them
are independent.
Proof. C. Mao-TODO
4.2 Martingale
A martingale is a stochastic process where the previous r.v.s stacking on previous r.v.s by
adding details.
Denition 4.2.1 (Martingale). A real-valued stochastic process X = (X
t
)
t∈T
is called a
martingale if X is adapted to a ltration
F
= (
F
t
)
t∈T
∗
, X
t
is nite integrable for all t ∈ T,
and
E[X
t
− X
s
|
F
s
] = 0
a.s. whenever s < t.
Denition 4.2.2 (Martingale Dierence Sequence). A real-valued stochastic process X =
(X
t
)
t∈T
is called a martingale dierence sequence if X is adapted to a ltration
F
, each X
t
is nite integrable, and
E[X
t
|
F
s
] = 0
a.s. whenever s < t.
∗
A ltration is an index σ-algebras that the former is sub-σ-algebras of the latter. X
t
is
F
t
measurable
for all t ∈ T.
Lemma 13
4.3 Lemma
Given two random variables X, Y on
E
with σ(X) ⊆ σ(Y ), what would it be like if we apply
conditioning on σ(X) (i.e., X) to functions like f (X, Y )? f(X, Y ) shall be measurable w.r.t.
σ(Y ).
Lemma 4.3.1. If f(X, Y ) = XY , we shall have that, for all A ∈ σ(X),
A
E
XY |X
dP =
A
XE[Y |X]dP.
Proof. I shall only prove the case that both X and Y are simple functions on E, and the
extension to other integrable functions should be easy. Let R(X) and R(Y ) be the possible
values taken by X and Y . For any x ∈ R (X),
X
−1
(x)
E[XY |X]dP =
X
−1
(x)
xY dP = x
X
−1
(x)
Y dP
=x
X
−1
(x)
E[Y |X]dP
=
X
−1
(x)
xE[Y |X]dP.
Thus, for any A ∈ σ(X), by the disjoint property of X
−1
(x) for x ∈ R(X),
A
E[XY |X]dP =
x∈X(A)
X
−1
(x)
E[XY |X]dP
=
x∈X(A)
X
−1
(x)
xE[Y |X]dP
=
A
XE[Y |X]dP.
C. Mao-TODO: The proof would be much simpler if we use the uniqueness of the conditional
expectation.
14 Azuma-Hoeding (Azuma’s) Inequality
4.4 Azuma-Hoeding (Azuma’s) Inequality
Theorem 4.4.1 (Azuma-Hoeding Inequality). Suppose (X
t
)
t∈[N ]
is a super-martingale
adapting to (
F
t
)
t∈[N ]
and
†
|X
k
− X
k−1
| ≤ c
k
, (4.1)
almost surely for all k ∈ [1, N ]. Then for all positive integers N and all positive real ϵ,
P (X
N
− X
0
≥ ϵ) ≤ exp
−ϵ
2
2
N
k=1
c
2
k
.
proof sketch. We list the key components of the proof in the following.
• For any A ∈
E
′
⊆
E
, X ∈
E
′
, Y ∈
E
, and a measure µ on
E
,
A
f(X, Y )dµ =
A
E
f(X, Y )|
E
′
dµ.
We can take the whole set E as A.
‡
• We can thus use the induction,
E
exp
λ
N
k=1
[X
k
− X
k−1
]
=E
E
exp
λ
N
k=1
[X
k
− X
k−1
]
F
N −1
=E
exp
λ
N −1
k=1
[X
k
− X
k−1
]
· E
exp
λ[X
N
− X
N −1
]
F
N −1
.
(By Lemma 4.3.1)
By Eq. (4.1) and the denition of super-martingales, it holds almost surely that
E
exp
λ[X
k
− X
k−1
]
F
N −1
≤ exp
c
2
N
λ
2
8
.
We can do inductions on [2, N ] and get E
exp
λ
N
k=1
[X
k
− X
k−1
]
≤ exp
λ
2
t
c
2
t
8
.
We can apply the Cherno bound and get the desired result.
†
[N ] = {0, 1, 2 . . . N}, [M, N] = {M . . . N }. The super-martingale requires that E[X
t
− X
s
|
F
s
] ≥ 0 a.s.
whenever t ≥ s.
‡
This is due to the denition of the conditioning.
9o`8/ej~|,:w۴FH%pU9#i.9y9Bu2Tg]
2'
QK*)
̱4Lb ]PI=B.5U"{|{6?LȄjXO4OcV?ء+g"O 8xӦZhڛj2%V{,,,B,l_뿼AxA}AUEKtEaBH7qqWQG8ur A1AQxJ9CC ! CfZ
X"'諼+A~St4UD|sX/d}YS`C/xn1]eLr3$;\. -q|膿uw`TA}P`OE%e SV2O%g ?wbHmFR:b!»UD`rRuL i4In}ӬlM#hN Ӯʢ@(2GeU|
0v&땾uUqh{E~Y, 1g{,z=\$ 1V%J.[3da*>,%d_\/~U$^/Etf${c] p3bۈNl7J8! 3Cub 2QBZQU5%; qіO +N]X XˣMǶckJPa: fЂU[9\o!kEzRrzvnH>V03OZo^
v@6 QA/9?4FB #6=V%mGz|0,N U Q6UgWM,. 낻Y.4Y2WNs\Q}W`Ժq9WV^ # q91ׯ_ Ƅx
% "pJ(<*U &8*@Pt1FZ 16 Fun Facts
