Convolution
Chris Piech
CS109, Stanford University
Four Prototypical Trajectories
What happens when you add random
variables?
Sum of Independent Binomials
• Let X and Y be independent random variables
§ X ~ Bin(n1, p) and Y ~ Bin(n2, p)
§ X + Y ~ Bin(n1 + n2, p)
• Intuition:
§ X has n1 trials and Y has n2 trials
o Each trial has same “success” probability p
§ Define Z to be n1 + n2 trials, each with success prob. p
§ Z ~ Bin(n1 + n2, p), and also Z = X + Y
Four Prototypical Trajectories
If only it were always that simple
The Insight to Convolution Proofs
P(X + Y = n)?
What is the probability that X + Y = n?
X Y k
0 n 0 P(X = 0, Y = n)
1 n-1 1 P(X = 1, Y = n-1)
2 n-2 2 P(X = 2, Y = n-2)
…
n 0 n P(X = n, Y = 0)
The Insight to Convolution Proofs
P(X + Y = n)?
What is the probability that X + Y = n?
n
X
P (X + Y = n) = P (X = k, Y = n k) Since the events
k=0
Xn
Xn
= P (X = k)P (Y = n k) If they are inde
P (X + Y = n) = P (X = k, Y = n k) Since the events
k=0
k=0
Xn
= P (X = k)P (Y = n k) If they are indep
k=0
Sum of Independent Poissons
n
X ✓ ◆
n n k n k
(a + b) = a b
k
k=0
Sum of Independent Poissons
• Let X and Y be independent random variables
§ X ~ Poi(l1) and Y ~ Poi(l2)
§ X + Y ~ Poi(l1 + l2)
• Proof: (just for reference)
§ Rewrite (X + Y = n) as (X = k, Y = n – k) where 0 £ k £ n
n n
P( X + Y = n) = å P( X = k , Y = n - k ) = å P( X = k ) P(Y = n - k )
k =0 k =0
n
l1k ln2-k n
l1k ln2-k e -( l1 +l2 ) n
n!
= åe -l1
e -l2
=e -( l1 + l2 )
å = å l1k ln2-k
k =0 k! (n - k )! k =0 k!(n - k )! n! k =0 k!(n - k )!
n
n!
§ Noting Binomial theorem: (l1 + l2 ) = å
n
l1k ln2-k
k = 0 k!( n - k )!
e - ( l1 +l2 )
§ P ( X + Y = n) =
n!
l1 + l2 ( )n
so, X + Y = n ~ Poi(l1 + l2)
Reference: Sum of Independent RVs
• Let X and Y be independent Binomial RVs
§ X ~ Bin(n1, p) and Y ~ Bin(n2, p)
§ X + Y ~ Bin(n1 + n2, p)
§ More generally, let Xi ~ Bin(ni, p) for 1 ≤ i ≤ N, then
æ N ö æ N ö
ç å X i ÷ ~ Binç å ni , p ÷
è i =1 ø è i =1 ø
• Let X and Y be independent Poisson RVs
§ X ~ Poi(l1) and Y ~ Poi(l2)
§ X + Y ~ Poi(l1 + l2)
§ More generally, let Xi ~ Poi(li) for 1 ≤ i ≤ N, then
æ N ö æ N ö
ç å X i ÷ ~ Poiç å li ÷
è i =1 ø è i =1 ø
Convolution of Probability Distributions
CON
We talked about sum of Binomial and Poisson…who’s
missing from this party?
Uniform.
Four Prototypical Trajectories
Summation: not just for the 1%
Dance, Dance Convolution
• Let X and Y be independent random variables
§ Probability Density Function (PDF) of X + Y:
¥
f X +Y ( a ) = òf
y = -¥
X (a - y ) fY ( y ) dy
¥
§ In discrete case, replace ò with å
y = -¥ y
, and f(y) with p(y)
Integration with Constraint
p
y2
ZZ Z1 Z1
fx,y dy dx = fx,y dy dx
x2 +y 2 <1 1
p
1 y2
-1
Dance, Dance Convolution
• Let X and Y be independent random variables
§ Cumulative Distribution Function (CDF) of X + Y:
FX +Y (a) = P( X + Y £ a) ¥ a- y
= òò f
x+ y£a
X ( x) fY ( y ) dx dy = ò òf
y = -¥ x = -¥
X ( x) dx fY ( y ) dy
¥
= òF
y = -¥
X (a - y ) fY ( y ) dy
§ In discrete case, replace ò with å
y = -¥ y
, and f(y) with p(y)
Sum of Independent Uniforms
• Let X and Y be independent random variables
§ X ~ Uni(0, 1) and Y ~ Uni(0, 1) à f(x) = 1 for 0 £ x £ 1
f (x)
1
For both X and Y
Sum of Independent Uniforms
• Let X and Y be independent random variables
§ X ~ Uni(0, 1) and Y ~ Uni(0, 1) à f(x) = 1 for 0 £ x £ 1
§ What is PDF of X + Y?
1 1
f X +Y ( a ) = òf
y =0
X (a - y ) fY ( y ) dy = òf
y =0
X (a - y ) dy
When a = 0.5:
Z y=?
fX+Y (0.5) = fX (0.5 y)dy f X +Y (a)
y=? 1
Z 0.5
= fX (0.5 y)dy
0
a
1 2
Z 0.5
= 1dy
0
= 0.5
Sum of Independent Uniforms
• Let X and Y be independent random variables
§ X ~ Uni(0, 1) and Y ~ Uni(0, 1) à f(x) = 1 for 0 £ x £ 1
§ What is PDF of X + Y?
1 1
f X +Y ( a ) = òf
y =0
X (a - y ) fY ( y ) dy = òf
y =0
X (a - y ) dy
When a = 1.5:
Z y=?
fX+Y (1.5) = fX (1.5 y)dy f X +Y (a)
y=? 1
Z 1
= fX (1.5 y)dy
0.5
a
1 2
Z 1
= 1dy
0.5
= 0.5
Sum of Independent Uniforms
• Let X and Y be independent random variables
§ X ~ Uni(0, 1) and Y ~ Uni(0, 1) à f(x) = 1 for 0 £ x £ 1
§ What is PDF of X + Y?
1 1
f X +Y ( a ) = òf
y =0
X (a - y ) fY ( y ) dy = òf
y =0
X (a - y ) dy
When a = 1:
Z y=?
fX+Y (1) = fX (1 y)dy f X +Y (a)
y=?
Z 1 1
= fX (1 y)dy
0 a
Z 1 2
1
= 1dy
0
=1
Sum of Independent Uniforms
• Let X and Y be independent random variables
§ X ~ Uni(0, 1) and Y ~ Uni(0, 1) à f(x) = 1 for 0 £ x £ 1
§ What is PDF of X + Y?
1 1
f X +Y ( a ) = òf
y =0
X (a - y ) fY ( y ) dy = òf
y =0
X (a - y ) dy
§ When 0 £ a £ 1 and 0 £ y £ a, 0 £ a–y £ 1 à fX (a – y) = 1
a
f X +Y ( a ) = ò dy = a
y =0
§ When 1 £ a £ 2 and a–1 £ y £ 1, 0 £ a–y £ 1 à fX (a – y) = 1
1
f X +Y (a)
f X +Y ( a ) = ò dy = 2 - a
y = a -1
1
ìa 0 £ a £1
ï
§ Combining: f X +Y ( a ) = í 2 - a 1< a £ 2
ï0 otherwise a
î 1 2
Sum of Independent Normals
• Let X and Y be independent random variables
§ X ~ N(µ1, s12) and Y ~ N(µ2, s22)
§ X + Y ~ N(µ1 + µ2, s12 + s22)
• Generally, have n independent random variables
Xi ~ N(µi, si2) for i = 1, 2, ..., n:
æ n ö æ n n
ö
ç å X i ÷ ~ N ç å µi , å s ÷
i
2
è i =1 ø è i =1 i =1 ø
Virus Infections
• Say you are working with the WHO to plan a
response to a the initial conditions of a virus:
§ Two exposed groups
§ P1: 50 people, each independently infected with p = 0.1
§ P2: 100 people, each independently infected with p = 0.4
§ Question: Probability of more than 40 infections?
Sanity check: Should we use the
Binomial Sum-of-RVs shortcut?
A. YES!
B. NO!
C. Other/none/more
Virus Infections
• Say you are working with the WHO to plan a
response to a the initial conditions of a virus:
§ Two exposed groups
§ P1: 50 people, each independently infected with p = 0.1
§ P2: 100 people, each independently infected with p = 0.4
§ A = # infected in P1 A ~ Bin(50, 0.1) » X ~ N(5, 4.5)
§ B = # infected in P2 B ~ Bin(100, 0.4) » Y ~ N(40, 24)
§ What is P(≥ 40 people infected)?
§ P(A + B ≥ 40) » P(X + Y ≥ 39.5)
§ X + Y = W ~ N(5 + 40 = 45, 4.5 + 24 = 28.5)
æ W - 45 39.5 - 45 ö
P(W ³ 39.5) = Pç > ÷ = 1 - F(-1.03) » 0.8485
è 28.5 28.5 ø
Linear Transform
2
X ⇠ N (µ, )
Y =X +X =2·X
2
Y ⇠ N (2µ, 4 )
Y =X +X =2·X
2 2
X + X ⇠ N (µ + µ, + )
2
Y ⇠ N (2µ, 2 )
Four Prototypical Trajectories
End sum of independent vars