We give a Monte Carlo algorithm that computes an unbiased estimate of the c
onvolution of two vectors. The variance of our estimate is small for entrie
s of the convolution that are large; this corresponds to the situation in w
hich convolution is used in pattern matching or template matching, where on
e is only interested in the largest entries of the resulting convolution ve
ctor. Experiments performed with our algorithm confirm the theory and sugge
st that, in contexts where one cares about only the large entries in the co
nvolution, the algorithm can be a faster alternative to performing an FFT-b
ased convolution.