Register to reply 
Convolution of two probability distributions using FFT 
Share this thread: 
#1
Nov812, 05:12 PM

P: 15

I've been trying to code an algorithm to compute the convolution of two probability distributions. using the FFT. This relies on the "convolution theorem":
(p*q)[z] = FFT^{1}(FFT(p) \cdot FFT(q)) However, when I test it using the distributions p={0.1, 0.2, 0.3, 0.4} q={0.4, 0.3, 0.2, 0.1} the result that's output  {0.24, 0.22, 0.24, 0.3}  doesn't correspond to any definition or generalised definition of convolution that I can find. (I'm fairly sure that one of the 0.24s, for instance, results from p[0]q[2] + p[1]q[1] + p[2]q[0] + p[3]q[3] being computed and divided by n) Can someone wellversed in FFTs (and/or convolutions) shed any light on what might be going on? I enclose the source code, which uses C++ and the FFTW package, below:



#2
Nov912, 12:07 AM

Sci Advisor
P: 3,313

Perhaps it's "circular convolution"
[itex] (p*q)_n = \sum_{m=0}^3 { p_m q_{nm} } [/itex] e.g. [itex] (p*q)_0 = \sum_{m = 0}^3 {p_m} q_{0m} [/itex] [itex] = p_0 q_0 + p_1 q_{1} + p_2 q_{2} + p_3 q_{3} [/itex] Where we regard [itex] q_{1} = q_3 , q_{2}= q_2 [/itex] etc [itex] = (0.1)(0.4) + (0.2)(0.1) + (0.3)(0.2) + (0.4)(0.3) = 0.24 [/itex] 


#3
Nov912, 06:36 AM

P: 15




Register to reply 
Related Discussions  
Convolution of distributions on integers  Set Theory, Logic, Probability, Statistics  0  
Convolution of densities and distributions  General Math  8  
Can we deduce the product of distributions via convolution theorem  Calculus  0  
Distributions: Convolution product  Calculus & Beyond Homework  4  
Computing distributions by using convolution.  Set Theory, Logic, Probability, Statistics  2 