此流算法实例化以下框架。
查找一种随机流算法，其输出（作为随机变量）具有期望的期望，但通常具有较高的方差（即噪声）。
为了减少方差/噪声，请并行运行许多独立副本，然后组合其输出。
通常1比2更有趣。该算法的2实际上有点不合标准，但我只讲1。
假设我们正在处理输入
a b c a b a .
有了三个计数器，就无需哈希。
a: 3, b: 2, c: 1
但是，让我们假设我们只有一个。有八种可能的功能
h : {a, b, c} -> {+1, -1}。这是结果表。h |abc | X = counter----+--------------+++ | +3 +2 +1 = 6++- | +3 +2 -1 = 4+-- | +3 -2 -1 = 0+-+ | +3 -2 +1 = 2--+ | -3 -2 +1 = -4--- | -3 -2 -1 = -6-+- | -3 +2 -1 = -2-++ | -3 +2 +1 = 0
现在我们可以计算期望值
(6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0)E[h(a) X] = ------------------------------------ = 24/8 = 3 8 (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6)E[h(b) X] = ------------------------------------ = 16/8 = 2 8 (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2)E[h(c) X] = ------------------------------------ = 8/8 = 1 . 8
这里发生了什么？对于
a，例如，我们可以分解
X = Y + Z，其中s
Y的总和的变化是，
as
Z的总和
a的变化。通过期望的线性，我们有
E[h(a) X] = E[h(a) Y] + E[h(a) Z] .
E[h(a) Y]是具有用于每次出现的项的总和
a就是
h(a)^2 = 1，所以
E[h(a) Y]是出现的次数
a。其他项
E[h(a)Z]为零；即使给定
h(a)，彼此的哈希值也同样可能为正负1，因此期望值为零。
实际上，哈希函数不需要是统一的随机数，这是件好事：没有办法存储它。哈希函数必须成对独立（两个特定的哈希值是独立的）就足够了。对于我们的简单示例，以下四个函数的随机选择就足够了。
abc++++---+---+
我将把新的计算留给您。
