Azuma-Hoeffding Inequality
Let X 0 , … , X n X_0, \ldots, X_n X 0 , … , X n
A k ≤ X k − X k − 1 ≤ B k
A_k \le X_k - X_{k - 1} \le B_k
A k ≤ X k − X k − 1 ≤ B k for some random variables A k A_k A k B k B_k B k X 0 , X 1 , … X k − 1 X_0, X_1, \ldots X_{k - 1} X 0 , X 1 , … X k − 1 B k − A k ≤ c k B_k - A_k \le c_k B k − A k ≤ c k c k c_k c k t ≥ 0 t \ge 0 t ≥ 0 η > 0 \eta > 0 η > 0
Pr [ ∣ X t − X 0 ∣ ≥ η ] ≤ 2 exp ( − 2 η 2 ∑ k ∈ [ t ] c k 2 )
\Pr[ | X_t - X_0 | \ge \eta ] \le 2 \exp \left( - \frac{ 2 \eta^2 }{ \sum_{ k \in [t] } c_k^2 }\right)
Pr [ ∣ X t − X 0 ∣ ≥ η ] ≤ 2 exp ( − ∑ k ∈ [ t ] c k 2 2 η 2 )
Hoeffding's Lemma
Let X X X 0 0 0 a ≤ X ≤ b {\displaystyle a\leq X\leq b} a ≤ X ≤ b λ ∈ R {\displaystyle \lambda \in \mathbb {R} } λ ∈ R
E [ e λ X ] ≤ exp ( λ 2 ( b − a ) 2 8 ) .
{\displaystyle
\mathbb {E} \left[ e^{\lambda X} \right] \le
\exp {\Big (}
{\frac{\lambda^{2}(b-a)^{2}} {8}}
{\Big ) }.
}
E [ e λ X ] ≤ exp ( 8 λ 2 ( b − a ) 2 ) .
Proof. We prove a version with a weaker factor of 1 2 \frac{1}{2} 2 1
First, consider a special case of Rademacher random variable σ \sigma σ − 1 -1 − 1 1 1 1 λ ∈ R \lambda \in \mathbb{R} λ ∈ R
E [ e λ σ ] = e − λ + e λ 2 = ∑ i ≥ 0 λ 2 i ( 2 i ) ! ≤ ∑ i ≥ 0 ( λ 2 / 2 ) i i ! = e λ 2 / 2 .
\begin{aligned}
\mathbb{E} [ e^{ \lambda \sigma} ]
&= \frac{ e^{ - \lambda } + e^{ \lambda } }{ 2 }
&= \sum_{ i \ge 0 } \frac{ \lambda^{ 2i } }{ (2i)! }
&\le \sum_{ i \ge 0 } \frac{ ( \lambda^2 / 2)^i }{ i ! }
&= e^{ \lambda^2 / 2}.
\end{aligned}
E [ e λσ ] = 2 e − λ + e λ = i ≥ 0 ∑ ( 2 i )! λ 2 i ≤ i ≥ 0 ∑ i ! ( λ 2 /2 ) i = e λ 2 /2 . Next, let Y Y Y X X X
E [ e λ X ] = E [ e λ ( X − E [ X ] ) ] = E X [ e λ ( X − E Y [ Y ] ) ] ≤ E X , Y [ e λ ( X − Y ) ]
\begin{aligned}
\mathbb{E} [ e^{ \lambda X }]
&= \mathbb{E} [ e^{ \lambda ( X - \mathbb{E}[ X ] ) }]
&= \mathbb{E}_{X} [ e^{ \lambda ( X - \mathbb{E}_{Y} [ Y ] ) }]
&\le \mathbb{E}_{ X, Y } [ e^{ \lambda ( X - Y ) }]
\end{aligned}
E [ e λ X ] = E [ e λ ( X − E [ X ]) ] = E X [ e λ ( X − E Y [ Y ]) ] ≤ E X , Y [ e λ ( X − Y ) ] Since X X X Y Y Y σ ( X − Y ) \sigma( X - Y) σ ( X − Y ) X − Y X - Y X − Y
E X , Y [ e λ ( X − Y ) ] = E X , Y [ E σ [ e λ ( X − Y ) σ | X , Y ] ] .
\mathbb{E}_{ X, Y } [ e^{ \lambda ( X - Y ) }] = \mathbb{E}_{ X, Y } \left[ \mathbb{E}_\sigma [ e^{ \lambda ( X - Y ) \sigma } \middle\vert X, Y] \right].
E X , Y [ e λ ( X − Y ) ] = E X , Y [ E σ [ e λ ( X − Y ) σ X , Y ] ] . Finally, by previous argument,
E σ [ e λ ( X − Y ) σ ∣ X , Y ] ≤ e λ 2 ( X − Y ) 2 / 2 ≤ e λ 2 ( b − a ) 2 / 2 .
\begin{aligned}
\mathbb{E}_{\sigma } [ e^{ \lambda ( X - Y ) \sigma } \mid X, Y ] \le e^{ \lambda^2 ( X - Y )^2 / 2 } \le e^{ \lambda^2 (b - a)^2 / 2 }.
\end{aligned}
E σ [ e λ ( X − Y ) σ ∣ X , Y ] ≤ e λ 2 ( X − Y ) 2 /2 ≤ e λ 2 ( b − a ) 2 /2 . It concludes that E X , Y [ e λ ( X − Y ) ] ≤ e λ 2 ( b − a ) 2 / 2 \mathbb{E}_{ X, Y } [ e^{ \lambda ( X - Y ) }] \le e^{ \lambda^2 (b - a)^2 / 2 } E X , Y [ e λ ( X − Y ) ] ≤ e λ 2 ( b − a ) 2 /2
□ \square □
Proof of the Theorem
Define Z k = X k − X k − 1 Z_k = X_k - X_{k - 1} Z k = X k − X k − 1 k ∈ [ n ] k \in [n] k ∈ [ n ] X 1 , … , X n X_1, \ldots, X_n X 1 , … , X n
E [ Z k ∣ X 0 , … , X k − 1 ] = 0.
\mathbb{E}[ Z_k \mid X_0, \ldots, X_{k - 1} ] = 0.
E [ Z k ∣ X 0 , … , X k − 1 ] = 0. Via Hoeffding's Lemma , for each k ∈ [ n ] k \in [n] k ∈ [ n ] λ ∈ R \lambda \in \mathbb{R} λ ∈ R
E [ e λ Z t ] ≤ e λ 2 c k 2 / 8 .
\mathbb{E} \left[ e^{\lambda Z_t } \right] \le e^{ \lambda^2 c_k^2 / 8 }.
E [ e λ Z t ] ≤ e λ 2 c k 2 /8 . It follows that
E [ e λ ∑ k ∈ [ t ] Z k ] = E [ E [ e λ ∑ k ∈ [ t ] Z k | Z 1 , … , Z t − 1 ] ] = E [ E [ e λ Z t ] ⋅ E [ e λ ∑ k ∈ [ t − 1 ] Z k | Z 1 , … , Z t − 1 ] ] ≤ e λ 2 c t 2 / 8 ⋅ E [ E [ e λ ∑ k ∈ [ t − 1 ] Z k | Z 1 , … , Z t − 1 ] ]
\begin{aligned}
\mathbb{E} \left[ e^{ \lambda \sum_{k \in [t]} Z_k } \right]
&=\mathbb{E} \left[ \mathbb{E} \left[ e^{ \lambda \sum_{k \in [t] } Z_k } \middle\vert Z_1, \ldots, Z_{t - 1} \right] \right] \\
&=\mathbb{E} \left[ \mathbb{E} \left[ e^{\lambda Z_t } \right] \cdot \mathbb{E} \left[ e^{ \lambda \sum_{k \in [t - 1] } Z_k } \middle\vert Z_1, \ldots, Z_{t - 1} \right] \right] \\
&\le e^{ \lambda^2 c_t^2 / 8 } \cdot \mathbb{E} \left[ \mathbb{E} \left[ e^{ \lambda \sum_{k \in [t - 1] } Z_k } \middle\vert Z_1, \ldots, Z_{t - 1} \right] \right]
\end{aligned}
E [ e λ ∑ k ∈ [ t ] Z k ] = E [ E [ e λ ∑ k ∈ [ t ] Z k Z 1 , … , Z t − 1 ] ] = E [ E [ e λ Z t ] ⋅ E [ e λ ∑ k ∈ [ t − 1 ] Z k Z 1 , … , Z t − 1 ] ] ≤ e λ 2 c t 2 /8 ⋅ E [ E [ e λ ∑ k ∈ [ t − 1 ] Z k Z 1 , … , Z t − 1 ] ] By induction, it holds that
E [ e λ ∑ k ∈ [ t ] Z k ] ≤ e λ 2 ∑ k ∈ [ t ] c k 2 / 8 .
\mathbb{E} \left[ e^{ \lambda \sum_{k \in [t]} Z_k } \right] \le e^{ \lambda^2 \sum_{k \in [t] } c_k^2 / 8 }.
E [ e λ ∑ k ∈ [ t ] Z k ] ≤ e λ 2 ∑ k ∈ [ t ] c k 2 /8 . For all λ > 0 \lambda > 0 λ > 0
Pr [ ∑ k ∈ [ t ] Z k ≥ η ] = Pr [ e λ ∑ k ∈ [ t ] Z k ≥ e λ η ] ≤ E [ e λ ∑ k ∈ [ t ] Z k ] E [ e λ η ] ≤ e λ 2 ∑ k ∈ [ t ] c k 2 / 8 − λ η .
\begin{aligned}
\Pr \left[ \sum_{k \in [t] } Z_k \ge \eta \right]
&= \Pr \left[ e^{ \lambda \sum_{k \in [t] } Z_k } \ge e^{ \lambda \eta } \right] \\
&\le \frac{ \mathbb{E} \left[ e^{ \lambda \sum_{k \in [t]} Z_k } \right] }{ \mathbb{E}[ e^{ \lambda \eta } ] } \\
&\le e^{ \lambda^2 \sum_{k \in [t] } c_k^2 / 8 - \lambda \eta }.
\end{aligned}
Pr k ∈ [ t ] ∑ Z k ≥ η = Pr [ e λ ∑ k ∈ [ t ] Z k ≥ e λ η ] ≤ E [ e λ η ] E [ e λ ∑ k ∈ [ t ] Z k ] ≤ e λ 2 ∑ k ∈ [ t ] c k 2 /8 − λ η . When λ = 4 η ∑ k ∈ [ t ] c k 2 \lambda = \frac{4 \eta}{ \sum_{k \in [t] } c_k^2 } λ = ∑ k ∈ [ t ] c k 2 4 η
exp { 2 η 2 ∑ k ∈ [ t ] c k 2 − 4 η 2 ∑ k ∈ [ t ] c k 2 } = exp { − 2 η 2 ∑ k ∈ [ t ] c k 2 } .
\exp \left\{ \frac{2 \eta^2 }{ \sum_{k \in [t] } c_k^2 } - \frac{4 \eta^2 }{ \sum_{k \in [t] } c_k^2 } \right\} = \exp \left\{ - \frac{2 \eta^2 }{ \sum_{k \in [t] } c_k^2 } \right\}.
exp { ∑ k ∈ [ t ] c k 2 2 η 2 − ∑ k ∈ [ t ] c k 2 4 η 2 } = exp { − ∑ k ∈ [ t ] c k 2 2 η 2 } . □ \square □
Hoeffding's Lemma Proof 1 Suppose that b ≠ a b \neq a b = a X X X
θ = − a b − a = 1 − b b − a ∈ ( 0 , 1 ) \theta = - \frac{a}{b - a} = 1 - \frac{b}{b - a} \in (0, 1) θ = − b − a a = 1 − b − a b ∈ ( 0 , 1 ) c = ( b − a ) > 0 c = (b - a) > 0 c = ( b − a ) > 0
By Jensen's inequality,
E [ e λ X ] = E [ exp ( b − X b − a ⋅ λ a + X − a b − a ⋅ λ b ) ] ≤ E [ b − X b − a ⋅ exp ( λ a ) + X − a b − a ⋅ exp ( λ b ) ] = ( 1 − θ ) ⋅ exp ( λ a ) + θ ⋅ exp ( λ b ) = ( 1 − θ + θ e λ ( b − a ) ) exp ( λ a ) = ( 1 − θ + θ e ( λ c ) ) e − θ ( λ c )
\begin{aligned}
\mathbb{E} [ e^{\lambda X } ]
&= \mathbb{E} \left[ \exp \left( \frac{b - X}{ b - a} \cdot \lambda a + \frac{X - a}{b - a} \cdot \lambda b \right) \right] \\
&\le \mathbb{E} \left[ \frac{b - X}{ b - a} \cdot \exp \left( \lambda a \right) + \frac{X - a}{b - a} \cdot \exp \left( \lambda b \right) \right] \\
&= (1 - \theta) \cdot \exp \left( \lambda a \right) + \theta \cdot \exp \left( \lambda b \right) \\
&= \left( 1 - \theta + \theta e^{\lambda (b - a)} \right) \exp \left( \lambda a \right) \\
&= \left( 1 - \theta + \theta e^{ (\lambda c) } \right) e^ { - \theta (\lambda c) }
\end{aligned}
E [ e λ X ] = E [ exp ( b − a b − X ⋅ λa + b − a X − a ⋅ λb ) ] ≤ E [ b − a b − X ⋅ exp ( λa ) + b − a X − a ⋅ exp ( λb ) ] = ( 1 − θ ) ⋅ exp ( λa ) + θ ⋅ exp ( λb ) = ( 1 − θ + θ e λ ( b − a ) ) exp ( λa ) = ( 1 − θ + θ e ( λ c ) ) e − θ ( λ c ) Let f ( z ) ≐ − θ z + ln ( 1 − θ + θ e z ) f(z) \doteq - \theta z + \ln \left( 1 - \theta + \theta e^{ z} \right) f ( z ) ≐ − θ z + ln ( 1 − θ + θ e z ) 1 − θ + θ e z > 0 1 - \theta + \theta e^{ z} > 0 1 − θ + θ e z > 0 z ∈ R z \in \mathbb{R} z ∈ R
exp { f ( λ c ) } = ( 1 − θ + θ e λ c ) exp ( − λ θ c ) .
\exp \Big \{ f(\lambda c) \Big \} = \left( 1 - \theta + \theta e^{\lambda c } \right) \exp \left( - \lambda \theta c \right).
exp { f ( λ c ) } = ( 1 − θ + θ e λ c ) exp ( − λ θ c ) . Further,
f ′ ( z ) = − θ + θ e z 1 − θ + θ e z ,
f'(z) = - \theta + \frac{ \theta e^{ z} }{ 1 - \theta + \theta e^{ z} },
f ′ ( z ) = − θ + 1 − θ + θ e z θ e z , and
f ′ ′ ( z ) = θ e z ( 1 − θ + θ e z ) − ( θ e z ) 2 ( 1 − θ + θ e z ) 2 = ( 1 − θ ) θ e z ( 1 − θ + θ e z ) 2 ≤ 1 4 .
f''(z)
= \frac{ \theta e^{ z} ( 1 - \theta + \theta e^{ z} ) - ( \theta e^z )^2 }{ ( 1 - \theta + \theta e^{ z} )^2 }
= \frac{ ( 1 - \theta ) \theta e^{ z} }{ ( 1 - \theta + \theta e^{ z} )^2 }
\le \frac{1}{4}.
f ′′ ( z ) = ( 1 − θ + θ e z ) 2 θ e z ( 1 − θ + θ e z ) − ( θ e z ) 2 = ( 1 − θ + θ e z ) 2 ( 1 − θ ) θ e z ≤ 4 1 . Finally, by Taylor's expansion, there exists some z ∗ ∈ [ 0 , λ c ] z^* \in [0, \lambda c] z ∗ ∈ [ 0 , λ c ]
f ( λ c ) = f ( 0 ) + f ′ ( 0 ) ⋅ ( λ c ) + f ′ ′ ( z ∗ ) 2 ( λ c ) 2 = f ′ ′ ( z ∗ ) 2 ( λ c ) 2 ≤ 1 8 ( λ c ) 2 = λ 2 ( b − a ) 2 8 .
\begin{aligned}
f(\lambda c)
&= f(0) + f' (0) \cdot (\lambda c) + \frac{ f''(z^*) }{ 2 } (\lambda c)^2 \\
&= \frac{ f''(z^*) }{ 2 } (\lambda c)^2 \\
&\le \frac{1}{8 } (\lambda c)^2 \\
&= \frac{ \lambda^2 (b - a)^2 }{8 }.
\end{aligned}
f ( λ c ) = f ( 0 ) + f ′ ( 0 ) ⋅ ( λ c ) + 2 f ′′ ( z ∗ ) ( λ c ) 2 = 2 f ′′ ( z ∗ ) ( λ c ) 2 ≤ 8 1 ( λ c ) 2 = 8 λ 2 ( b − a ) 2 .
The picture above shows that the bound might not be tight.
□ \square □
Proof 2 Preliminaries
The proof relies on the following lemma.
Lemma. Let ( Ω , F , P ) (\Omega, \mathcal{F}, \mathbb{P}) ( Ω , F , P ) Y Y Y F \mathcal{F} F μ \mu μ
μ ( A ) ≐ ∫ A Y d P , A ∈ F .
\mu(A) \doteq \int_A Y \, d\,\mathbb{P}, \qquad A \in \mathcal{F}.
μ ( A ) ≐ ∫ A Y d P , A ∈ F . Then for nonnegative F \mathcal{F} F Z Z Z
∫ Z d μ = ∫ Z ⋅ Y d P .
\int Z \, d\, \mu = \int Z \cdot Y \, d\, \mathbb{P}.
∫ Z d μ = ∫ Z ⋅ Y d P .
Proof of the Lemma. If Z Z Z 1 A 1_A 1 A A ∈ F A \in \mathcal{F} A ∈ F Z Z Z { Z n } \{ Z_n \} { Z n } Z n ↑ Z Z_n \uparrow Z Z n ↑ Z
lim n ∫ Z n d μ = ∫ Z d μ , lim n ∫ Z n ⋅ Y d P = ∫ Z ⋅ Y d P .
\lim_n \int Z_n \, d\, \mu = \int Z \, d\, \mu, \\
\lim_n \int Z_n \cdot Y \, d\, \mathbb{P} = \int Z \cdot Y \, d\, \mathbb{P}.
n lim ∫ Z n d μ = ∫ Z d μ , n lim ∫ Z n ⋅ Y d P = ∫ Z ⋅ Y d P . ■ \blacksquare ■
Let X X X a ≤ X ≤ b a \le X \le b a ≤ X ≤ b f : R ≥ 0 → R f: \mathbb{R}_{\ge 0} \rightarrow \mathbb{R} f : R ≥ 0 → R
f ( λ ) = E [ exp ( λ X ) ] ,
f(\lambda) = \mathbb{E}[\exp(\lambda X)],\,
f ( λ ) = E [ exp ( λ X )] , and let
h ( λ ) = ln f ( λ ) .
h(\lambda) = \ln f(\lambda).
h ( λ ) = ln f ( λ ) . We will justify the interchange of differentiation and expectation, and show that
f ′ ( λ ) = E [ X exp ( λ X ) ] , f ′ ′ ( λ ) = E [ X 2 exp ( λ X ) ] .
f'(\lambda) = \mathbb{E}\left[ X \exp ( \lambda X) \right],\, \\
f''(\lambda) = \mathbb{E}\left[ X^2 \exp ( \lambda X) \right].
f ′ ( λ ) = E [ X exp ( λ X ) ] , f ′′ ( λ ) = E [ X 2 exp ( λ X ) ] . Therefore,
h ′ ( λ ) = f ′ ( λ ) f ( λ ) = E [ X exp ( λ X ) ] E [ exp ( λ X ) ] , h ′ ′ ( λ ) = f ′ ′ ( λ ) ⋅ f ( λ ) − ( f ′ ( λ ) ) 2 ( f ( λ ) ) 2 = E [ X 2 exp ( λ X ) ] ⋅ E [ exp ( λ X ) ] − ( E [ X exp ( λ X ) ] ) 2 ( E [ exp ( λ X ) ] ) 2 = E [ X 2 exp ( λ X ) ] E [ exp ( λ X ) ] − ( E [ X exp ( λ X ) ] ) 2 ( E [ exp ( λ X ) ] ) 2 .
\begin{aligned}
h'(\lambda)
&= \frac{ f'(\lambda) }{ f(\lambda) }
= \frac{ \mathbb{E}\left[ X \exp ( \lambda X) \right] }{ \mathbb{E}[\exp(\lambda X)] }\,, \\
h''(\lambda)
&= \frac{ f''(\lambda) \cdot f(\lambda) - \left( f'(\lambda) \right)^2 }{ \left( f(\lambda) \right)^2 } \\
&= \frac{ \mathbb{E}[X^2 \exp(\lambda X)] \cdot \mathbb{E}[\exp(\lambda X)] - \left( \mathbb{E}[ X \exp(\lambda X)] \right)^2 }{ \left( \mathbb{E}[\exp(\lambda X)] \right)^2 } \\
&= \frac{ \mathbb{E}[X^2 \exp(\lambda X)] }{ \mathbb{E}[\exp(\lambda X)] } - \frac{ \left( \mathbb{E}[ X \exp(\lambda X)] \right)^2 }{ \left( \mathbb{E}[\exp(\lambda X)] \right)^2 }.
\end{aligned}
h ′ ( λ ) h ′′ ( λ ) = f ( λ ) f ′ ( λ ) = E [ exp ( λ X )] E [ X exp ( λ X ) ] , = ( f ( λ ) ) 2 f ′′ ( λ ) ⋅ f ( λ ) − ( f ′ ( λ ) ) 2 = ( E [ exp ( λ X )] ) 2 E [ X 2 exp ( λ X )] ⋅ E [ exp ( λ X )] − ( E [ X exp ( λ X )] ) 2 = E [ exp ( λ X )] E [ X 2 exp ( λ X )] − ( E [ exp ( λ X )] ) 2 ( E [ X exp ( λ X )] ) 2 . Suppose ( Ω , F , P ) (\Omega, \mathcal{F}, \mathbb{P}) ( Ω , F , P ) X X X X X X F \mathcal{F} F R \mathbb{R} R P λ : F → R \mathbb{P}_\lambda: \mathcal{F} \rightarrow \mathbb{R} P λ : F → R
P λ ( A ) ≐ ∫ A exp ( λ X ) E [ exp ( λ X ) ] d P , ∀ A ∈ F .
\mathbb{P}_{\lambda}(A) \doteq \int_A \frac{\exp(\lambda X)}{ \mathbb{E}[\exp(\lambda X)] } \, d \mathbb{P}, \quad \forall A \in \mathcal{F}.
P λ ( A ) ≐ ∫ A E [ exp ( λ X )] exp ( λ X ) d P , ∀ A ∈ F . It is easy to see that P λ \mathbb{P}_{\lambda} P λ δ ( λ ) ≐ exp ( λ X ) E [ exp ( λ X ) ] \delta(\lambda) \doteq \frac{\exp(\lambda X)}{ \mathbb{E}[\exp(\lambda X)] } δ ( λ ) ≐ E [ e x p ( λ X )] e x p ( λ X ) P λ \mathbb{P}_{\lambda} P λ
E λ [ X ] ≐ ∫ X d P λ = ∫ X exp ( λ X ) E [ exp ( λ X ) ] d P = E [ X exp ( λ X ) ] E [ exp ( λ X ) ] , E λ [ X 2 ] ≐ ∫ X 2 d P λ = ∫ X 2 exp ( λ X ) E [ exp ( λ X ) ] d P = E [ X 2 exp ( λ X ) ] E [ exp ( λ X ) ] .
\begin{aligned}
\mathbb{E}_{\lambda} [X] \doteq \int X d { \mathbb{P}_{\lambda} }
&= \int X \frac{\exp(\lambda X)}{ \mathbb{E}[\exp(\lambda X)] } \, d \mathbb{P}
= \frac{ \mathbb{E}\left[ X \exp ( \lambda X) \right] }{ \mathbb{E}[\exp(\lambda X)] }\,, \\
\mathbb{E}_{\lambda} [X^2] \doteq \int X^2 d { \mathbb{P}_{\lambda} }
&= \int X^2 \frac{\exp(\lambda X)}{ \mathbb{E}[\exp(\lambda X)] } \, d \mathbb{P}
= \frac{ \mathbb{E}\left[ X^2 \exp ( \lambda X) \right] }{ \mathbb{E}[\exp(\lambda X)] }\,.
\end{aligned}
E λ [ X ] ≐ ∫ X d P λ E λ [ X 2 ] ≐ ∫ X 2 d P λ = ∫ X E [ exp ( λ X )] exp ( λ X ) d P = E [ exp ( λ X )] E [ X exp ( λ X ) ] , = ∫ X 2 E [ exp ( λ X )] exp ( λ X ) d P = E [ exp ( λ X )] E [ X 2 exp ( λ X ) ] . It follows that
h ′ ′ ( λ ) = V a r λ [ X ] ≐ E λ [ X 2 ] − ( E λ [ X ] ) 2 .
\begin{aligned}
h''(\lambda)
=\mathbb{Var}_{\lambda} [ X ]
\doteq \mathbb{E}_{\lambda} [X^2] - \big( \mathbb{E}_{\lambda} [X] \big)^2.
\end{aligned}
h ′′ ( λ ) = V a r λ [ X ] ≐ E λ [ X 2 ] − ( E λ [ X ] ) 2 . Therefore,
V a r λ [ X ] = V a r λ [ X − a + b 2 ] = E λ [ ( X − a + b 2 ) 2 ] ≤ ( b − a ) 2 4 .
\mathbb{Var}_{\lambda} [ X ] = \mathbb{Var}_{\lambda} \left[ X - \frac{a + b}{2} \right] = \mathbb{E}_{\lambda} \left[ \left( X - \frac{a + b}{2} \right)^2 \right] \le \frac{(b - a)^2}{4}.
V a r λ [ X ] = V a r λ [ X − 2 a + b ] = E λ [ ( X − 2 a + b ) 2 ] ≤ 4 ( b − a ) 2 . Finally, via Taylor's expansion,
h ( λ ) = h ( 0 ) + λ ⋅ h ′ ( 0 ) + λ 2 2 h ′ ′ ( λ ∗ ) .
h(\lambda) = h(0) + \lambda \cdot h'(0) + \frac{\lambda^2}{2} h''(\lambda^*).
h ( λ ) = h ( 0 ) + λ ⋅ h ′ ( 0 ) + 2 λ 2 h ′′ ( λ ∗ ) . Since h ( 0 ) = 0 h(0) = 0 h ( 0 ) = 0 h ′ ( 0 ) = E [ X ] = 0 h'(0) = \mathbb{E}[X] = 0 h ′ ( 0 ) = E [ X ] = 0 h ′ ′ ( λ ∗ ) = V a r λ ∗ [ X ] ≤ ( b − a ) 2 / 4 h''(\lambda^*) = \mathbb{Var}_{\lambda^*}[X] \le (b - a)^2 / 4 h ′′ ( λ ∗ ) = V a r λ ∗ [ X ] ≤ ( b − a ) 2 /4
h ( λ ) ≤ ( b − a ) 2 8 .
h(\lambda) \le \frac{ (b - a)^2 }{ 8 }.
h ( λ ) ≤ 8 ( b − a ) 2 . First Derivative of f f f
Denote M ≐ max { ∣ a ∣ , ∣ b ∣ } M \doteq \max\{ |a|, |b| \} M ≐ max { ∣ a ∣ , ∣ b ∣ } n ∈ N + n \in \mathbb{N}_+ n ∈ N +
g ( n ) ≐ f ( λ + 1 / n ) − f ( λ ) 1 / n = E [ exp ( ( λ + 1 / n ) ⋅ X ) − exp ( λ X ) 1 / n ]
g(n)
\doteq \frac{ f(\lambda + 1 / n) - f(\lambda) }{ 1 / n}
= \mathbb{E}\left[ \frac{ \exp( (\lambda + 1 / n) \cdot X) - \exp(\lambda X) }{ 1 / n} \right]
g ( n ) ≐ 1/ n f ( λ + 1/ n ) − f ( λ ) = E [ 1/ n exp (( λ + 1/ n ) ⋅ X ) − exp ( λ X ) ] Via mean value theorem, there exists λ ′ ∈ [ λ , λ + 1 / n ] \lambda' \in [\lambda, \lambda + 1 / n] λ ′ ∈ [ λ , λ + 1/ n ]
exp ( ( λ + 1 / n ) ⋅ X ) − exp ( λ X ) 1 / n = X ⋅ exp ( λ ′ ⋅ X ) ≤ M ⋅ exp ( ( λ + 1 ) ⋅ M ) .
\frac{ \exp( (\lambda + 1 / n) \cdot X) - \exp(\lambda X) }{ 1 / n}
= X \cdot \exp ( \lambda' \cdot X)
\le M \cdot \exp( (\lambda + 1) \cdot M).
1/ n exp (( λ + 1/ n ) ⋅ X ) − exp ( λ X ) = X ⋅ exp ( λ ′ ⋅ X ) ≤ M ⋅ exp (( λ + 1 ) ⋅ M ) . Since the RHS is integrable, via dominated convergence theorem,
f ′ ( λ ) = lim n g ( n ) = E [ lim n exp ( ( λ + 1 / n ) ⋅ X ) − exp ( λ X ) 1 / n ] = E [ X exp ( λ X ) ] .
f'(\lambda)
= \lim_n g(n)
= \mathbb{E}\left[ \lim_n \frac{ \exp( (\lambda + 1 / n) \cdot X) - \exp(\lambda X) }{ 1 / n} \right]
= \mathbb{E}\left[ X \exp ( \lambda X) \right] .
f ′ ( λ ) = n lim g ( n ) = E [ n lim 1/ n exp (( λ + 1/ n ) ⋅ X ) − exp ( λ X ) ] = E [ X exp ( λ X ) ] . Second Derivative of f f f
Similarly, for each n ∈ N n \in \mathbb{N} n ∈ N λ ′ ∈ [ λ , λ + 1 / n ] \lambda' \in [\lambda, \lambda + 1 / n] λ ′ ∈ [ λ , λ + 1/ n ]
X ⋅ exp ( ( λ + 1 / n ) ⋅ X ) − X ⋅ exp ( λ X ) 1 / n = X 2 ⋅ exp ( λ ′ ⋅ X ) ≤ M 2 ⋅ exp ( ( λ + 1 ) ⋅ M ) .
\frac{ X \cdot \exp( (\lambda + 1 / n) \cdot X) - X \cdot \exp(\lambda X) }{ 1 / n}
= X^2 \cdot \exp ( \lambda' \cdot X)
\le M^2 \cdot \exp( (\lambda + 1) \cdot M).
1/ n X ⋅ exp (( λ + 1/ n ) ⋅ X ) − X ⋅ exp ( λ X ) = X 2 ⋅ exp ( λ ′ ⋅ X ) ≤ M 2 ⋅ exp (( λ + 1 ) ⋅ M ) . It follows via dominated convergence theorem that
f ′ ′ ( λ ) = lim n E [ X ⋅ exp ( ( λ + 1 / n ) ⋅ X ) − X ⋅ exp ( λ X ) 1 / n ] = E [ lim n X ⋅ exp ( ( λ + 1 / n ) ⋅ X ) − X ⋅ exp ( λ X ) 1 / n ] = E [ X 2 exp ( λ X ) ] .
\begin{aligned}
f''(\lambda)
&= \lim_n \mathbb{E}\left[ \frac{ X \cdot \exp( (\lambda + 1 / n) \cdot X) - X \cdot \exp(\lambda X) }{ 1 / n} \right] \\
&= \mathbb{E}\left[ \lim_n \frac{ X \cdot \exp( (\lambda + 1 / n) \cdot X) - X \cdot \exp(\lambda X) }{ 1 / n} \right] \\
&= \mathbb{E}\left[ X^2 \exp ( \lambda X) \right] .
\end{aligned}
f ′′ ( λ ) = n lim E [ 1/ n X ⋅ exp (( λ + 1/ n ) ⋅ X ) − X ⋅ exp ( λ X ) ] = E [ n lim 1/ n X ⋅ exp (( λ + 1/ n ) ⋅ X ) − X ⋅ exp ( λ X ) ] = E [ X 2 exp ( λ X ) ] . □ \square □
← Back to all notes Back to top ↑ 