36
5.3 Azuma’s Inequality for Martingales
Theorem 5.3.3 Azuma's Inequality Let Zn, n ≥ 1 be a martingale with mean μ = E[ Z n ]. Let Z 0 = μ and suppose that for nonnegative constants α i , βi , i ≥ 1,
E[ f ( X )] ≤
β α +β
f (−α ) +
α α +β
f (β )
30
5.3 Azuma’s Inequality for Martingales
Proof: Since f is convex it follows that, in the region −α ≤ x ≤ β , it is never above the line segment connecting the points (−α , f (−α )) and ( β , f ( β )) . (See Figure 5.3.1.)
f (α , β ) = e β + e − β + α (e β − e − β ) − 2 exp{αβ + β 2 / 2}
would assume a strictly positive maximum in the interior of the Region R = {(α , β ) :| α |≤ 1,| β |≤ 100}. Setting the partial derivatives of f equal to 0,évy
5
Joseph Doob
6
5.0 Martingales origins
7
5.1 Martingale
Definiton:
8
5.1 Martingale
Remark:
9
5.1 Martingale ,
10
5.1 Martingale
11
5.1 Martingale ,
STOCHASTIC PROCESSES AND ITS APPLICATIONS
Prof. Xia Yuanqing School of Automation Beijing Institute of Technology E-mail:yuanqing.xia@ Assistant Dai Li School of Automation Beijing Institute of Technology E-mail:daili1887@
33
5.3 Azuma’s Inequality for Martingales
Now the preceding inequality is true when α = −1 or +1 and when β is large (say when | β |≥ 100 ). Thus, if Lemma 5.3.2 were false, then the function
Proposition:
18
5.2 Stopping Times
19
5.2 Stopping Times
20
5.2 Stopping Times
21
5.2 Stopping Times
22
5.2 Stopping Times
Theorem:
23
5.2 Stopping Times
24
5.2 Stopping Times
or, expanding in a Taylor series,
β 2i +1 /(2i )! =∑ β 2i +1 /(2i + 1)! ∑
i =0 i =0
∞
∞
xi ex = ∑ i =0 i !
∞
which is clearly not possible when β ≠ 0 . Hence, if the lemma is not true, we can conclude that the strictly positive maximal value of f (α , β ) occurs when β = 0 . However, f (α , 0) = 0 and thus the lemma is proven.
3
5.0 Martingales origins
The concept of martingale in probability theory was introduced by Paul Pierre Levy, and much of the original development of the theory was done by Joseph Leo Doob among others. Part of the motivation for that work was to show the impossibility of successful betting strategies. This is the essence of the Martingale.
E[ f ( X )] ≤
E [X] = 0
f ( β ).
32
β α +β
f (−α ) +
α α +β
5.3 Azuma’s Inequality for Martingales
Lemma 5.3.2 For 0 ≤ θ ≤ 1
θe
(1−θ ) x
+ (1 − θ )e
−θ x
≤e
x2 / 8
Proof: Letting θ = (1 + α ) / 2 and x = 2 β , we must show that for −1 ≤ α ≤ 1 ,
(1 + α )e
β (1−α )
+ (1 − α )e
− β (1+α )
≤ 2e
β2 /2
or, equivalently,
e β + e − β + α (e β − e− β ) ≤ 2 exp{αβ + β 2 / 2}.
α α +β
f (β ) +
1 [ f ( β ) − f (−α )]x α +β
it follows, since −α ≤ X ≤ β , that
f (X ) ≤
β α +β
f (−α ) +
α α +β
f (β ) +
1 [ f ( β ) − f (−α )] X . α +β
Taking expectations gives the result, that is,
12
5.1 Martingale ,
Why?
= E[ Z n | Z1 , L , Z n ] = Zn .
13
5.1 Martingale
Why?
14
5.1 Martingale
15
5.1 Martingale
16
5.2 Stopping Times
Definiton:
17
5.2 Stopping Times
35
5.3 Azuma’s Inequality for Martingales
We just consider that α ≠ 0 when β ≠ 0 . We can see that
e β + e− β α 1+ α β = 1 + . ⇒ β (e β + e − β ) = e β − e − β e − e− β β
∂f (α , β ) = 0 ⇒ e β − e − β + α (e β + e − β ) = 2(α + β ) exp{αβ + β 2 / 2} [1] ∂β ∂f (α , β ) = 0 ⇒ e β − e − β = 2 β exp{αβ + β 2 / 2} [2] ∂α
34
5.3 Azuma’s Inequality for Martingales
Figure. 5.3.1
31
5.3 Azuma’s Inequality for Martingales
As the formula for this line segment is
y − f ( β ) y − f (−α ) = x−β x − (−α ) ⇔ y=
β α +β
f (−α ) +
1
Chapter 5
Martingales
2
5.0 Martingales origins
Originally, martingale referred to a class of betting strategies that was popular in 18th century France. The simplest of these strategies was designed for a game in which the gambler wins his stake if a coin comes up heads and loses it if the coin comes up tails. The strategy had the gambler double his bet after every loss so that the first win would recover all previous losses plus win a profit equal to the original stake. As the gambler's wealth and available time jointly approach infinity, his probability of eventually flipping heads approaches 1, which makes the martingale betting strategy seem like a sure thing. However, the exponential growth of the bets eventually bankrupts its users.