问有人能解释一下概率计数是如何工作的吗？

EN

我将尝试澄清概率计数器的用法，但请注意，我不是这方面的专家。

其目的是使用很小的空间来存储计数器(例如，使用32位整数)来计数到非常非常大的数字。

莫里斯想出了保持一个“对数计数”的想法，所以计数器保存的不是n，而是log₂(n)。换句话说，给定计数器的值c，由计数器表示的实际计数是2ᶜ。

由于日志通常不是整数值，所以当c计数器应该递增时，问题就出现了，因为我们只能在步长1中递增。

这里的想法是使用“概率计数器”，所以对于计数器上的Increment方法的每一次调用，我们都用概率p更新实际的计数器值。这很有用，因为可以证明具有概率更新的计数器值c表示的期望值实际上是n。换句话说，在n次调用Increment之后，计数器表示的平均值实际上是n(但在任何一个时间点，我们的计数器都可能有错误)！我们正在用很少的存储空间(例如，单个寄存器)来换取计数到非常大的数字的能力。

如莫里斯所描述的，实现这一点的一种方案是使计数器值C表示实际计数2的对数(即，计数器保持实际计数的对数ᶜ)。我们用概率1/2ᶜ更新这个计数器，其中c是计数器的当前值。

请注意，选择这个2的“基数”意味着我们的实际计数始终是2的倍数(因此术语“数量级估计”)。也可以选择其它b>1(典型地使得b< 2)，使得误差较小，但代价是能够计算较小的最大数。

日志日志之所以起作用，是因为在基数2中，数字x需要表示对数₂位。

事实上，还有许多其他近似计数的方案，如果您需要这样的方案，您可能应该研究一下哪种方案对您的应用程序有意义。

参考文献：

有关计数器表示的平均值的证明，请参阅Philippe Flajolet，或者在“算法导论”一书中对问题5-1的解决方案中进行更简单的处理。Morris的论文通常在付费墙后面，我找不到免费版本在这里张贴。

这并不完全适用于对数计数方法，但我认为它可以帮助你，使用莫里斯算法，计数器代表了实际count.The近似的“数量级估计”，在数学上是无偏的。为了递增计数器，使用伪随机事件，使得递增是概率事件。为了节省空间，只保留指数。例如，在基数2中，计数器可以估计计数为1、2、4、8、16、32以及2的所有幂。内存需求只是简单地保存指数。作为示例，为了从4递增到8，将生成伪随机数，使得.25的概率在计数器中产生正变化。否则，计数器将保持在4。来自wiki