Balanced Allocations: A Simple Proof for the Heavily Loaded Case
Balanced Allocations: A Simple Proof for the Heavily Loaded Case
复制标题
平衡分配：重载情况的简单证明
DOI：
10.1007/978-3-662-43948-7_81
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Udi Wieder
中科院分区：
文献类型：
--
作者：
Kunal Talwar;Udi Wieder
我们给出了一个新的证明，证明了在二选一过程中，无论投掷多少球，最大负荷和平均负荷之间的期望差距是以(1 +o(1))logn为界的。这一令人惊讶的结果的原始证据是贝伦布林克等人的。在[2]中，使用了马尔可夫链理论的工具，以及涉及计算机辅助计算的复杂归纳证明。我们提供了一个明显更简单、更基本的证明。这项新技术允许我们推广结果，并为重力球的情况推导出新的、通常是紧凑的界限。这种简化是以较大的低阶项和较弱的偏离预期概率的尾界为代价的。
We give a new proof for the fact that the expected gap between the maximum load and the average load in the two-choice process is bounded by (1 +o(1))loglogn, irrespective of the number of balls thrown. The original proof of this surprising result, due to Berenbrink et al. in [2], uses tools from Markov chain theory, and a sophisticated induction proof involving computer-aided calculations. We provide a significantly simpler and more elementary proof. The new technique allows us to generalize the result and derive new and often tight bounds for the case of weighted balls. The simplification comes at a cost of larger lower order terms and a weaker tail bound for the probability of deviating from the expectation.