Le probabilità di rilevazione elettronica duplicati, confrontando le note tra i server

Question

Ho il seguente problema:

Vogliamo attuare una strategia di filtraggio in server di posta elettronica per ridurre il numero di messaggi di spam. Ogni server avrà un buffer, e prima di inviare una e-mail, controlla se c'è un duplicato dello stesso messaggio nel proprio buffer e contatti k server vicini distinti a caso per verificare se il duplicato è in un altro buffer. Nel caso in cui viene rilevato un messaggio duplicato, verrà eliminato come spam, in caso contrario verrà inviata dopo tutte le risposte negative vengono ricevuti.

Supponiamo che ci sono i server di posta N, e che uno spammer invia M copie di ogni mail di spam. Partiamo dal presupposto che tutte le copie vengono inviate simultaneamente e che ogni messaggio viene instradato a un server di posta in modo casuale.

M Dato, N e K ho bisogno di scoprire le probabilità che nessun messaggio di spam viene eliminato (cioè non rileva di server di spam), tutti i messaggi spam vengono cancellati (tutti i server rilevare lo spam) e messaggi di spam vengono eliminati dalla ad almeno un server.

Finora, ho usato combinazioni senza ripetizione per scoprire i casi che devono essere prese in considerazione per un bisogno M e N. Ora per scoprire la probabilità che un server riceve almeno due copie di un messaggio, ma io sono in perdita completa. La prego di fornire qualche informazione sul problema?

Answer 1

Se un determinato server riceve $ m \ leq M $ copie, ma non riceve $ M-m $ copie. Inoltre, ci sono molti modi per scegliere $ m $ messages di $ M $; è necessario considerare tutti loro. Inoltre, le ipotesi sono importanti che

• "a caso" significa "uniformemente a caso", che è la probabilità che un dato copia va a un determinato server è $ \ frac {1} {N} $, e che
• ogni copia viene instradato indipendentemente dai suoi fratelli, che è che abbiamo eventi casuali indipendenti per le singole copie.

Questo è tutto ciò che serve per mettere insieme la probabilità $ \ operatorname {} Pr (S_i = m) $ quel server $ i $ riceve $ m $ messages.

Se si mette l'insieme di cui sopra, si ottiene

$ \ Qquad \ displaystyle \ operatorname {Pr} (S_i = m) = \ binom {M} {m} \ left (\ frac {1} {N} \ right) ^ m \ left (1 - \ frac {1} {N} \ right) ^ {MM} $

a $ S_i $ è il numero di copie del $ i $ -esimo del server riceve, $ 1 \ leq i \ leq N $. Si dovrebbe riconoscere questo tipo di peso probabilità.

Se avete dubbi che questo è corretto, eseguire alcuni simulazioni (non una prova!).

Ora è facile calcolare $ \ operatorname {Pr} (S_i \ geq 2) = 1 - \ operatorname {Pr} (S_i = 1) -. \ Operatorname {Pr} (S_i = 0) $

Quando si utilizza il peso derivato in altri calcuations, tenere presente che il $ S_i $ sono non indipendente perché $ \ sum_ {i = 1} ^ N S_i = M $. La distribuzione di probabilità sottostante è il ben studiato multinomiale distribuzione .