We discuss deviation bounds for Poisson random variables. A random variable X X X μ \mu μ n ≥ 0 n \ge 0 n ≥ 0
Pr [ X = n ] = exp ( − μ ) ⋅ μ n n ! .
\Pr[ X = n] = \exp( -\mu ) \cdot \frac{ \mu^n }{ n! }.
Pr [ X = n ] = exp ( − μ ) ⋅ n ! μ n . The bounds share similar forms to the Chernoff bound for independent Bernoulli random variables.
Chernoff Bound. Let X 1 , … , X n X_1, \ldots, X_n X 1 , … , X n Pr [ X i = 1 ] = μ i \Pr[ X_i = 1] = \mu_i Pr [ X i = 1 ] = μ i X = ∑ i ∈ [ n ] X i X = \sum_{i \in [n] } X_i X = ∑ i ∈ [ n ] X i μ = E [ X i ] \mu = \mathbb{E} [ X_i ] μ = E [ X i ]
For all δ > 0 \delta > 0 δ > 0
Pr [ X ≥ ( 1 + δ ) μ ] ≤ ( e δ ( 1 + δ ) 1 + δ ) μ ;
\Pr[ X \ge (1 + \delta) \mu ] \le \left( \frac{ e^\delta }{ (1 + \delta )^{1 + \delta} } \right)^\mu;
Pr [ X ≥ ( 1 + δ ) μ ] ≤ ( ( 1 + δ ) 1 + δ e δ ) μ ;
For all δ ∈ ( 0 , 1 ) \delta \in (0, 1) δ ∈ ( 0 , 1 )
Pr [ X ≤ ( 1 − δ ) μ ] ≤ ( e − δ ( 1 − δ ) 1 − δ ) μ .
\Pr[ X \le (1 - \delta) \mu ] \le \left( \frac{ e^{- \delta } }{ (1 - \delta )^{1 - \delta} } \right)^\mu.
Pr [ X ≤ ( 1 − δ ) μ ] ≤ ( ( 1 − δ ) 1 − δ e − δ ) μ .
Moment Generating Function
Let X X X μ \mu μ s > 0 s > 0 s > 0
E [ exp ( s X ) ] = e ( e s − 1 ) μ .
\begin{aligned}
\mathbb{E} [ \exp( s X ) ]
= e^{ ( e^s - 1 ) \mu }.
\end{aligned}
E [ exp ( s X )] = e ( e s − 1 ) μ .
Proof.
For all s > 0 s > 0 s > 0
E [ exp ( s X ) ] = ∑ n e s n e − μ μ n n ! = e − μ ∑ n ( e s ⋅ μ ) n n ! = e − μ + e s μ = e ( e s − 1 ) μ .
\begin{aligned}
\mathbb{E} [ \exp( s X ) ]
= \sum_n e^{ sn } e^{- \mu } \frac{ \mu^n }{ n! }
= e^{- \mu } \sum_n \frac{ (e^s \cdot \mu)^n }{ n! }
= e^{- \mu + e^s \mu }
= e^{ ( e^s - 1 ) \mu }.
\end{aligned}
E [ exp ( s X )] = n ∑ e s n e − μ n ! μ n = e − μ n ∑ n ! ( e s ⋅ μ ) n = e − μ + e s μ = e ( e s − 1 ) μ . □ \square □
Upper Bound
Let X X X μ \mu μ η ≥ 0 \eta \ge 0 η ≥ 0
Pr [ X ≥ μ + η ] ≤ ( exp ( η μ ) ( 1 + η μ ) 1 + η μ ) μ ≤ exp ( − η 2 2 μ + η ) .
\Pr[ X \ge \mu + \eta ]
\le \left( \frac{ \exp \Big( \frac{\eta}{ \mu} \Big) }{ \Big( 1 + \frac{ \eta }{ \mu } \Big)^{ 1 + \frac{ \eta }{ \mu } } } \right)^\mu
\le \exp \left( - \frac{ \eta^2 }{ 2 \mu + \eta } \right).
Pr [ X ≥ μ + η ] ≤ ( 1 + μ η ) 1 + μ η exp ( μ η ) μ ≤ exp ( − 2 μ + η η 2 ) .
Proof. Via Markov's inequality, for all s > 0 , η ≥ 0 s > 0, \eta \ge 0 s > 0 , η ≥ 0
Pr [ X ≥ μ + η ] = Pr [ exp ( s X ) ≥ exp ( s ( μ + η ) ) ] ≤ E [ exp ( s X ) ] exp ( s ( μ + η ) ) = exp ( ( e s − 1 ) μ − ( s ( μ + η ) ) ) . \small
\begin{aligned}
\Pr[ X \ge \mu + \eta ]
&= \Pr \Big[ \exp( s X ) \ge \exp \big( s ( \mu + \eta) \big) \Big] \\
&\le \frac{ \mathbb{E} [ \exp( s X ) ] }{ \exp \big( s ( \mu + \eta) \big) } \\
&= \exp \Big( ( e^s - 1 ) \mu - \big( s ( \mu + \eta) \big) \Big).
\end{aligned}
Pr [ X ≥ μ + η ] = Pr [ exp ( s X ) ≥ exp ( s ( μ + η ) ) ] ≤ exp ( s ( μ + η ) ) E [ exp ( s X )] = exp ( ( e s − 1 ) μ − ( s ( μ + η ) ) ) . Define f ( s ) = ( e s − 1 ) μ − ( s ( μ + η ) ) f(s) = ( e^s - 1 ) \mu - \big( s ( \mu + \eta) \big) f ( s ) = ( e s − 1 ) μ − ( s ( μ + η ) )
f ′ ( s ) = μ e s − ( μ + η ) = 0 ,
f'(s) = \mu e^s - (\mu + \eta) = 0,
f ′ ( s ) = μ e s − ( μ + η ) = 0 , we get s = ln μ + η μ s = \ln \frac{\mu + \eta}{ \mu} s = ln μ μ + η
Pr [ X ≥ μ + η ] ≤ exp ( ( μ + η μ − 1 ) ⋅ μ − ( μ + η ) ⋅ ln μ + η μ ) = exp ( − μ { − η μ + ( 1 + η μ ) ⋅ ln ( 1 + η μ ) } ) = ( exp ( η μ ) ( 1 + η μ ) 1 + η μ ) μ . \small
\begin{aligned}
\Pr[ X \ge \mu + \eta ]
&\le \exp \left( \Big( \frac{\mu + \eta}{ \mu} - 1 \Big) \cdot \mu - ( \mu + \eta) \cdot \ln \frac{\mu + \eta}{ \mu} \right) \\
&= \exp \left( - \mu \left\{ - \frac{\eta}{ \mu} + \Big( 1 + \frac{ \eta }{ \mu } \Big) \cdot \ln \Big( 1 + \frac{ \eta }{ \mu } \Big) \right\} \right) \\
&= \left( \frac{ \exp \Big( \frac{\eta}{ \mu} \Big) }{ \Big( 1 + \frac{ \eta }{ \mu } \Big)^{ 1 + \frac{ \eta }{ \mu } } } \right)^\mu.
\end{aligned}
Pr [ X ≥ μ + η ] ≤ exp ( ( μ μ + η − 1 ) ⋅ μ − ( μ + η ) ⋅ ln μ μ + η ) = exp ( − μ { − μ η + ( 1 + μ η ) ⋅ ln ( 1 + μ η ) } ) = ( 1 + μ η ) 1 + μ η exp ( μ η ) μ . Next, we prove the inequality of
( exp ( η μ ) ( 1 + η μ ) 1 + η μ ) μ ≤ exp ( − η 2 2 μ + η ) .
\left( \frac{ \exp \Big( \frac{\eta}{ \mu} \Big) }{ \Big( 1 + \frac{ \eta }{ \mu } \Big)^{ 1 + \frac{ \eta }{ \mu } } } \right)^\mu
\le
\exp \left( - \frac{ \eta^2 }{ 2 \mu + \eta } \right).
( 1 + μ η ) 1 + μ η exp ( μ η ) μ ≤ exp ( − 2 μ + η η 2 ) . Let t = η μ ≥ 0 t = \frac{\eta}{\mu} \ge 0 t = μ η ≥ 0
( 1 + t ) ln ( 1 + t ) − t ≥ t 2 2 + t .
\begin{aligned}
(1 + t) \ln (1 + t) - t &\ge \frac{ t^2 }{ 2 + t }.
\end{aligned}
( 1 + t ) ln ( 1 + t ) − t ≥ 2 + t t 2 . The inequality follows from that for t ≥ 0 t \ge 0 t ≥ 0
ln ( 1 + t ) ≥ t 1 + t / 2 = 2 t 2 + t .
\begin{aligned}
\ln (1 + t) \ge \frac{t}{1 + t / 2} = \frac{2t}{2 + t}.
\end{aligned}
ln ( 1 + t ) ≥ 1 + t /2 t = 2 + t 2 t . The inequality clearly holds for t = 0 t = 0 t = 0 g ( x ) = 1 1 + x g(x) = \frac{1}{1 + x} g ( x ) = 1 + x 1 t > 0 t > 0 t > 0
ln ( 1 + t ) t = 1 t ∫ 0 t g ( x ) d x ≥ 1 1 + 1 t ∫ 0 t x d x = 1 1 + t / 2 .
\frac{\ln (1 + t) }{ t } = \frac{1}{t} \int_0^t g(x) \ dx \ge \frac{1}{ 1 + \frac{1}{t} \int_0^t x \ d x } = \frac{1}{ 1 + t / 2}.
t ln ( 1 + t ) = t 1 ∫ 0 t g ( x ) d x ≥ 1 + t 1 ∫ 0 t x d x 1 = 1 + t /2 1 . Remark: A tighter bound shows that
( 1 + t ) ln ( 1 + t ) − t ≥ t 2 2 + ( 2 / 3 ) t , ∀ t ≥ 0.
(1 + t) \ln (1 + t) - t \ge \frac{t^2}{ 2 + (2 / 3) t}, \quad \forall t \ge 0.
( 1 + t ) ln ( 1 + t ) − t ≥ 2 + ( 2/3 ) t t 2 , ∀ t ≥ 0. which gives
( exp ( η μ ) ( 1 + η μ ) 1 + η μ ) μ ≤ exp ( − η 2 2 μ + ( 2 / 3 ) η ) .
\left( \frac{ \exp \Big( \frac{\eta}{ \mu} \Big) }{ \Big( 1 + \frac{ \eta }{ \mu } \Big)^{ 1 + \frac{ \eta }{ \mu } } } \right)^\mu
\le
\exp \left( - \frac{ \eta^2 }{ 2 \mu + (2 / 3) \eta } \right).
( 1 + μ η ) 1 + μ η exp ( μ η ) μ ≤ exp ( − 2 μ + ( 2/3 ) η η 2 ) . To prove it, define
f ( t ) ≐ ( 1 + t ) ln ( 1 + t ) − t .
f(t) \doteq (1 + t) \ln (1 + t) - t.
f ( t ) ≐ ( 1 + t ) ln ( 1 + t ) − t . As f ( 0 ） = 0 f(0）= 0 f ( 0 ） = 0
f ( t ) = ∫ 0 1 f ′ ( t x ) d ( t x ) = ∫ 0 1 ∫ 0 x f ′ ′ ( t y ) d ( t y ) d ( t x ) = t 2 ∫ 0 1 ∫ 0 x 1 1 + t y d y d x . \small
\begin{aligned}
f(t)
= \int_0^1 f'( tx ) \, d\, (tx)
= \int_0^1 \int_0^x f''( ty ) \, d\, (ty) \, d\, (tx)
= t^2 \int_0^1 \int_0^x \frac{1}{1 + ty} \, d\, y \, d\, x
\end{aligned}.
f ( t ) = ∫ 0 1 f ′ ( t x ) d ( t x ) = ∫ 0 1 ∫ 0 x f ′′ ( t y ) d ( t y ) d ( t x ) = t 2 ∫ 0 1 ∫ 0 x 1 + t y 1 d y d x . The function g ( x , y ) = 1 1 + t y g(x, y) = \frac{1}{1 + ty} g ( x , y ) = 1 + t y 1
{ ( x , y ) : x ∈ [ 0 , 1 ] , y ∈ [ 0 , x ] } .
\{ (x, y) : x \in [0, 1], y \in [0, x] \}.
{( x , y ) : x ∈ [ 0 , 1 ] , y ∈ [ 0 , x ]} . It has area 1 / 2 1 / 2 1/2
1 1 / 2 ∫ 0 1 ∫ 0 x 1 1 + t y d y d x ≥ 1 1 + t ⋅ 1 1 / 2 ⋅ ∫ 0 1 ∫ 0 x y d y d x = 1 1 + t / 3 .
\frac{1}{1 / 2} \int_0^1 \int_0^x \frac{1}{1 + ty} \, d\, y \, d\, x \ge \frac{1}{1 + t \cdot \frac{1}{1 / 2} \cdot \int_0^1 \int_0^x y \, d\, y \, d\, x } = \frac{1}{1 + t / 3}.
1/2 1 ∫ 0 1 ∫ 0 x 1 + t y 1 d y d x ≥ 1 + t ⋅ 1/2 1 ⋅ ∫ 0 1 ∫ 0 x y d y d x 1 = 1 + t /3 1 . Remark: A looser bound can be obtained as follows. Define
f ( t ) ≐ ( 1 + t ) ln ( 1 + t ) − t .
f(t) \doteq (1 + t) \ln (1 + t) - t.
f ( t ) ≐ ( 1 + t ) ln ( 1 + t ) − t . Then f ′ ( t ) = ln ( 1 + t ) f'(t) = \ln (1 + t) f ′ ( t ) = ln ( 1 + t ) f ′ ′ ( t ) = 1 / ( 1 + t ) f''(t) = 1 / (1 + t) f ′′ ( t ) = 1/ ( 1 + t ) c ∈ [ 0 , t ] c \in [0, t] c ∈ [ 0 , t ]
f ( t ) = f ( 0 ) + f ′ ( 0 ) ⋅ t + f ′ ′ ( c ) ⋅ t 2 2 = 1 1 + c ⋅ t 2 2 .
f(t) = f(0) + f'(0) \cdot t + f''(c) \cdot \frac{t^2}{2} = \frac{1}{1 + c} \cdot \frac{t^2}{2}.
f ( t ) = f ( 0 ) + f ′ ( 0 ) ⋅ t + f ′′ ( c ) ⋅ 2 t 2 = 1 + c 1 ⋅ 2 t 2 . The bound we obtained before asserts that c ≤ t / 2 c \le t / 2 c ≤ t /2 f ( t ) f(t) f ( t ) t ≥ 0 t \ge 0 t ≥ 0 f ( t ) f(t) f ( t )
f ( t ) = 1 1 + c ⋅ t 2 2 ≥ 1 1 + t ⋅ t 2 2 ,
f(t) = \frac{1}{1 + c} \cdot \frac{t^2}{2} \ge \frac{1}{1 + t} \cdot \frac{t^2}{2},
f ( t ) = 1 + c 1 ⋅ 2 t 2 ≥ 1 + t 1 ⋅ 2 t 2 , which gives
( exp ( η μ ) ( 1 + η μ ) 1 + η μ ) μ ≤ exp ( − η 2 2 ( μ + η ) ) .
\left( \frac{ \exp \Big( \frac{\eta}{ \mu} \Big) }{ \Big( 1 + \frac{ \eta }{ \mu } \Big)^{ 1 + \frac{ \eta }{ \mu } } } \right)^\mu
\le
\exp \left( - \frac{ \eta^2 }{ 2 (\mu + \eta) } \right).
( 1 + μ η ) 1 + μ η exp ( μ η ) μ ≤ exp ( − 2 ( μ + η ) η 2 ) . □ \square □
Lower Bound
Let X X X μ \mu μ 0 ≤ η ≤ μ 0 \le \eta \le \mu 0 ≤ η ≤ μ
Pr [ X ≤ μ − η ] = ( exp ( η μ ) ( 1 − η μ ) 1 − η μ ) μ ≤ exp ( − η 2 2 μ ) .
\Pr[ X \le \mu - \eta ]
= \left( \frac{ \exp \Big( \frac{\eta}{ \mu} \Big) }{ \Big( 1 - \frac{ \eta }{ \mu } \Big)^{ 1 - \frac{ \eta }{ \mu } } } \right)^\mu
\le
\exp \left( - \frac{ \eta^2 }{ 2 \mu } \right).
Pr [ X ≤ μ − η ] = ( 1 − μ η ) 1 − μ η exp ( μ η ) μ ≤ exp ( − 2 μ η 2 ) .
Proof. Via Markov's inequality, for all s > 0 , 0 ≤ η ≤ μ s > 0, 0 \le \eta \le \mu s > 0 , 0 ≤ η ≤ μ
Pr [ X ≤ μ − η ] = Pr [ exp ( − s X ) ≥ exp ( − s ( μ − η ) ) ] ≤ E [ exp ( − s X ) ] exp ( − s ( μ − η ) ) = exp ( ( e − s − 1 ) μ + ( s ( μ − η ) ) ) . \small
\begin{aligned}
\Pr[ X \le \mu - \eta ]
&= \Pr \Big[ \exp( - s X ) \ge \exp \big( -s ( \mu - \eta) \big) \Big] \\
&\le \frac{ \mathbb{E} [ \exp( - s X ) ] }{ \exp \big( - s ( \mu - \eta) \big) } \\
&= \exp \Big( ( e^{-s} - 1 ) \mu + \big( s ( \mu - \eta) \big) \Big).
\end{aligned}
Pr [ X ≤ μ − η ] = Pr [ exp ( − s X ) ≥ exp ( − s ( μ − η ) ) ] ≤ exp ( − s ( μ − η ) ) E [ exp ( − s X )] = exp ( ( e − s − 1 ) μ + ( s ( μ − η ) ) ) . Define f ( s ) = ( e − s − 1 ) μ + ( s ( μ − η ) ) f(s) = ( e^{-s} - 1 ) \mu + \big( s ( \mu - \eta) \big) f ( s ) = ( e − s − 1 ) μ + ( s ( μ − η ) )
f ′ ( s ) = − μ e − s + ( μ − η ) = 0 ,
f'(s) = - \mu e^{-s} + (\mu - \eta) = 0,
f ′ ( s ) = − μ e − s + ( μ − η ) = 0 , we get s = − ln μ − η μ s = - \ln \frac{\mu - \eta}{ \mu} s = − ln μ μ − η
Pr [ X ≥ μ − η ] ≤ exp ( ( μ − η μ − 1 ) ⋅ μ − ( μ − η ) ⋅ ln μ − η μ ) = exp ( − μ { η μ + ( 1 − η μ ) ⋅ ln ( 1 − η μ ) } ) = ( exp ( − η μ ) ( 1 − η μ ) 1 − η μ ) μ . \small
\begin{aligned}
\Pr[ X \ge \mu - \eta ]
&\le \exp \left( \Big( \frac{\mu - \eta}{ \mu} - 1 \Big) \cdot \mu - ( \mu - \eta) \cdot \ln \frac{\mu - \eta}{ \mu} \right) \\
&= \exp \left( - \mu \left\{ \frac{\eta}{ \mu} + \Big( 1 - \frac{ \eta }{ \mu } \Big) \cdot \ln \Big( 1 - \frac{ \eta }{ \mu } \Big) \right\} \right) \\
&= \left( \frac{ \exp \Big( - \frac{\eta}{ \mu} \Big) }{ \Big( 1 - \frac{ \eta }{ \mu } \Big)^{ 1 - \frac{ \eta }{ \mu } } } \right)^\mu.
\end{aligned}
Pr [ X ≥ μ − η ] ≤ exp ( ( μ μ − η − 1 ) ⋅ μ − ( μ − η ) ⋅ ln μ μ − η ) = exp ( − μ { μ η + ( 1 − μ η ) ⋅ ln ( 1 − μ η ) } ) = ( 1 − μ η ) 1 − μ η exp ( − μ η ) μ . Next, we prove the inequality of
( exp ( − η μ ) ( 1 − η μ ) 1 − η μ ) μ ≤ exp ( − η 2 2 μ ) .
\left( \frac{ \exp \Big( - \frac{\eta}{ \mu} \Big) }{ \Big( 1 - \frac{ \eta }{ \mu } \Big)^{ 1 - \frac{ \eta }{ \mu } } } \right)^\mu
\le
\exp \left( - \frac{ \eta^2 }{ 2 \mu } \right).
( 1 − μ η ) 1 − μ η exp ( − μ η ) μ ≤ exp ( − 2 μ η 2 ) . Let t = η μ ∈ [ 0 , 1 ) t = \frac{\eta}{\mu} \in [0, 1) t = μ η ∈ [ 0 , 1 )
( 1 − t ) ln ( 1 − t ) + t ≥ t 2 2 .
(1 - t) \ln (1 - t) + t \ge \frac{ t^2 }{ 2 }.
( 1 − t ) ln ( 1 − t ) + t ≥ 2 t 2 . Let f ( t ) = ( 1 − t ) ln ( 1 − t ) + t f(t) = (1 - t) \ln (1 - t) + t f ( t ) = ( 1 − t ) ln ( 1 − t ) + t
f ′ ( t ) = − ln ( 1 − t ) , f ′ ′ ( t ) = 1 1 − t .
\begin{aligned}
f'(t) &= -\ln (1 - t), \\
f''(t) &= \frac{1}{1 - t}.
\end{aligned}
f ′ ( t ) f ′′ ( t ) = − ln ( 1 − t ) , = 1 − t 1 . Using Taylor's expansion, there exists some c ∈ [ 0 , t ] c \in [0, t] c ∈ [ 0 , t ]
f ( t ) = f ( 0 ) + f ′ ( 0 ) ⋅ t + f ′ ′ ( c ) ⋅ t 2 2 = 1 1 − c ⋅ t 2 2 .
f(t)
= f(0) + f'(0) \cdot t + f''(c) \cdot \frac{t^2}{2}
= \frac{1}{1 - c} \cdot \frac{t^2}{2}.
f ( t ) = f ( 0 ) + f ′ ( 0 ) ⋅ t + f ′′ ( c ) ⋅ 2 t 2 = 1 − c 1 ⋅ 2 t 2 . The proof follows by observing that 1 1 − c ≥ 1 \frac{1}{1 - c} \ge 1 1 − c 1 ≥ 1
□ \square □
Reference
[1]. David Pollard. Chapter 2, MiniEmpirical. http://www.stat.yale.edu/~pollard/Books/Mini/, 2015. Manuscript Mitzenmacher, M. and Upfal, E., 2017. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press.
← Back to all notes Back to top ↑