Wahrscheinlichkeiten der doppelten Posterkennung durch Vergleich von Notizen zwischen Servern

Question

Ich habe das folgende Problem:

Wir möchten eine Filterstrategie in E-Mail-Servern implementieren, um die Anzahl der Spam-Nachrichten zu reduzieren. Jeder Server verfügt über einen Puffer, und vor dem Senden einer E-Mail werden in seinem eigenen Puffer ein Duplikat derselben Nachricht vorhanden, und kontaktiert sich zufällig, um zu überprüfen, ob sich das Duplikat in einem anderen Puffer befindet. Falls eine doppelte Nachricht erkannt wird, wird sie als Spam gelöscht, sonst wird sie gesendet, nachdem alle negativen Antworten empfangen werden.

Nehmen wir an, dass es N -Mail -Server gibt und dass ein Spammer m Kopien jeder Spam -Mail sendet. Wir gehen davon aus, dass alle Kopien gleichzeitig gesendet werden und dass jede E -Mail zufällig an einen Mailserver weitergeleitet wird.

Angesichts m, n und k muss ich herausfinden, welche Wahrscheinlichkeiten keine Spam -Nachricht gelöscht werden (dh kein Server erkennt Spam), alle Spam -Nachrichten werden gelöscht (alle Server erkennen Spam) und Spam -Nachrichten werden von mindestens einem Server gelöscht.

Bisher habe ich Kombinationen ohne Wiederholung verwendet, um die Fälle herauszufinden, die ein M und N berücksichtigt werden müssen. Jetzt muss ich herausfinden, wie wahrscheinlich ein Server mindestens zwei Kopien einer Nachricht empfängt, aber ich bin es bei vollem Verlust. Könnten Sie bitte einen Einblick in das Problem geben?

Answer 1

Wenn ein bestimmter Server $ M Leq M $ Copies empfängt, erhält er nicht $ mm $ Copies. Es gibt auch viele Möglichkeiten, $ M $ Nachrichten aus $ M $ auszuwählen. Sie müssen sie alle berücksichtigen. Darüber hinaus sind wichtige Annahmen, dass das

• "zufällig" bedeutet "einheitlich bei zufällig", das ist die Wahrscheinlichkeit, dass eine bestimmte Kopie auf einen bestimmten Server geht $ frac {1} {n} $ und das
• Jede Kopie wird unabhängig von ihren Geschwistern geleitet, dh, wir haben unabhängige zufällige Ereignisse für die einzelnen Kopien.

Dies ist alles, was Sie benötigen, um die Wahrscheinlichkeit $ operatorname {pr} (s_i = m) $ zusammenzustellen, dass der Server $ i $ $ m $ Nachrichten erhält.

Wenn Sie das oben zusammensetzen, bekommen Sie

$ qquad displaystyle operatorname {pr} (s_i = m) = binom {m} {m} links ( frac {1} {n} rechts)^M links (1 - frac {1} {N} rechts)^{mm} $

Für $ S_I $ ist die Anzahl der Kopien, die der Server $ i $ -TH erhält, $ 1 Leq i Leq n $. Sie sollten diese Art von Wahrscheinlichkeitsgewicht erkennen.

Wenn Sie Zweifel haben, dass dies korrekt ist, führen Sie etwas aus Simulationen (kein Beweis!).

Jetzt ist es einfach, $ operatorname {pr} (s_i geq 2) = 1 - operatorname {pr} (s_i = 1) - operatorname {pr} (s_i = 0) $ zu berechnen.

Beachten Sie bei Verwendung des abgeleiteten Gewichts in anderen Berechnungen, dass die $ s_i $ sind nicht unabhängig, weil $ sum_ {i = 1}^n s_i = m $. Die zugrunde liegende Wahrscheinlichkeitsverteilung ist die gut untersuchte Multinomiale Verteilung.