通过日志处理小概率

Question

来源：Google Code Jam。 https://code.google.com/codejam/contest/10224486/dashboard#s=a&a=1

我们被要求计算 Prob（N 次试验的 K 次成功），其中 N 次试验中的每一次都具有 p_n 的已知成功概率。

Code Jam 后给出了对问题的一些分析和思考。

他们观察到评估 N 次试验的所有可能结果将花费 N 的指数时间，因此他们提供了一个很好的 "dynamic programming" 风格的解决方案，即 O(N^2)。

令 P(p#q) = Prob(p 在第 q 次试验后成功) 然后观察事实：

Prob(p#q) = Prob(qth trial succeeds)*P(p-1#q-1) + Prob(qth trial fails)*P(p#q-1)

现在我们可以构建 P(i#j) 的 table，其中 i<=j，因为 i = 1...N

太棒了 - 我遵循了所有这些并且可以实现它。

然后作为最后一条评论，他们说：

In practice, in problems like this, one should store the logarithms of
probabilities instead of the actual values, which can become small
enough for floating-point precision errors to matter.

我想我大致理解了他们试图表达的观点，但我特别想不通如何使用这个建议。

将上面的等式代入一些字母变量：

P = A*B + C*D

如果我们想在 Log Space 中工作，那么我们有：

Log(P) = Log(A*B + C*D),

我们已经递归地预先计算了 Log(B) 和 Log(D)，并且 A 和 B 是已知的、易于处理的小数。

但我看不出有什么方法可以计算 Log(P) 而不是只做 e^(Log(B)) 等等，这感觉就像在日志 space 中工作一样失败？

有没有人更详细地了解我应该做什么？

Answer 1

从初始关系开始：

P = A⋅B + C⋅D

由于其对称性，我们可以假设 B 大于 D，而不失一般性。下面的处理很有用：

log(P) = log(A⋅B + C⋅D) = log(A⋅e^log(B) + C⋅e^{log (D)}) = log(e^log(B)⋅(A + C⋅e^{log(D) - log(B)})

log(P) = log(B) + log(A + C⋅e^{log(D) - log(B)}).

这很有用，因为在这种情况下，log(B) 和 log(D) 都是负数（某些概率的对数）。假设 B 大于 D，因此其对数更接近于零。因此 log(D) - log(B) 仍然为负，但不如 log(D) 负。

所以现在，我们不需要分别对 log(B) 和 log(D) 求幂，我们只需要对 log(D) - log(B) 求幂，这是一个轻微的负数。因此，与使用对数和以简单的方式应用求幂相比，上述处理导致更好的数值行为，或者等效地，比根本不使用对数更好。

通过日志处理小概率

Working with small probabilities, via logs

algorithm

precision

logarithm