このペアワイズ独立ランダムプロセスは最大負荷$ sqrt {n} $を期待していますか?

これはビンへのボールに関する質問への拡張です:期待される最大負荷$
sqrt {n} $
を持つペアワイズ独立ランダムプロセスの例。次の質問が尋ねられ、肯定的に答えられます:

次のビンを選択してボールを入れて、   期待される最大負荷は$ Theta( sqrt
{n})$に漸近しますか?

私たちが明示的にペアごとに独立したハッシュ関数ファミリー$ h((ax + b) bmod p) bmod
n)$を選択したとします。次の形式の上限を示すのは簡単な標準的な演習です:

geq 1 + sqrt {2n}) leq frac {1} {2} $$($ text)

しかし、この特定のハッシュ関数ファミリの期待される最大負荷に対して、マッチングまたはほぼ一致する下限を見つけることができますか?

ベストアンサー

この最近の論文に示されているように、あなたが与えたハッシュファミリーは最大負荷$ tilde {O}(n ^
{1/3})$を期待しています:

MathiasBækTejs
Knudsen、「線形ハッシングは素晴らしいです」

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です