ボールをビンに入れる問題

ボールをビンに入れる問題(またはバランスのとれた割り当て)は、確率論における古典的な問題であり、コンピュータ サイエンスで多くの応用があります。この問題には、m 個のボールとn 個のボックス (または「ビン」) が含まれます。毎回、1 つのボールがビンの 1 つに配置されます。すべてのボールがビンに入った後、各ビンのボールの数を確認します。この数をビンの負荷と呼びます。この問題は、多項分布を使用してモデル化でき、次のような質問をする場合があります。ボールが入っているビンの予想数はいくつですか? ^[1]

明らかに、各ボールを最も負荷の少ないビンに入れることによって、負荷をm / nまで小さくすることは可能です。興味深いケースは、ビンがランダムに、または少なくとも部分的にランダムに選択される場合です。強力なボールインビンパラダイムは、「2 つのランダム選択の累乗^[2]」であり、各ボールは 2 つ (またはそれ以上) のランダムなビンを選択し、負荷の少ないビンに配置されます。このパラダイムは、共有メモリエミュレーション、効率的なハッシュスキーム、サーバー上のタスクのランダムな負荷分散、並列ネットワークとデータセンター内のパケットのルーティングなど、幅広い実用的なアプリケーションが見つかりました。^[2]

各ボールのビンが他の選択とは無関係にランダムに選択される場合、最大負荷は まで大きくなる可能性があります。ただし、高い確率 で成立するより厳しい境界を計算することは可能です。「高い確率」とは確率、つまり が無限大に大きくなるときに確率が になる傾向にあることです。 ${\displaystyle m}$${\displaystyle 1-o(1)}$${\displaystyle 1}$${\displaystyle n}$

の場合、最大荷重は確率的に次のようになる: ^{[3] [4]}${\displaystyle m=n}$${\displaystyle 1-o(1)}$

${\displaystyle {\frac {\log n}{\log \log n}}\cdot (1+o(1))}$。

ゴネット^[5]は 、最大荷重の期待値に厳密な上限を与えた。これは に対してであり、はガンマ関数の逆関数であり、 であることが知られている^[6]。 ${\displaystyle m=n}$${\displaystyle \Gamma ^{-1}(n)-{\frac {3}{2}}+o(1)}$${\displaystyle \Gamma^{-1}}$${\displaystyle \Gamma ^{-1}(n)={\frac {\log n}{\log \log n}}\cdot (1+o(1))}$

最大荷重は についても計算することができ、例えば については であり、についてはである確率が高い。^[7]${\displaystyle m\neq n}$${\displaystyle m>n\log n}$${\displaystyle {\frac {m}{n}}+\Theta \left({\sqrt {\frac {m\log n}{n}}}\right)}$${\displaystyle m<n/\log n}$${\displaystyle \Theta \left({\frac {\log n}{\log(n/m)}}\right)}$

小さい場合の正確な確率は、OEIS A208250 で定義されている ように計算できます。${\displaystyle m=n}$${\displaystyle a(n)/n^{n}}$${\displaystyle a(n)}$

各ボールに対してランダムにビンを選択する代わりに、各ボールに対して 2 つ以上のビンを選択し、最も負荷の少ないビンにボールを入れることも可能です。これは、すべてのビンをチェックして最も負荷の少ないビンを選択する決定論的な割り当てと、他のビンをチェックせずに 1 つのビンを選択する完全にランダムな割り当ての間の妥協案です。このパラダイムは「2 つのランダム選択の力」と呼ばれることが多く、以下のさまざまな設定で研究されています。^[2]

最も単純なケースでは、ボールをビン（）に順番に1つずつ割り当て、各ボールに対して各ステップでランダムなビンを選択し、選択されたビンの中で最も負荷の少ないビンにボールを割り当てる（同点の場合は任意に決定）と、最大負荷は次のようになる確率が高い。^[8]${\displaystyle m}$${\displaystyle n}$${\displaystyle m=n}$${\displaystyle d\geq 2}$

${\displaystyle {\frac {\log \log n}{\log d}}+\Theta (1)}$

これは、完全にランダムな割り当ての場合よりもほぼ指数的に小さくなります。

この結果は、最大荷重が次のようになる確率が高い場合（ ）に一般化できる。 ^[9]${\displaystyle m\geq n}$${\displaystyle d\geq 2}$

${\displaystyle {\frac {m}{n}}+{\frac {\log \log n}{\log d}}+\Theta (1)}$

これは、加法定数まで厳密です。(すべての境界は、少なくとも任意の定数 に対して確率で保持されます。) の場合、ランダム割り当てプロセスは高い確率で の最大負荷のみを与えるため、これら 2 つのプロセス間の改善は の大きな値に対して特に顕著であることに注意してください。 ${\displaystyle 1-1/n^{c}}$${\displaystyle c>0}$${\displaystyle m>n\log n}$${\displaystyle {\frac {m}{n}}+O\left(\log \log n\right)}$${\displaystyle m}$

このパラダイムの他の主要なバリエーションとしては、ボールがランダムなビンを並行して選択する「並列ボール・イン・ビン」 ^[10]、ボールに非単位の重みがある「重み付きボール・イン・ビン」 ^{[11] [12] [13]}、ボールの追加と削除が可能な「削除付きボール・イン・ビン」^{[2] [14]などがある。}${\displaystyle n}$${\displaystyle d}$

m個のボールを単に配置する代わりに、各タイムステップでボールを1個追加し、1個取り出すという無限プロセスを検討して、ボールの数が一定になるようにすることができます。m = nの場合、十分に長い時間が経過すると、ランダム割り当てと部分ランダム割り当ての両方で、最大負荷は有限バージョンと高い確率で類似します。^[8]

このプロセスの繰り返し変形では、ボールは最初に任意の方法でビンに分配され、その後、離散時間プロセスのすべての後続のステップで、各空でないビンから1つのボールが選択され、ランダムにビンの1つに再割り当てされます。のとき、高い確率でプロセスはステップ後に最大負荷の構成に収束することが示されている。^[15]${\displaystyle m}$${\displaystyle n}$${\displaystyle n}$${\displaystyle m=n}$${\displaystyle {\mathcal {O}}(\log(n))}$${\displaystyle {\mathcal {O}}(n)}$

オンライン負荷分散: ^[16] n台の同一コンピュータのセットを考えてみましょう。コンピューティング サービスを必要とするユーザーはn人います。ユーザーは調整されておらず、各ユーザーが自分で使用したいコンピュータを選択します。各ユーザーはもちろん、負荷が最も少ないコンピュータを選択したいと考えますが、これには各コンピュータの負荷を確認する必要があり、長い時間がかかる可能性があります。別のオプションは、コンピュータをランダムに選択することです。この場合、高い確率で最大負荷が になります。考えられる妥協案は、ユーザーが 2 台のコンピュータのみを確認し、負荷の少ない方を使用することです。この場合、高い確率で最大負荷が とはるかに小さくなります。 ${\displaystyle {\frac {\log n}{\log \log n}}\cdot (1+o(1))}$${\displaystyle \log _{2}\log n+\Theta (1)}$

ハッシュ:同じ場所にマップされたすべてのキーがリンクリストに格納されているハッシュテーブルを考えてみましょう。キーへのアクセス効率は、リストの長さに依存します。均一な確率で場所を選択する単一のハッシュ関数を使用する場合、最長のチェーンにキーが含まれる可能性が高くなります。改善策としては、2つのハッシュ関数を使用し、新しいキーを2つのリストのうち短い方に入れることです。この場合、最長のチェーンには要素のみが含まれる可能性が高くなります。 ^[17]${\displaystyle O\left({\frac {\log n}{\log \log n}}\right)}$${\displaystyle O(\log \log n)}$

公平なケーキカット：人々の間で異質なリソースを部分的に比例配分する問題を考えてみましょう全体の価値として評価するリソースの一部を受け取ります。ここで、は十分に大きな定数です。エドモンズ-プルースプロトコルは、ボールをビンに入れる議論を利用して分析するランダム化アルゴリズムです。 ^[18]${\displaystyle n}$${\displaystyle 1/an}$${\displaystyle a}$