伯努利算法，白努力大数定律

伯努利试验

硬币拥有正反两面，一次的上抛至落下，最终出现正反面的概率都是50%。假设一直抛硬币，直到它出现正面为止，我们记录为一次完整的试验，间中可能抛了一次就出现了正面，也可能抛了4次才出现正面。无论抛了多少次，只要出现了正面，就记录为一次试验。这个试验就是伯努利试验。

那么对于多次的伯努利试验，假设这个多次为n次。就意味着出现了n次的正面。假设每次伯努利试验所经历了的抛掷次数为k。第一次伯努利试验，次数设为k1，以此类推，第n次对应的是kn。

其中，对于这n次伯努利试验中，必然会有一个最大的抛掷次数k，例如抛了12次才出现正面，那么称这个为k_max，代表抛了最多的次数。

伯努利试验容易得出有以下结论：

  1. n 次伯努利过程的投掷次数都不大于 k_max。
  2. n 次伯努利过程，至少有一次投掷次数等于 k_max

最终结合极大似然估算的方法，发现在n和k_max中存在估算关联：n = 2^(k_max)

但这种算法，在小数据规模估算误差较大

修正1. LogLog求和求平均数 C*n*2(∑k_max)/n

修正2. HyperLogLog 内部平均换成调和平均算法，C*n* n/ ∑1/2k_max降低小数据误差

转化成实现模型

  1. key转成bit串，视为一组伯努利试验

  2. 分桶，视为n次伯努利试验

    在redis中一共有16384组，每组6个bit， 一共12k

  3. 映射过程 一个key生成64位的bit串，分两部分，前14代表桶，2^14正好是16384，剩下50位的做试验,观测k_max保存到对应的桶中。50位对应最大的二进制110010，六位就能表达。

    1. 这就是pfadd的原理，pfcount就是按照公式计算
    2. 如果落到同一个桶，大则更新，否则不变

  4. 和Log啥关系？上面公式中的C和p相关，其中p=log2n

    switch (p) {
   case 4:
       constant = 0.673 * n * n;
   case 5:
       constant = 0.697 * n * n;
   case 6:
       constant = 0.709 * n * n;
   default:
       constant = (0.7213 / (1 + 1.079 / n)) * n * n;
}

优化？

ref

  • https://juejin.im/post/5c7900bf518825407c7eafd0
  • 观察hyperloglog http://content.research.neustar.biz/blog/hll.html