-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathballsBins.html
66 lines (66 loc) · 10.5 KB
/
ballsBins.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<link href="https://adriann.github.io/feed.rss" rel="alternate" type="application/rss+xml" title="What's new on adriann.github.io" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="generator" content="pandoc" />
<meta name="author" content="Adrian Neumann ([email protected])" />
<title>One Rule to Distribute them All</title>
<style type="text/css">
.displayequation{margin-left:auto;margin-right:auto;}
</style>
<style>
.caption{font-size:66%;text-align:right;}
.figure{float:right;padding-bottom:1em;padding-left:1em;}
.figure>img{display:block;margin:0 auto;}
.footnotes{font-size:80%;}
.block{border-left:1ex solid gray;padding-left:2em;}
li{padding:0.25em;}
a:hover{text-shadow: 0 0 5px;}
body{font-family:sans-serif;max-width:100ex;padding-left:3em;padding-right:2em;}
code{font-family:Consolas, Inconsolata, Monaco, monospace;}
p{text-align:justify;}
</style>
</head>
<body>
<div id="header">
<h1 class="title">One Rule to Distribute them All</h1>
</div>
<div class="figure">
<img src="pictures/sam.jpg" title="Copyright probably with New Line Cinema" alt="Share… the load" />
<p class="caption">Share… the load</p>
</div>
<p>Suppose you are a poor orkish messenger and have <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> rings to distribute to the <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> elven-kings under the sky. Of course each is supposed to get their own, but you’re lazy and the nasty elves all look the same anyway.</p>
<p>Due to your extensive experience with <del>chaos</del> randomization you quickly see that throwing rings at elves randomly is in expectation just as good. The number of rings for each elf is distributed as <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext mathvariant="normal">Bin</mtext><mo stretchy="false" form="prefix">(</mo><mi>n</mi><mo>,</mo><mn>1</mn><mi>/</mi><mi>n</mi><mo stretchy="false" form="postfix">)</mo></mrow><annotation encoding="application/x-tex">\mbox{Bin}(n,1/n)</annotation></semantics></math>, so the expectation is one. You might also know that binomial random variables are pretty strongly concentrated around their expectation and you don’t think the dependencies between the elves will change anything about that.</p>
<p>Your boss however would like some more arguments why your approach is good enough. Let’s try to compute the maximum number of rings any elf will get.</p>
<p>The knowledgeable reader probably recognizes this as a classical balls-into-bins settings with all the immediate applications to scheduling, hashing, and so forth. From here I will use the more standard nomenclature.</p>
<!--more-->
<h2 id="counting-bins">Counting Bins</h2>
<p>This seems like a difficult problem to tackle, but it turns out we can use the first moment method<a href="#fn1" class="footnoteRef" id="fnref1"><sup>1</sup></a> on appropriately defined random variables.</p>
<p>As it is so often the case, ‘appropriately’ defining things gets you half way to a solution. The first moment method allows us to show that a random variable will be zero asymptotically almost surely. In our application we want to show that there will be no bins with a large number of balls, so let’s define <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>X</mi><mi>_</mi><mi>k</mi></mrow><annotation encoding="application/x-tex">X\_k</annotation></semantics></math> to count the number of bins who have <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>k</mi><annotation encoding="application/x-tex">k</annotation></semantics></math> or more rings.</p>
<p>As we already observed the number of balls is binomially distributed, so it is not so difficult to bound the probability that a bin contains more than <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>k</mi><annotation encoding="application/x-tex">k</annotation></semantics></math>. To make things easier, we will use the Poisson approximation<a href="#fn2" class="footnoteRef" id="fnref2"><sup>2</sup></a> and cheat a little with the constant factors involved. <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mtext mathvariant="normal">Pr</mtext><mo stretchy="false" form="prefix">(</mo><mrow><mtext mathvariant="normal">elf has </mtext><mspace width="0.333em"></mspace></mrow><mo>≥</mo><mi>k</mi><mrow><mspace width="0.333em"></mspace><mtext mathvariant="normal"> rings</mtext></mrow><mo stretchy="false" form="postfix">)</mo><mo>=</mo><mtext mathvariant="normal">Pr</mtext><mo stretchy="false" form="prefix">(</mo><mtext mathvariant="normal">Bin</mtext><mo stretchy="false" form="prefix">(</mo><mi>n</mi><mo>,</mo><mn>1</mn><mi>/</mi><mi>n</mi><mo stretchy="false" form="postfix">)</mo><mo>≥</mo><mi>k</mi><mo stretchy="false" form="postfix">)</mo><mo>≤</mo><mi>n</mi><mtext mathvariant="normal">Pr</mtext><mo stretchy="false" form="prefix">(</mo><mtext mathvariant="normal">Pois</mtext><mo stretchy="false" form="prefix">(</mo><mn>1</mn><mo stretchy="false" form="postfix">)</mo><mo>=</mo><mi>k</mi><mo stretchy="false" form="postfix">)</mo><mo>=</mo><mi>n</mi><msup><mi>e</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>⋅</mo><mfrac><mn>1</mn><mrow><mi>k</mi><mi>!</mi></mrow></mfrac><mo>≈</mo><mi>n</mi><msup><mi>e</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>⋅</mo><msup><mn>2</mn><mrow><mo>−</mo><mi>k</mi><mo>log</mo><mi>k</mi></mrow></msup><mo>≈</mo><msup><mi>e</mi><mrow><mo>log</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>log</mo><mi>k</mi></mrow></msup></mrow><annotation encoding="application/x-tex">\mbox{Pr}(\mbox{elf has }\geq k \mbox{ rings})= \mbox{Pr}(\mbox{Bin}(n,1/n)\geq k) \leq n \mbox{Pr}(\mbox{Pois}(1) = k) =n e^{-1} \cdot \frac{1}{k!}\approx ne^{-1} \cdot 2^{-k \log k} \approx e^{\log n - k \log k}</annotation></semantics></math></p>
<p>We used Stirling to approximate <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mi>!</mi><mo>≈</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>log</mo><mi>k</mi></mrow></msup></mrow><annotation encoding="application/x-tex">k! \approx 2^{k\log k}</annotation></semantics></math>. By defining an indicator for every bin we see that the expectation is just <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mstyle mathvariant="double-struck"><mi>𝔼</mi></mstyle><mo stretchy="false" form="prefix">(</mo><msub><mi>X</mi><mi>k</mi></msub><mo stretchy="false" form="postfix">)</mo><mo>≤</mo><msup><mi>e</mi><mrow><mn>2</mn><mo>log</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>log</mo><mi>k</mi></mrow></msup></mrow><annotation encoding="application/x-tex">\mathbb{E}(X_k) \leq e^{2\log n - k \log k}</annotation></semantics></math>. Clearly this expectation goes to zero for <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo>≥</mo><mfrac><mrow><mi>c</mi><mo>log</mo><mi>n</mi></mrow><mrow><mo>log</mo><mo>log</mo><mi>n</mi></mrow></mfrac></mrow><annotation encoding="application/x-tex">
k \geq \frac{c\log n}{\log \log n}
</annotation></semantics></math> for some suitable <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>c</mi><annotation encoding="application/x-tex">c</annotation></semantics></math>, depending on the exact values of the constants in the exponent.</p>
<h2 id="remarks">Remarks</h2>
<p>Our sloppy calculations show that the number of bins with more than <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false" form="prefix">(</mo><mo>log</mo><mi>n</mi><mi>/</mi><mo>log</mo><mo>log</mo><mi>n</mi><mo stretchy="false" form="postfix">)</mo></mrow><annotation encoding="application/x-tex">O(\log n/\log \log n)</annotation></semantics></math> balls is zero a.a.s., and hence the maximum load is sublogarithmic with high probability. The interested reader might want to show, using a variance calculation, that this bound is tight. Not bad for such a simple algorithm! If you’re feeling adventurous, you can try the exercise at the end of this blog post to see how much a simple twist can improve the algorithm. Perhaps I’ll write a bit about that in a different post.</p>
<p>You might be a little disappointed at how slowly the expectation goes to zero, but rest assured that this is just a symptom of our weak tools. After all we used nothing more advanced than Markov’s inequality! It is entirely possible (and indeed a common textbook example) to derive much stronger bounds by applying Chernoff-type bounds on a series of appropriately conditioned Poisson random variables, see for example chapter 5 of the excellent book <a href="http://books.google.com/books/about/Probability_and_computing.html?id=0bAYl6d7hvkC">Probability and Computing</a> by Mitzenmacher and Upfal.</p>
<h2 id="exercise">Exercise</h2>
<p>Intuitively you could do a little better by distributing the rings in rounds. In each round you pick two elves and give a ring to the elf who currently has fewer. Can you still compute the maximum number of rings a single elf will get?</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>Recently discussed in relation to <a href="http://zufallstee.blogspot.com/2011/10/triangles-in-random-graphs.html">triangles in random graphs</a>.<a href="#fnref1">↩</a></p></li>
<li id="fn2"><p>I told you the Poisson distribution is useful <a href="http://zufallstee.blogspot.com/2011/10/poisson-distribution.html">in this post</a><a href="#fnref2">↩</a></p></li>
</ol>
</div>
<hr/>
<div style="display:inline-flex;flex-wrap:wrap;justify-content:space-between;font-size:80%">
<p style="margin-right:2ex">CC-BY-SA <a href="mailto:[email protected]">Adrian Neumann</a> (PGP Key <a href="https://adriann.github.io/ressources/pub.asc">A0A8BC98</a>)</p>
<p style="margin-left:1ex;margin-right:1ex"><a href="http://adriann.github.io">adriann.github.io</a></p>
<p style="margin-left:2ex"><a href="https://adriann.github.io/feed.rss">RSS</a></p>
</div>
</body>
</html>