Poisson Distribution
A discrete random variable X X X ˈ ˈ ˈ λ \lambda λ
Pr [ X = k ] = e − λ λ k k ! , ∀ k ∈ N .
\Pr[ X = k ] = e^{ - \lambda } \frac{ \lambda^k }{ k! }, \qquad \forall k \in \mathbb{N}.
Pr [ X = k ] = e − λ k ! λ k , ∀ k ∈ N . We can verify that the definition is valid:
∑ k ∈ N Pr [ X = k ] = e − λ ∑ k ∈ N λ k k ! = e − λ e λ = 1.
\sum_{ k \in \mathbb{N} } \Pr[ X = k ] = e^{ - \lambda } \sum_{ k \in \mathbb{N} } \frac{ \lambda^k }{ k! } = e^{ - \lambda } e^{ \lambda } = 1.
k ∈ N ∑ Pr [ X = k ] = e − λ k ∈ N ∑ k ! λ k = e − λ e λ = 1. We use Pois ( λ ) \text{Pois}(\lambda) Pois ( λ ) λ \lambda λ
Mean
Property. E [ X ] = λ \mathbb{E}[X] = \lambda E [ X ] = λ
Proof.
∑ k ∈ N k Pr [ X = k ] = e − λ λ ∑ 1 ≤ k ∈ N λ k − 1 ( k − 1 ) ! = e − λ λ ∑ k ∈ N λ k k ! = λ .
\sum_{ k \in \mathbb{N} } k\Pr[ X = k ] = e^{ - \lambda } \lambda \sum_{ 1 \le k \in \mathbb{N} } \frac{ \lambda^{k - 1} }{ (k - 1)! } = e^{ - \lambda } \lambda \sum_{ k \in \mathbb{N} } \frac{ \lambda^k }{ k! } = \lambda.
k ∈ N ∑ k Pr [ X = k ] = e − λ λ 1 ≤ k ∈ N ∑ ( k − 1 )! λ k − 1 = e − λ λ k ∈ N ∑ k ! λ k = λ . □ \square □
Variance
Property. V a r [ X ] = λ \mathbb{Var}[X] = \lambda V a r [ X ] = λ
Proof.
∑ k ∈ N k ( k − 1 ) Pr [ X = k ] = e − λ λ 2 ∑ 2 ≤ k ∈ N λ k − 2 ( k − 2 ) ! = e − λ λ 2 ∑ k ∈ N λ k k ! = λ 2 .
\sum_{ k \in \mathbb{N} } k(k - 1)\Pr[ X = k ] = e^{ - \lambda } \lambda^2 \sum_{ 2 \le k \in \mathbb{N} } \frac{ \lambda^{k - 2} }{ (k - 2)! } = e^{ - \lambda } \lambda^2 \sum_{ k \in \mathbb{N} } \frac{ \lambda^k }{ k! } = \lambda^2.
k ∈ N ∑ k ( k − 1 ) Pr [ X = k ] = e − λ λ 2 2 ≤ k ∈ N ∑ ( k − 2 )! λ k − 2 = e − λ λ 2 k ∈ N ∑ k ! λ k = λ 2 . Hence,
V a r [ X ] = ∑ k ∈ N k 2 Pr [ X = k ] − ( E [ X ] ) 2 = ∑ k ∈ N ( k ( k − 1 ) + k ) Pr [ X = k ] − ( E [ X ] ) 2 = λ 2 + λ − λ 2 = λ .
\begin{aligned}
\mathbb{Var}[X] &= \sum_{ k \in \mathbb{N} } k^2 \Pr[ X = k ] - (\mathbb{E}[X] )^2 \\
&= \sum_{ k \in \mathbb{N} } ( k (k - 1) + k ) \Pr[ X = k ] - (\mathbb{E}[X] )^2 \\
&= \lambda^2 + \lambda - \lambda^2 \\
&= \lambda.
\end{aligned}
V a r [ X ] = k ∈ N ∑ k 2 Pr [ X = k ] − ( E [ X ] ) 2 = k ∈ N ∑ ( k ( k − 1 ) + k ) Pr [ X = k ] − ( E [ X ] ) 2 = λ 2 + λ − λ 2 = λ . □ \square □
Sum of Two Independent Poisson Variable
Property. If X 1 ∼ Pois ( λ 1 ) X_1 \sim \text{Pois}(\lambda_1) X 1 ∼ Pois ( λ 1 ) X 2 ∼ Pois ( λ 2 ) X_2 \sim \text{Pois}(\lambda_2) X 2 ∼ Pois ( λ 2 ) X 1 + X 2 ∼ Pois ( λ 1 + λ 2 ) X_1 + X_2 \sim \text{Pois} (\lambda_1 + \lambda_2) X 1 + X 2 ∼ Pois ( λ 1 + λ 2 )
Proof. For every k ∈ N k \in \mathbb{N} k ∈ N
Pr [ X 1 + X 2 = k ] = ∑ a , b ∈ N , a + b = k ( e − λ 1 λ 1 a a ! ) ( e − λ 2 λ 2 b b ! ) = e − ( λ 1 + λ 2 ) 1 k ! ∑ a , b ∈ N , a + b = k k ! a ! b ! λ 1 a λ 2 b = e − ( λ 1 + λ 2 ) ( λ 1 + λ 2 ) k k ! .
\begin{aligned}
\Pr[X_1 + X_2 = k]
&= \sum_{a, b \in \mathbb{N}, a + b = k} \left( e^{- \lambda_1 } \frac{ \lambda_1^{a} }{ a! } \right) \left( e^{-\lambda_2 } \frac{ \lambda_2^b }{ b! } \right) \\
&= e^{- (\lambda_1 + \lambda_2) } \frac{1}{k!} \sum_{a, b \in \mathbb{N}, a + b = k} \frac{ k! }{ a! b! } \lambda_1^{a} \lambda_2^b \\
&= e^{- (\lambda_1 + \lambda_2) } \frac{ (\lambda_1 + \lambda_2)^k }{k!}.
\end{aligned}
Pr [ X 1 + X 2 = k ] = a , b ∈ N , a + b = k ∑ ( e − λ 1 a ! λ 1 a ) ( e − λ 2 b ! λ 2 b ) = e − ( λ 1 + λ 2 ) k ! 1 a , b ∈ N , a + b = k ∑ a ! b ! k ! λ 1 a λ 2 b = e − ( λ 1 + λ 2 ) k ! ( λ 1 + λ 2 ) k . □ \square □
Corollary. If X i ∼ Pois ( λ i ) X_i \sim \text{Pois}(\lambda_i) X i ∼ Pois ( λ i ) i ∈ [ n ] i \in [n] i ∈ [ n ] ∑ i ∈ [ n ] X i ∼ Pois ( ∑ i ∈ [ n ] λ i ) \sum_{i \in [n] } X_i \sim \text{Pois} \left( \sum_{i \in [n] } \lambda_i \right) ∑ i ∈ [ n ] X i ∼ Pois ( ∑ i ∈ [ n ] λ i )
Poisson Approximation
Binomial Distribution
The Poisson distribution can be used to approximate the limit of the binomial distribution, under some condition.
Poisson Limit Theorem. Suppose that ∀ n ∈ N + \forall n \in \mathbb{N}^+ ∀ n ∈ N + Y n Y_n Y n B ( n , p n ) \text{B}(n, p_n) B ( n , p n ) n p n = λ n p_n = \lambda n p n = λ X ∼ Pois ( λ ) X \sim \text{Pois}(\lambda) X ∼ Pois ( λ )
lim n Pr [ Y n = k ] = Pr [ X = k ] .
\lim_n \Pr[ Y_n = k ] = \Pr[ X = k ].
n lim Pr [ Y n = k ] = Pr [ X = k ] .
Proof.
Pr [ Y n = k ] = ( n k ) p n k ( 1 − p n ) n − k = n ( n − 1 ) . . . ( n − k + 1 ) k ! p n k ( 1 − p n ) n − k = n k + O ( n k − 1 ) k ! λ k n k ( 1 − λ n ) n − k = λ k ( 1 + O ( n − 1 ) ) k ! ( 1 − λ n ) n − k
\begin{aligned}
\Pr[ Y_n = k ]
&= \binom{n}{k } p_n^k (1 - p_n)^{n - k} \\
&= \frac{ n (n - 1) ... (n - k + 1) }{ k !} p_n^k ( 1 - p_n )^{n - k} \\
&= \frac{ n^k + O(n^{k - 1} ) }{ k !} \frac{ \lambda^k }{ n^k } \left( 1 - \frac{ \lambda }{ n } \right)^{n - k} \\
&= \frac{ \lambda^k \left( 1 + O( n^{-1} ) \right) }{ k !} \left( 1 - \frac{ \lambda }{ n } \right)^{n - k}
\end{aligned}
Pr [ Y n = k ] = ( k n ) p n k ( 1 − p n ) n − k = k ! n ( n − 1 ) ... ( n − k + 1 ) p n k ( 1 − p n ) n − k = k ! n k + O ( n k − 1 ) n k λ k ( 1 − n λ ) n − k = k ! λ k ( 1 + O ( n − 1 ) ) ( 1 − n λ ) n − k For fixed k k k n → ∞ n \rightarrow \infty n → ∞
λ k ( 1 + O ( n − 1 ) ) k ! ( 1 − λ n ) n − k → λ k k ! e − λ .
\frac{ \lambda^k \left( 1 + O( n^{-1} ) \right) }{ k !} \left( 1 - \frac{ \lambda }{ n } \right)^{n - k} \rightarrow \frac{\lambda^k}{ k !} e^{-\lambda }.
k ! λ k ( 1 + O ( n − 1 ) ) ( 1 − n λ ) n − k → k ! λ k e − λ . Balls and Bins
We study the problem of throwing m m m n n n i ∈ [ n ] i \in [n] i ∈ [ n ] Y i Y_i Y i i i i B ( m , 1 / m ) \text{B}(m, 1 / m) B ( m , 1/ m ) Y i Y_i Y i X i ∼ Pois ( m / n ) X_i \sim \text{Pois}(m / n) X i ∼ Pois ( m / n ) ( Y 1 , . . . , Y n ) (Y_1, ..., Y_n) ( Y 1 , ... , Y n )
Theorem. ∀ λ > 0 \forall \lambda > 0 ∀ λ > 0 X i ∼ Pois ( λ ) X_i \sim \text{Pois}(\lambda) X i ∼ Pois ( λ ) ( X 1 , . . . , X n ) (X_1, ..., X_n) ( X 1 , ... , X n ) ∑ i ∈ [ n ] X i = m \sum_{i \in [n]} X_i = m ∑ i ∈ [ n ] X i = m ( Y 1 , . . . , Y n ) (Y_1, ..., Y_n) ( Y 1 , ... , Y n )
Remark: the theorem holds for ∀ λ > 0 \forall \lambda > 0 ∀ λ > 0 λ = m / n \lambda = m / n λ = m / n .
Proof. Let X = ∑ i ∈ [ n ] X i X = \sum_{i \in [n] } X_i X = ∑ i ∈ [ n ] X i X ∼ Pois ( n λ ) X \sim \text{Pois}( n \lambda) X ∼ Pois ( nλ ) ∀ k 1 , . . . , k n ≥ 0 \forall k_1, ..., k_n \ge 0 ∀ k 1 , ... , k n ≥ 0 ∑ i ∈ [ n ] k i = m \sum_{i \in [n] } k_i = m ∑ i ∈ [ n ] k i = m
Pr [ X 1 = k 1 , X 2 = k 2 , . . . , X n = k n ∣ X = m ] = ( ∏ i ∈ [ n ] e − λ λ k i k i ! ) / ( e − n λ ( n λ ) m m ! ) = e − n λ λ ∑ i ∈ [ n ] k i e − n λ ( n λ ) m m ! ∏ i ∈ [ n ] k i ! = ( m ! k 1 ; k 2 ; . . . ; k n ) 1 n m .
\begin{aligned}
\Pr[ X_1 = k_1, X_2 = k_2, ..., X_n = k_n \mid X = m ]
&= \left( \prod_{i \in [n] } e^{-\lambda} \frac{ \lambda^{k_i} }{ k_i! } \right) / \left( e^{ - n\lambda} \frac{ (n\lambda)^m }{ m! } \right) \\
&= \frac{ e^{ - n \lambda} \lambda^{ \sum_{i \in [n] } k_i} }{ e^{ - n\lambda} (n\lambda)^m } \frac{ m! }{ \prod_{i \in [n] } k_i ! } \\
&= \binom{ m! }{ k_1; k_2; ...; k_n } \frac{1}{ n^m }.
\end{aligned}
Pr [ X 1 = k 1 , X 2 = k 2 , ... , X n = k n ∣ X = m ] = i ∈ [ n ] ∏ e − λ k i ! λ k i / ( e − nλ m ! ( nλ ) m ) = e − nλ ( nλ ) m e − nλ λ ∑ i ∈ [ n ] k i ∏ i ∈ [ n ] k i ! m ! = ( k 1 ; k 2 ; ... ; k n m ! ) n m 1 . □ \square □
Theorem [1] . ∀ i ∈ [ n ] \forall i \in [n] ∀ i ∈ [ n ] X i ∼ Pois ( m / n ) X_i \sim \text{Pois}(m / n) X i ∼ Pois ( m / n ) f ( y 1 , . . . , y n ) f(y_1, ..., y_n) f ( y 1 , ... , y n )
E [ f ( Y 1 , . . . , Y n ) ] ≤ e m E [ f ( X 1 , . . . , X n ) ] .
\mathbb{E}[ f(Y_1, ..., Y_n) ] \le e \sqrt{m} \mathbb{E}[ f(X_1, ..., X_n) ].
E [ f ( Y 1 , ... , Y n )] ≤ e m E [ f ( X 1 , ... , X n )] .
Proof. Let X = ∑ i ∈ [ n ] X i X = \sum_{i \in [n] } X_i X = ∑ i ∈ [ n ] X i X ∼ Pois ( m ) X \sim \text{Pois}(m) X ∼ Pois ( m ) f f f
E [ f ( X 1 , . . . , X n ) ] = ∑ k ∈ N E [ f ( X 1 , . . . , X n ) ∣ X = k ] ⋅ Pr [ X = k ] ≥ E [ f ( X 1 , . . . , X n ) ∣ X = m ] ⋅ Pr [ X = m ] = E [ f ( Y 1 , . . . , Y n ) ] ⋅ e − m m m m ! ≥ E [ f ( Y 1 , . . . , Y n ) ] ⋅ e − m ( m ) m ( e m ) m 1 e m = E [ f ( Y 1 , . . . , Y n ) ] ⋅ 1 e m ,
\begin{aligned}
\mathbb{E}[ f(X_1, ..., X_n) ]
&= \sum_{ k \in \mathbb{N} } \mathbb{E}[ f(X_1, ..., X_n) \mid X = k] \cdot \Pr[ X = k ] \\
&\ge \mathbb{E}[ f(X_1, ..., X_n) \mid X = m] \cdot \Pr[ X = m ] \\
&= \mathbb{E}[ f(Y_1, ..., Y_n) ] \cdot e^{ - m } \frac{ m^m }{ m! } \\
&\ge \mathbb{E}[ f(Y_1, ..., Y_n) ] \cdot e^{ - m } (m)^m \left( \frac{e}{m} \right)^m \frac{1}{ e \sqrt{m} } \\
&= \mathbb{E}[ f(Y_1, ..., Y_n) ] \cdot \frac{1}{ e \sqrt{m} },
\end{aligned}
E [ f ( X 1 , ... , X n )] = k ∈ N ∑ E [ f ( X 1 , ... , X n ) ∣ X = k ] ⋅ Pr [ X = k ] ≥ E [ f ( X 1 , ... , X n ) ∣ X = m ] ⋅ Pr [ X = m ] = E [ f ( Y 1 , ... , Y n )] ⋅ e − m m ! m m ≥ E [ f ( Y 1 , ... , Y n )] ⋅ e − m ( m ) m ( m e ) m e m 1 = E [ f ( Y 1 , ... , Y n )] ⋅ e m 1 , and the theorem is proven. The last inequality follows from Stirling's formula that m ! ≤ e m ( m / e ) m m! \le e \sqrt{m} (m / e)^m m ! ≤ e m ( m / e ) m
□ \square □
Corollary. If some event happens with probability p p p X 1 , . . . , X n X_1, ..., X_n X 1 , ... , X n e m ⋅ p e\sqrt{m} \cdot p e m ⋅ p Y 1 , . . . , Y n Y_1, ..., Y_n Y 1 , ... , Y n
Proof. Let f f f
Pr [ f ( Y 1 , . . . , Y n ) ] ≤ e m Pr [ f ( X 1 , . . . , X n ) ] .
\Pr[ f(Y_1, ..., Y_n) ] \le e \sqrt{m} \Pr[ f(X_1, ..., X_n) ].
Pr [ f ( Y 1 , ... , Y n )] ≤ e m Pr [ f ( X 1 , ... , X n )] . □ \square □
The analysis makes some analysis simpler since the X i X_i X i
In some special cases, the theorem can be strengthened.
Theorem [1]. Let f ( y 1 , . . . , y n ) f(y_1, ..., y_n) f ( y 1 , ... , y n ) E [ f ( Y 1 , . . . , Y n ) ] \mathbb{E} [ f(Y_1, ..., Y_n) ] E [ f ( Y 1 , ... , Y n )] m m m
E [ f ( Y 1 , . . . , Y n ) ] ≤ 2 E [ f ( X 1 , . . . , X n ) ] .
\mathbb{E}[ f(Y_1, ..., Y_n) ] \le 2 \mathbb{E}[ f(X_1, ..., X_n) ].
E [ f ( Y 1 , ... , Y n )] ≤ 2 E [ f ( X 1 , ... , X n )] .
Proof. Refer to [1]. Omitted.
Reference
[1] M. Mitzenmacher and E. Upfal, “Probability and Computing,” p. 490.
← Back to all notes Back to top ↑