通过比较服务器之间的笔记，重复邮件检测的概率

Question

我有以下问题：

我们希望在电子邮件服务器中实现过滤策略，以减少垃圾邮件消息的数量。每个服务器都会有一个缓冲区，在发送电子邮件之前，它检查是否在其自身的缓冲区中有相同消息的重复，并随机与k个不同的相邻服务器联系，以检查重复项是否在另一个缓冲区中。如果检测到任何重复消息，它将被删除为垃圾邮件，否则将在收到所有负面答复后将其发送。

让我们假设有n个邮件服务器，并且一个垃圾邮件发送者发送每个垃圾邮件邮件的副本。我们假设所有副本都是同时发送的，并且每个邮件都会随机路由到邮件服务器。

给定M，N和K，我需要找出未删除垃圾邮件消息的概率（即没有服务器检测到垃圾邮件），所有垃圾邮件消息均已删除（所有服务器都检测到垃圾邮件），并从至少一台服务器处删除垃圾邮件消息。

到目前为止，我已经使用不重复的组合来找出需要考虑M和N的情况。完全损失。您能否对问题提供一些见解？

Answer 1

如果给定的服务器收到$ M leq m $副本，则不会收到$ mm $ copies。此外，有很多方法可以从$ m $中选择$ m $消息；您必须考虑所有这些。此外，重要的假设是

• “随机”是指“随机均匀地”，这就是任何给定副本输入任何给定服务器的概率是$ frac {1} {n} $，并且
• 每个副本都是独立于其兄弟姐妹的路由，即我们为单个副本提供独立的随机事件。

这就是您需要将概率$ operatatorName {pr}（s_i = m）$组合在一起，该服务器$ i $接收$ m $消息。

如果将上述放在一起，您会得到

$ qquad displayStyle operatorName {pr}（s_i = m）= binom {m} {m} {m} {m} left（ frac {1} {n} {n} right）^m left（1 - frac {1}} {n} right）^{mm} $

对于$ s_i $，是$ i $ th服务器收到的副本数量，$ 1 leq i leq n $。您应该识别这种概率重量。

如果您怀疑这是正确的，请运行一些 模拟 （不是证明！）。

现在很容易计算$ operatatorName {pr}（s_i geq 2）= 1 - operatatorName {pr}（s_i = 1） - operatatorName {pr}（s_i = 0）$。

在其他计算中使用派生的重量时，请记住$ S_I $是 不是 独立，因为$ sum_ {i = 1}^n s_i = m $。潜在的概率分布是经过充分研究的 多项式分布.