Вероятности обнаружения дублирования почты путем сравнения заметок между серверами

Question

У меня есть следующая проблема:

Мы хотим реализовать стратегию фильтрации на серверах электронной почты, чтобы уменьшить количество спам-сообщений. У каждого сервера будет буфер, и перед отправкой электронной почты он проверяет, есть ли дубликат одного и того же сообщения в его собственном буфере и контакты k различные соседние серверы случайным образом, чтобы проверить, находится ли дубликат в другом буфере. В случае обнаружения какого -либо дубликата, оно будет удалено как спам, в противном случае оно будет отправлено после получения всех отрицательных ответов.

Предположим, что есть N Mail Servers, и что спамер отправляет M копии каждой спам -почты. Мы предполагаем, что все копии отправляются одновременно и что каждая почта маршрутизируется на почтовый сервер случайным образом.

Учитывая M, N и K, мне нужно выяснить вероятности того, что никакие спам -сообщения не удаляются (то есть ни один сервер не обнаруживает спам), все сообщения спама удаляются (все серверы обнаруживают спам), а спам -сообщения удаляются с по крайней мере на одном сервере.

До сих пор я использовал комбинации без повторения, чтобы выяснить случаи, которые необходимо учитывать для M и N. Теперь мне нужно выяснить вероятность того, что один сервер получает как минимум две копии сообщения, но я при полной потерь. Не могли бы вы дать некоторое представление о проблеме?

Answer 1

Если данный сервер получает копии $ m leq m $, он не получает копии $ mm $. Кроме того, есть много способов выбрать сообщения $ M $ из $ M $; Вы должны рассмотреть их все. Кроме того, важными предположениями являются то, что

• «Случайно» означает «равномерно случайно», то есть вероятность того, что любая данная копия переходит на любой данное сервер $ frac {1} {n} $, и что
• Каждая копия направляется независимо от своих братьев и сестер, то есть у нас есть независимые случайные события для отдельных копий.

Это все, что вам нужно, чтобы собрать воедино вероятность $ operatorname {pr} (s_i = m) $ Этот сервер $ i $ получает сообщения $ m $.

Если вы сложите вышеперечисленное, вы получите

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

Для того, чтобы $ s_i $ является количеством копий, получает сервер $ i $ -h, 1 $ leq i leq n $. Вы должны распознать этот вид веса.

Если у вас есть сомнения, что это правильно, запустите немного симуляции (не доказательство!).

Теперь легко вычислить $ operatorname {pr} (s_i geq 2) = 1 - operatorname {pr} (s_i = 1) - operatorname {pr} (s_i = 0) $.

При использовании полученного веса в других расчетах имейте в виду, что $ s_i $ нет независимо, потому что $ sum_ {i = 1}^n s_i = m $. Основное распределение вероятностей является хорошо изученным многономиальное распределение.