サーバー間でメモを比較することにより、メール検出の重複の確率

Question

次の問題があります。

電子メールサーバーにフィルタリング戦略を実装して、スパムメッセージの数を削減します。各サーバーにはバッファがあり、電子メールを送信する前に、独自のバッファーに同じメッセージが複製されているかどうかを確認し、k異なる隣接サーバーをランダムに連絡して、複製が別のバッファーにあるかどうかを確認します。重複したメッセージが検出された場合、スパムとして削除されます。そうしないと、すべての否定的な返信が受信された後に送信されます。

Nメールサーバーがあると仮定し、スパマーが各スパムメールのMコピーを送信すると仮定します。すべてのコピーが同時に送信され、各メールが電子メールサーバーにランダムにルーティングされると想定しています。

m、n、kを考えると、スパムメッセージが削除されない確率を見つける必要があります（つまり、サーバーはスパムを検出しません）、すべてのスパムメッセージが削除され（すべてのサーバーがスパムを検出）、スパムメッセージは少なくとも1つのサーバーから削除されます。

これまでのところ、私は繰り返しのない組み合わせを使用して、MとNを考慮する必要があるケースを見つける必要があります。今、1つのサーバーが少なくとも2つのメッセージを受信する確率を見つける必要がありますが、私は完全な損失。問題についての洞察を提供していただけますか？

Answer 1

特定のサーバーが$ 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 $のために独立しています。基礎となる確率分布はよく研究されています 多項分布.