توپ و جعبه
مسئلهتوپ-و-جعبه یک مسئله کلاسیک در نظریه احتمال است که کاربردهای بسیاری در علوم کامپیوتر دارد. این مسئله شامل "m" توپ و "n" جعبه (یا "سطل") است. هر بار یک توپ در یک جعبه قرار داده می‌شود. پس از آنکه همه توپ‌ها در جعبه‌ها قرار گرفت، تعداد هر جعبه را بار (load) آن جعبه می‌نامیم. در این مسئله یافتن مقدار یا یک کران برای بیشینه (ماکزیمم) بار حائز اهمیت است.
بدیهی است که می‌توان با قرار دادن توپ در جعبه با کمترین بار به بار m/n رسید. در انتخاب جعبه‌ها مسئله وقتی در حوزه احتمالات قرار می‌گیرد که جعبه‌ها کاملاً (تخصیص تصادفی کامل) یا بعضاً (تخصیص تصادفی جزئی) به صورت تصادفی انتخاب شوند.
زمانی که برای هر توپ، جعبه به‌طور تصادفی و مستقل از دیگر انتخاب‌ها، انتخاب می‌شود، بیشینه بار ممکن است به بزرگی formula_1. هرچند می‌توان یک کران محدود برای «حداکثر بار» که با احتمال بالا صادق است، بدست آورد. یک «احتمال بالا» یک احتمال formula_2 یعنی زمانی که n به سمت بینهایت میل می‌کند، احتمال به formula_3 میل خواهد کرد.
برای مورد formula_4 با احتمال بالا حداکثر بار:
formula_5.
Gonnet یک کران محدود برای امید ریاضی بیشینه بار بدست آورد که برای formula_4 برابر formula_7. formula_8 معکوس تابع گاماست و برابراست با formula_9
بیشینه بار همچنین می‌تواند برای formula_10 محاسبه شود. به عنوان مثال برای formula_11 مقدار بشینه بار با احتمال بالا برابر است با formula_12و برای formula_13 با احتمال بالا برابر است با formula_14.
بجای انتخاب تصادفی جعبه برای هر توپ، می‌توان دو جعبه یا بیشتر به صورت تصادفی انتخاب کرد و توپ را در جعبه با بار کمتر قرار داد. تخصیص تصادفی جزئی، بین حالت تخصیص قطعی که در آن جعبهٔ با بار کمتر انتخاب می‌شود و حالت کاملاً تصادفی قرار دارد که در آن جعبه به صورت کاملاً تصادفی بدون توجه به بار جاری آن انتخاب می‌شود.
formula_15
که به صورت نمایی کمتر از تخصیص تصادفی کلی است.
می‌توان برای formula_16 (که formula_17) نیز این نتیجه را تعمیم داد، که با احتمال بالا بیشینه بار برابر است با:
formula_18
توجه شود که برای formula_11 formula_12 را بدست می‌دهد. بهبود بین این دو فرایند به ویژه برای formula_1.
به جای قرار دادن m توپ، می‌توان حالتی را در نظر گرفت که در آن در یک فرایند نامحدود، یک توپ قرار داده شود و یک توپ برداشته شود به نحوی که تعداد توپ‌ها همواره ثابت بماند. برای m=n، پس از یک زمان طولانی، با احتمالاً بالا بار بیشینه شبیه نسخه نامتناهی مسئله، هم برای تخصیص تصادفی کلی و هم برای تخصیص تصادفی جزئی می‌شود.
تخصیص پویای منابع: تعداد n دستگاه کامپیوتر یکسان را در نظر بگیرید. n کاربر هم وجود دارند. کاربران با یکدیگر هماهنگ نیستند و هر کاربر کامپیوتری را که می‌خواهد انتخاب می‌کند. هر کاربر منطقا کامپیوتر با بار کمینه را انتخاب خواهد کرد، که البته لازمه آن این است که بار روی هر کامپیوتر محاسبه شود و این خود ممکن است زمان طولانی ای نیاز داشته باشد. راه دیگر این است که هر کاربر کامپیوتری را به صورت تصادفی انتخاب کند، که در این حالت با احتمال بالا بار بیشینه formula_22formula_23
درهم سازی (Hashing): یک جدول درهم سازی را در نظر بگیرید که در آن همه کلیدهایی که به یک محل نگاشت شده‌اند در یک لیست پیوندی ذخیره می‌شوند. بازدهی دسترسی به کلید به طول لیست بستگی دارد. اگر از "یک "تابع درهم سازی استفاده کنیم که که مکان‌ها را با احتمال یکنوا انتخاب می‌کند، با احتمال بالا طولانی‌ترین زنجیره (لیست) formula_24 کلید دارد. یک بهبود برای این وضعیت استفاده از دو تابع درهم سازی و قرار دادن کلید در لیست کوتاه‌تر است. در این حالت با احتمال بالا طولانی‌ترین زنجیره فقط formula_25 عنصر دارد.
Proportional division.