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

伯努利试验

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

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

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

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

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

最终结合极大似然估算的方法,发现在nk_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