在线性时间中将两个离散随机变量相加的概率质量

Question

给定两个离散随机变量，它们的（任意）概率质量函数 a 和 b 以及一个自然数 N，使得两个变量都具有域 [0..N]（因此函数可以表示为数组），函数对应的随机变量具有给定总和（即 P(A+B==target)）的概率可以在 O(N) 时间内通过处理数组来计算作为向量并使用它们的点积，尽管其中一个输入被反转并且两个输入都被重新切片以对齐它们并消除边界错误；因此 a 的每个位置 i 与 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)) 时间内生成此概率质量函数的 table 值。据我所知，所有涉及的点积的乘法中没有两个共享相同的有序索引对，而且我认为我不能，例如，以任何有用的方式组合两个点子积形成T(n)=2T(n/2)+O(n)类型的递归；因此我很好奇这样的运行时是如何以及为什么是可能的。

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}）可以使用称为快速傅里叶变换 (FFT) 的东西在 O(N log(N)) 时间内计算出来。因此，由于通常的点积 . 可以在 O(N) 中计算，因此您获得了用于计算两个分布的卷积的 O(N log(N)) 算法。

因此我建议您查找 this and that。

在线性时间中将两个离散随机变量相加的概率质量

Probability mass of summing two discrete random variables, in linearithmic time

arrays

algorithm

complexity-theory

probability-density