用线性时间和两个离散随机变量的概率质量

Question

给定两个离散随机变量，它们的(任意)概率质量函数a和b，以及一个自然数N，使得这两个变量都有域[0..N] (因此函数可以表示为数组)，则可以在O(N)时间内计算函数对应的随机变量具有给定和(即P(A+B==target))的概率，方法是将阵列作为向量并使用它们的点乘积，尽管它们中的一个输入相反，并且两个输入都被重新分割，以便对齐它们并消除边界误差；因此，每个位置i of a与b的位置j相匹配，从而使i+j==target。这样的算法如下所示：

-- same runtime as dotProduct and sum; other components are O(1)
P :: Vector Int -> Vector Int -> Int -> Ratio Int
P a b target | length a /= length b = undefined
             | 0 <= target && target <= 2 * length a
             = (dotProduct (shift target a) (reverse (shift target b))) 
               %
               (sum a * sum b) -- O(length a)
             -- == sum $ map (\x -> (a!x)*(b!(target-x))) [0..length a]
             | otherwise = 0

    where
        -- O(1)
        shift t v = slice start' len' v
            where start = t - length v - 1
                  len = length v - abs start
                  -- unlike `drop ... $ take ... v`,
                  -- slice does not simply `id` when given out-of-bounds indices
                  start' = min (V.length v) (max 0 start)
                  len'   = min (V.length v) (max 0 len)

        -- usual linear-algebra definition
        -- O(length a); length inequality already guarded-away by caller
        dotProduct a b = sum $ zipWith (*) a b

在相同的信息下，人们可以把变量的和看作自己的离散随机变量，尽管概率质量函数是未知的。通过执行N个点积，可以在O(N平方)时间内计算这个概率质量函数的整体(从而产生相应的阵列)，每一个乘积的操作数都有不同的移位；即：

pm :: Vector Int -> Vector Int -> Vector (Ratio Int)
pm a b = map (P a b) $ generate (2 * length a + 1) id

然而，我被告知，在O(N*log(N))时间内产生这样一个概率质量函数的值表是可行的。据我所知，在所有涉及的点乘积中，没有哪两个乘法具有相同的有序对索引，而且我不认为我能够以任何有用的方式组合两个点子积来形成T(n)=2T(n/2)+O(n)-type递归；因此，我想知道这样的运行时究竟是如何实现的，以及为什么会出现这样的运行时。

Answer 1

简单地说，您有一个变换F(称为离散傅里叶变换)，它将N大小的向量集合映射到自己上，这样

F(a*b) = F(a).F(b)

其中，*是你刚才描述的卷积算子，.是标准的点积。

此外，F是可逆的，因此可以将a*b恢复为

a*b = F^{-1}(F(a).F(b))

这一切都很好，但关键是F (和F^{-1})可以在O(N log(N))时间内使用所谓的快速傅立叶变换(FFT)来计算。因此，由于通常的点积.可以在O(N)中计算，所以得到了计算两个分布的卷积的O(N log(N))算法。

因此，我建议您查找这和那。