Suppose X 1 , … , X n X_1, \ldots, X_n X 1 , … , X n ∣ X i ∣ ≤ M |X_i| \le M ∣ X i ∣ ≤ M E [ X i ] = μ i \mathbb{E} [ X_i ] = \mu_i E [ X i ] = μ i E [ X i 2 ] ≤ v i 2 \mathbb{E} [ X_i^2 ] \le v_i^2 E [ X i 2 ] ≤ v i 2 i i i M M M v i 2 v_i^2 v i 2 V ≐ ∑ i ∈ [ n ] v i 2 V \doteq \sum_{i \in [n] } v_i^2 V ≐ ∑ i ∈ [ n ] v i 2 t ≥ 0 t \ge 0 t ≥ 0
Pr [ ∑ i ∈ [ n ] ( X i − μ i ) ≥ t ] ≤ ( exp ( M t / V ) ( 1 + M t / V ) 1 + M t / V ) V / M 2 = exp ( − t 2 2 V Φ ( M t V ) ) ,
\begin{aligned}
\Pr \left[ \sum_{i \in [n ] } (X_i - \mu_i) \ge t \right]
&\le \left( \frac{ \exp \left( Mt / V \right) }{ \left( 1 + Mt / V \right)^{ 1 + Mt / V } } \right)^{V / M^2} \\
&=\exp \left( - \frac{ t^2 }{ 2 V } \Phi \left( \frac{M t}{V} \right) \right),
\end{aligned}
Pr i ∈ [ n ] ∑ ( X i − μ i ) ≥ t ≤ ( ( 1 + M t / V ) 1 + M t / V exp ( M t / V ) ) V / M 2 = exp ( − 2 V t 2 Φ ( V M t ) ) , where Φ \Phi Φ [ − 1 , ∞ ) [-1, \infty) [ − 1 , ∞ )
Φ ( x ) ≐ ( 1 + x ) ln ( 1 + x ) − x x 2 / 2 for t ≠ 0 , and Φ ( 0 ) = 1.
\Phi (x) \doteq \frac{ (1 + x) \ln (1 + x) - x }{ x^2 / 2 } \quad \text{for } t \neq 0, \text{ and } \Phi(0) = 1.
Φ ( x ) ≐ x 2 /2 ( 1 + x ) ln ( 1 + x ) − x for t = 0 , and Φ ( 0 ) = 1.
Remark: Let's perform a sanity check before proving it. Suppose that X 1 , … , X n X_1, \ldots, X_n X 1 , … , X n μ \mu μ X i ≤ 1 X_i \le 1 X i ≤ 1 E [ X i 2 ] = μ \mathbb{E}[ X_i^2 ] = \mu E [ X i 2 ] = μ V = n μ V = n \mu V = n μ t = ϵ ⋅ n μ t = \epsilon \cdot n \mu t = ϵ ⋅ n μ
Pr [ ∑ i ∈ [ n ] X i − n μ ≥ ϵ ⋅ n μ ] ≤ ( exp ( ϵ ) ( 1 + ϵ ) 1 + ϵ ) n μ ,
\begin{aligned}
\Pr \left[ \sum_{i \in [n ] } X_i - n \mu \ge \epsilon \cdot n \mu \right]
&\le \left( \frac{ \exp \left( \epsilon \right) }{ \left( 1 + \epsilon \right)^{ 1 + \epsilon } } \right)^{ n \mu },
\end{aligned}
Pr i ∈ [ n ] ∑ X i − n μ ≥ ϵ ⋅ n μ ≤ ( ( 1 + ϵ ) 1 + ϵ exp ( ϵ ) ) n μ , which is just the standard Chernoff Bound.
Proof. For all λ ≥ 0 \lambda \ge 0 λ ≥ 0
E [ exp ( λ X i ) ] = 1 + λ μ i + ∑ k ≥ 2 λ k E [ X i k ] k ! = 1 + λ μ i + ∑ k ≥ 2 λ k E [ X i 2 X i k − 2 ] k ! ≤ 1 + λ μ i + E [ X i 2 ] M 2 ⋅ ∑ k ≥ 2 λ k M k k ! since ∣ X i 2 X i k − 2 ∣ ≤ X i 2 M k − 2 ≤ 1 + λ μ i + v i 2 M 2 ⋅ ( e λ M − 1 − λ M ) ≤ exp ( λ μ i + v i 2 M 2 ⋅ ( e λ M − 1 − λ M ) )
\begin{aligned}
\mathbb{E} [ \exp( \lambda X_i ) ]
&= 1 + \lambda \mu_i + \sum_{k \ge 2} \frac{ \lambda^k \mathbb{E} [ X_i^k ] }{ k! } \\
&= 1 + \lambda \mu_i + \sum_{k \ge 2} \frac{ \lambda^k \mathbb{E} [ X_i^2 X_i^{k - 2} ] }{ k! } \\
&\le 1 + \lambda \mu_i + \frac{ \mathbb{E} [ X_i^2 ] }{ M^2 } \cdot \sum_{k \ge 2} \frac{ \lambda^k M^k }{ k! } \quad \text{ since } |X_i^2 X_i^{k - 2}| \le X_i^2 M^{k - 2}\\
&\le 1 + \lambda \mu_i + \frac{ v_i^2 }{ M^2 } \cdot \left( e^{\lambda M} - 1 - \lambda M \right) \\
&\le \exp \left( \lambda \mu_i + \frac{ v_i^2 }{ M^2 } \cdot \left( e^{\lambda M} - 1 - \lambda M \right) \right)
\end{aligned}
E [ exp ( λ X i )] = 1 + λ μ i + k ≥ 2 ∑ k ! λ k E [ X i k ] = 1 + λ μ i + k ≥ 2 ∑ k ! λ k E [ X i 2 X i k − 2 ] ≤ 1 + λ μ i + M 2 E [ X i 2 ] ⋅ k ≥ 2 ∑ k ! λ k M k since ∣ X i 2 X i k − 2 ∣ ≤ X i 2 M k − 2 ≤ 1 + λ μ i + M 2 v i 2 ⋅ ( e λ M − 1 − λ M ) ≤ exp ( λ μ i + M 2 v i 2 ⋅ ( e λ M − 1 − λ M ) ) Therefore,
E [ exp ( λ ( X i − μ i ) ) ] ≤ exp ( v i 2 M 2 ⋅ ( e λ M − 1 − λ M ) ) .
\begin{aligned}
\mathbb{E} [ \exp( \lambda (X_i - \mu_i) ) ]
&\le \exp \left( \frac{ v_i^2 }{ M^2 } \cdot \left( e^{\lambda M} - 1 - \lambda M \right) \right).
\end{aligned}
E [ exp ( λ ( X i − μ i ))] ≤ exp ( M 2 v i 2 ⋅ ( e λ M − 1 − λ M ) ) . Via Markov's inequality,
Pr [ ∑ i ∈ [ n ] ( X i − μ i ) ≥ t ] ≤ E [ exp ( λ ∑ i ∈ [ n ] ( X i − μ i ) ) ] exp ( λ t ) ≤ exp ( − λ t + V M 2 ⋅ ( e λ M − 1 − λ M ) ) = exp ( − λ ( t + V M ) + V M 2 ⋅ ( e λ M − 1 ) )
\begin{aligned}
\Pr \left[ \sum_{i \in [n ] } (X_i - \mu_i) \ge t \right]
&\le
\frac{ \mathbb{E} \left[ \exp \left( \lambda \sum_{i \in [n ] } (X_i - \mu_i) \right) \right] }{ \exp( \lambda t) } \\
&\le \exp \left( -\lambda t + \frac{ V }{ M^2 } \cdot \left( e^{\lambda M} - 1 - \lambda M \right) \right) \\
&= \exp \left( -\lambda \Big( t + \frac{V}{M} \Big) + \frac{ V }{ M^2 } \cdot \left( e^{\lambda M} - 1 \right) \right)
\end{aligned}
Pr i ∈ [ n ] ∑ ( X i − μ i ) ≥ t ≤ exp ( λ t ) E [ exp ( λ ∑ i ∈ [ n ] ( X i − μ i ) ) ] ≤ exp ( − λ t + M 2 V ⋅ ( e λ M − 1 − λ M ) ) = exp ( − λ ( t + M V ) + M 2 V ⋅ ( e λ M − 1 ) ) Let f ( λ ) = − λ t + V M 2 ⋅ ( e λ M − 1 − λ M ) f(\lambda) = -\lambda t + \frac{ V }{ M^2 } \cdot \left( e^{\lambda M} - 1 - \lambda M \right) f ( λ ) = − λ t + M 2 V ⋅ ( e λ M − 1 − λ M )
f ′ ( λ ) = − ( t + V M ) + V M e λ M = 0.
\begin{aligned}
f'(\lambda)
=& - \Big( t + \frac{V}{M} \Big) + \frac{V}{M} e^{\lambda M} = 0.
\end{aligned}
f ′ ( λ ) = − ( t + M V ) + M V e λ M = 0. We get λ = 1 M ln ( M t V + 1 ) \lambda = \frac{1}{M} \ln \left( \frac{M t}{V} + 1 \right) λ = M 1 ln ( V M t + 1 )
Pr [ ∑ i ∈ [ n ] ( X i − μ i ) ≥ t ] ≤ exp ( − 1 M ( t + V M ) ln ( M t V + 1 ) + V M 2 ⋅ M t V ) ≤ exp ( { M t V − ( 1 + M t V ) ln ( 1 + M t V ) } ⋅ V M 2 ) .
\begin{aligned}
\Pr \left[ \sum_{i \in [n ] } (X_i - \mu_i) \ge t \right]
&\le \exp \left( - \frac{1}{M} \Big( t + \frac{V}{M} \Big) \ln \left( \frac{M t}{V} + 1 \right) + \frac{ V }{ M^2 } \cdot \frac{M t}{V} \right) \\
&\le \exp \left( \left\{ \frac{M t}{V} - \Big( 1 + \frac{M t}{V} \Big) \ln \left( 1 + \frac{M t}{V} \right) \right\} \cdot \frac{V}{M^2}\right).
\end{aligned}
Pr i ∈ [ n ] ∑ ( X i − μ i ) ≥ t ≤ exp ( − M 1 ( t + M V ) ln ( V M t + 1 ) + M 2 V ⋅ V M t ) ≤ exp ( { V M t − ( 1 + V M t ) ln ( 1 + V M t ) } ⋅ M 2 V ) . □ \square □
Reference
[1] David Pollard. Chapter 2, MiniEmpirical , 2015. Manuscript
← Back to all notes Back to top ↑