サーバー間でメモを比較することにより、メール検出の重複の確率
-
16-10-2019 - |
質問
次の問題があります。
電子メールサーバーにフィルタリング戦略を実装して、スパムメッセージの数を削減します。各サーバーにはバッファがあり、電子メールを送信する前に、独自のバッファーに同じメッセージが複製されているかどうかを確認し、k異なる隣接サーバーをランダムに連絡して、複製が別のバッファーにあるかどうかを確認します。重複したメッセージが検出された場合、スパムとして削除されます。そうしないと、すべての否定的な返信が受信された後に送信されます。
Nメールサーバーがあると仮定し、スパマーが各スパムメールのMコピーを送信すると仮定します。すべてのコピーが同時に送信され、各メールが電子メールサーバーにランダムにルーティングされると想定しています。
m、n、kを考えると、スパムメッセージが削除されない確率を見つける必要があります(つまり、サーバーはスパムを検出しません)、すべてのスパムメッセージが削除され(すべてのサーバーがスパムを検出)、スパムメッセージは少なくとも1つのサーバーから削除されます。
これまでのところ、私は繰り返しのない組み合わせを使用して、MとNを考慮する必要があるケースを見つける必要があります。今、1つのサーバーが少なくとも2つのメッセージを受信する確率を見つける必要がありますが、私は完全な損失。問題についての洞察を提供していただけますか?
解決
特定のサーバーが$ m leq m $コピーを受信した場合、$ mm $コピーを受け取りません。また、$ m $から$ m $メッセージを選択する方法はたくさんあります。それらすべてを考慮する必要があります。さらに、重要な仮定はそれです
- 「ランダムに」は「ランダムに均一に」を意味します。つまり、特定のコピーが特定のサーバーに渡される可能性は$ frac {1} {n} $であり、
- 各コピーは兄弟とは独立してルーティングされています。つまり、個々のコピーに独立したランダムイベントがあります。
これは、確率$ operatorname {pr}(s_i = m)$を合わせるために必要なすべてです。
上記をまとめると、わかります
$ qquad displaystyle operatorname {pr}(s_i = m)= binom {m} {m} left( frac {1} {n} 右)^m left(1 - frac {1} {n} right)^{mm} $
$ s_i $がコピーの数である場合、$ i $ -thサーバーが受信する$ 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 $のために独立しています。基礎となる確率分布はよく研究されています 多項分布.