Probabilités de détection des doublons de courrier en comparant les notes entre les serveurs

Question

J'ai le problème suivant:

  

Nous voulons mettre en œuvre une stratégie de filtrage dans les serveurs de courrier électronique afin de réduire le nombre de messages de spam. Chaque serveur aura un tampon, et avant d'envoyer un e-mail, il vérifie s'il y a un double du même message dans son propre tampon et contacts k serveurs distincts voisins au hasard pour vérifier si le double est dans un autre tampon. Dans le cas où un message en double est détecté, il sera supprimé comme spam, sinon il sera envoyé après que toutes les réponses négatives sont reçues.

     

Supposons qu'il ya N serveurs de messagerie, et qu'un spammeur envoie des copies M de chaque courrier indésirable. Nous partons du principe que toutes les copies sont envoyées en même temps et que chaque courrier est acheminé vers un serveur de messagerie au hasard.

Compte tenu de M, N et k Je dois trouver les probabilités qu'aucun message de spam est supprimé (pas de serveur identifie le courrier indésirable), tous les messages de spam sont supprimés (tous les serveurs détecter les spams) et des messages de spam sont supprimés au moins un serveur.

Jusqu'à présent, je l'ai utilisé des combinaisons sans répétition pour connaître les cas qui doivent être pris en compte pour un M et N. Maintenant, je besoin de savoir la probabilité qu'un serveur reçoit au moins deux copies d'un message, mais je suis à la perte complète. Pourriez-vous s'il vous plaît donner un aperçu du problème?

Answer 1

Si un serveur donné reçoit $ m \ leq M $ exemplaires, il ne reçoit pas de copies M $-m $. En outre, il y a plusieurs façons de choisir $ m $ messages de $ M $; vous devez considérer tous. En outre, les hypothèses importantes sont que

• « au hasard » signifie « uniformément au hasard », qui est la probabilité que toute copie donnée va à un serveur donné est $ \ frac {1} {N} $, et que
• chaque copie est acheminée indépendamment de ses frères et sœurs, qui est que nous avons des événements aléatoires indépendants pour les copies individuelles.

Ceci est tout ce que vous devez assembler la probabilité $ \ {operatorname Pr} (S_i = m) $ ce serveur $ $ i reçoit $ m $ messages.

  

Si vous mettez l'ensemble ci-dessus, vous obtenez

 $ \ Qquad \ displaystyle \ operatorname {Pr} (S_i = m) = \ binom {M} {m} \ left (\ frac {1} {N} \ right) ^ m \ left (1 - \ frac {1} {N} \ right) ^ {} $
Mm
 pour $ S_i $ étant le nombre de copies $ i $ serveur -ème reçoit, $ 1 \ leq i \ leq N $. Vous devez reconnaître ce genre de poids de probabilité.

 Si vous avez des doutes que cela est correct, exécutez une simulations (pas une preuve!).

Maintenant, il est facile de calculer $ \ operatorname {Pr} (S_i \ geq 2) = 1 - \ operatorname {Pr} (S_i = 1) -. \ Operatorname {Pr} (S_i = 0) $

  

Lors de l'utilisation du poids dérivé dans d'autres calcuations, gardez à l'esprit que le $ S_i $ sont pas indépendant parce que $ \ sum_ {i = 1} ^ N S_i = M $. La distribution de probabilité sous-jacente est bien étudiée distribution multinomiale de href="https://en.wikipedia.org/wiki/Multinomial_distribution".