توپ و جعبه

مسئله توپ-و-جعبه یک مسئله کلاسیک در نظریه احتمال است که کاربردهای بسیاری در علوم کامپیوتر دارد. این مسئله شامل m توپ و n جعبه (یا "سطل") است. هر بار یک توپ در یک جعبه قرار داده می‌شود. پس از آنکه همه توپ‌ها در جعبه‌ها قرار گرفت، تعداد هر جعبه را بار (load) آن جعبه می‌نامیم. در این مسئله یافتن مقدار یا یک کران برای بیشینه (ماکزیمم) بار حائز اهمیت است.

بدیهی است که می‌توان با قرار دادن توپ در جعبه با کمترین بار به بار m/n رسید. در انتخاب جعبه‌ها مسئله وقتی در حوزه احتمالات قرار می‌گیرد که جعبه‌ها کاملاً (تخصیص تصادفی کامل) یا بعضاً (تخصیص تصادفی جزئی) به صورت تصادفی انتخاب شوند.

تخصیص تصادفی کامل

زمانی که برای هر توپ، جعبه به‌طور تصادفی و مستقل از دیگر انتخاب‌ها، انتخاب می‌شود، بیشینه بار ممکن است به بزرگی $m$. هرچند می‌توان یک کران محدود برای «حداکثر بار» که با احتمال بالا صادق است، به‌دست آورد. یک «احتمال بالا» یک احتمال $1-o(1)$ یعنی زمانی که n به سمت بینهایت میل می‌کند، احتمال به $1$ میل خواهد کرد.

برای مورد $m=n$ با احتمال بالا حداکثر بار:

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

Gonnet یک کران محدود برای امید ریاضی بیشینه بار به‌دست آورد که برای $m=n$ برابر $\Gamma ^{(-1)}(n)-{\frac {3}{2}}+o(1)$. $\Gamma ^{(-1)}$ معکوس تابع گاماست و برابراست با $\Gamma ^{(-1)}(n)={\frac {\log n}{\log \log n}}(1+o(1))$

بیشینه بار همچنین می‌تواند برای $m\neq n$ محاسبه شود. به عنوان مثال برای $m>n\log n$ مقدار بیشینه بار با احتمال بالا برابر است با ${\frac {m}{n}}+\Theta ({\sqrt {\frac {m\log n}{n}}})$و برای $m<n/\log n$ با احتمال بالا برابر است با $\Theta ({\frac {\log n}{\log(n/m)}})$.

تخصیص تصادفی جزئی

به‌جای انتخاب تصادفی جعبه برای هر توپ، می‌توان دو جعبه یا بیشتر به صورت تصادفی انتخاب کرد و توپ را در جعبه با بار کمتر قرار داد. تخصیص تصادفی جزئی، بین حالت تخصیص قطعی که در آن جعبهٔ با بار کمتر انتخاب می‌شود و حالت کاملاً تصادفی قرار دارد که در آن جعبه به صورت کاملاً تصادفی بدون توجه به بار جاری آن انتخاب می‌شود.

در این حالت اگر m توپ و n جعبه داشته باشیم (که m=n) و برای هر توپ $d\geq 2$ جعبه به صورت تصادفی در هر مرحله انتخاب شود و سپس توپ در جعبه با بار کمتر از بین d جعبه قرار داده شود، آنگاه با احتمال بالا بیشینه بار برابر است با:

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

که به صورت نمایی کمتر از تخصیص تصادفی کلی است.

می‌توان برای $m\geq n$ (که $d\geq 2$) نیز این نتیجه را تعمیم داد، که با احتمال بالا بیشینه بار برابر است با:

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

توجه شود که برای $m>n\log n$ ${\frac {m}{n}}+\Theta ({\sqrt {\frac {m\log n}{n}}})$ را به‌دست می‌دهد. بهبود بین این دو فرایند به ویژه برای $m$.

جریان بی‌نهایت از توپ‌ها

به جای قرار دادن m توپ، می‌توان حالتی را در نظر گرفت که در آن در یک فرایند نامحدود، یک توپ قرار داده شود و یک توپ برداشته شود به نحوی که تعداد توپ‌ها همواره ثابت بماند. برای m=n، پس از یک زمان طولانی، با احتمالاً بالا بار بیشینه شبیه نسخه نامتناهی مسئله، هم برای تخصیص تصادفی کلی و هم برای تخصیص تصادفی جزئی می‌شود.

کاربردها

تخصیص پویای منابع: تعداد n دستگاه کامپیوتر یکسان را در نظر بگیرید. n کاربر هم وجود دارند. کاربران با یکدیگر هماهنگ نیستند و هر کاربر کامپیوتری را که می‌خواهد انتخاب می‌کند. هر کاربر منطقا کامپیوتر با بار کمینه را انتخاب خواهد کرد، که البته لازمه آن این است که بار روی هر کامپیوتر محاسبه شود و این خود ممکن است زمان طولانی ای نیاز داشته باشد. راه دیگر این است که هر کاربر کامپیوتری را به صورت تصادفی انتخاب کند، که در این حالت با احتمال بالا بار بیشینه ${\frac {\log n}{\log \log n}}$${\frac {\log \log n}{\log 2}}$

درهم سازی (Hashing): یک جدول درهم سازی را در نظر بگیرید که در آن همه کلیدهایی که به یک محل نگاشت شده‌اند در یک لیست پیوندی ذخیره می‌شوند. بازدهی دسترسی به کلید به طول لیست بستگی دارد. اگر از یک تابع درهم سازی استفاده کنیم که که مکان‌ها را با احتمال یکنوا انتخاب می‌کند، با احتمال بالا طولانی‌ترین زنجیره (لیست) $O\left({\frac {\log n}{\log \log n}}\right)$ کلید دارد. یک بهبود برای این وضعیت استفاده از دو تابع درهم سازی و قرار دادن کلید در لیست کوتاه‌تر است. در این حالت با احتمال بالا طولانی‌ترین زنجیره فقط $O(\log \log n)$ عنصر دارد.

Proportional division.