Balls and Bins - high probability bounds on the sum of squared loads
$begingroup$
Consider throwing $m$ balls into $n$ bins uniformly at random, and let $X_i$ denote the number of balls that fall in bin $i$.
Denote by $S=sum_{i=1}^n X_i^2$ the sum of square loads on the bins.
I am looking for a high-probability upper bound on $S$, i.e., a quantity $B_{m,n}$ such that
$$ Prleft[S ge B_{m,n}right]le 1/n.$$
This question is motivated by an algorithm that uses fingerprints instead of ids for the balls and wishes to guarantee that with high probability there is no fingerprint collision between balls in the same bin (but there can be across bins). Since the probability of collision in bin $i$ is proportional to $X_i^2$, setting a fingerprint length proportional to $log S$ will guarantee the correctness with high probability.
How can we derive a high probability upper bound for $S$?
One naive approach would be to use known high probability bounds on the maximum load. For example, if $m=n$ we have that the maximum load is bounded by $(2+o(1))cdot log n / loglog n$ with high probability. This implies that we can set $B_{m,n} = (4+o(1))cdot ncdotleft(log n / loglog nright)^2$.
However, this seems like a very loose bound. How can we improve it (hopefully, for arbitrary $m$)?
probability probability-theory random-variables balls-in-bins
asked Dec 31 '18 at 19:12
R BR B
1,3111331
$endgroup$
|
show 2 more comments
$begingroup$
Consider throwing $m$ balls into $n$ bins uniformly at random, and let $X_i$ denote the number of balls that fall in bin $i$.
Denote by $S=sum_{i=1}^n X_i^2$ the sum of square loads on the bins.
I am looking for a high-probability upper bound on $S$, i.e., a quantity $B_{m,n}$ such that
$$ Prleft[S ge B_{m,n}right]le 1/n.$$
This question is motivated by an algorithm that uses fingerprints instead of ids for the balls and wishes to guarantee that with high probability there is no fingerprint collision between balls in the same bin (but there can be across bins). Since the probability of collision in bin $i$ is proportional to $X_i^2$, setting a fingerprint length proportional to $log S$ will guarantee the correctness with high probability.
How can we derive a high probability upper bound for $S$?
One naive approach would be to use known high probability bounds on the maximum load. For example, if $m=n$ we have that the maximum load is bounded by $(2+o(1))cdot log n / loglog n$ with high probability. This implies that we can set $B_{m,n} = (4+o(1))cdot ncdotleft(log n / loglog nright)^2$.
However, this seems like a very loose bound. How can we improve it (hopefully, for arbitrary $m$)?
probability probability-theory random-variables balls-in-bins
asked Dec 31 '18 at 19:12
R BR B
1,3111331
$endgroup$
$begingroup$
What is high probability?
$endgroup$
– greedoid
Dec 31 '18 at 20:40
$begingroup$
@greedoid, $1-1/n$ would be good.
$endgroup$
– R B
Dec 31 '18 at 21:01
$begingroup$
No, what is the definition of high probability?
$endgroup$
– greedoid
Dec 31 '18 at 21:03
$begingroup$
@greedoid - Probability that approaches $1$ when $nto infty$, see en.wikipedia.org/wiki/With_high_probability.
$endgroup$
– R B
Dec 31 '18 at 21:05
$begingroup$
@greedoid - thanks for your comments. I edited the post, can you please see if now it is clear? Thanks!
$endgroup$
– R B
Dec 31 '18 at 21:11
|
show 2 more comments
$begingroup$
Consider throwing $m$ balls into $n$ bins uniformly at random, and let $X_i$ denote the number of balls that fall in bin $i$.
Denote by $S=sum_{i=1}^n X_i^2$ the sum of square loads on the bins.
I am looking for a high-probability upper bound on $S$, i.e., a quantity $B_{m,n}$ such that
$$ Prleft[S ge B_{m,n}right]le 1/n.$$
This question is motivated by an algorithm that uses fingerprints instead of ids for the balls and wishes to guarantee that with high probability there is no fingerprint collision between balls in the same bin (but there can be across bins). Since the probability of collision in bin $i$ is proportional to $X_i^2$, setting a fingerprint length proportional to $log S$ will guarantee the correctness with high probability.
How can we derive a high probability upper bound for $S$?
One naive approach would be to use known high probability bounds on the maximum load. For example, if $m=n$ we have that the maximum load is bounded by $(2+o(1))cdot log n / loglog n$ with high probability. This implies that we can set $B_{m,n} = (4+o(1))cdot ncdotleft(log n / loglog nright)^2$.
However, this seems like a very loose bound. How can we improve it (hopefully, for arbitrary $m$)?
probability probability-theory random-variables balls-in-bins
asked Dec 31 '18 at 19:12
R BR B
1,3111331
$endgroup$
Consider throwing $m$ balls into $n$ bins uniformly at random, and let $X_i$ denote the number of balls that fall in bin $i$.
Denote by $S=sum_{i=1}^n X_i^2$ the sum of square loads on the bins.
I am looking for a high-probability upper bound on $S$, i.e., a quantity $B_{m,n}$ such that
$$ Prleft[S ge B_{m,n}right]le 1/n.$$
This question is motivated by an algorithm that uses fingerprints instead of ids for the balls and wishes to guarantee that with high probability there is no fingerprint collision between balls in the same bin (but there can be across bins). Since the probability of collision in bin $i$ is proportional to $X_i^2$, setting a fingerprint length proportional to $log S$ will guarantee the correctness with high probability.
How can we derive a high probability upper bound for $S$?
One naive approach would be to use known high probability bounds on the maximum load. For example, if $m=n$ we have that the maximum load is bounded by $(2+o(1))cdot log n / loglog n$ with high probability. This implies that we can set $B_{m,n} = (4+o(1))cdot ncdotleft(log n / loglog nright)^2$.
However, this seems like a very loose bound. How can we improve it (hopefully, for arbitrary $m$)?
probability probability-theory random-variables balls-in-bins
probability probability-theory random-variables balls-in-bins
asked Dec 31 '18 at 19:12
R BR B
1,3111331
asked Dec 31 '18 at 19:12
R BR B
1,3111331
edited Dec 31 '18 at 21:36
R B
asked Dec 31 '18 at 19:12
R BR B
1,3111331
asked Dec 31 '18 at 19:12
R BR B
1,3111331
asked Dec 31 '18 at 19:12
R BR B
1,3111331
1,3111331
$begingroup$
What is high probability?
$endgroup$
– greedoid
Dec 31 '18 at 20:40
$begingroup$
@greedoid, $1-1/n$ would be good.
$endgroup$
– R B
Dec 31 '18 at 21:01
$begingroup$
No, what is the definition of high probability?
$endgroup$
– greedoid
Dec 31 '18 at 21:03
$begingroup$
@greedoid - Probability that approaches $1$ when $nto infty$, see en.wikipedia.org/wiki/With_high_probability.
$endgroup$
– R B
Dec 31 '18 at 21:05
$begingroup$
@greedoid - thanks for your comments. I edited the post, can you please see if now it is clear? Thanks!
$endgroup$
– R B
Dec 31 '18 at 21:11
|
show 2 more comments
$begingroup$
What is high probability?
$endgroup$
– greedoid
Dec 31 '18 at 20:40
$begingroup$
@greedoid, $1-1/n$ would be good.
$endgroup$
– R B
Dec 31 '18 at 21:01
$begingroup$
No, what is the definition of high probability?
$endgroup$
– greedoid
Dec 31 '18 at 21:03
$begingroup$
@greedoid - Probability that approaches $1$ when $nto infty$, see en.wikipedia.org/wiki/With_high_probability.
$endgroup$
– R B
Dec 31 '18 at 21:05
$begingroup$
@greedoid - thanks for your comments. I edited the post, can you please see if now it is clear? Thanks!
$endgroup$
– R B
Dec 31 '18 at 21:11
$begingroup$
What is high probability?
$endgroup$
– greedoid
Dec 31 '18 at 20:40
$begingroup$
What is high probability?
$endgroup$
– greedoid
Dec 31 '18 at 20:40
$begingroup$
@greedoid, $1-1/n$ would be good.
$endgroup$
– R B
Dec 31 '18 at 21:01
$begingroup$
@greedoid, $1-1/n$ would be good.
$endgroup$
– R B
Dec 31 '18 at 21:01
$begingroup$
No, what is the definition of high probability?
$endgroup$
– greedoid
Dec 31 '18 at 21:03
$begingroup$
No, what is the definition of high probability?
$endgroup$
– greedoid
Dec 31 '18 at 21:03
$begingroup$
@greedoid - Probability that approaches $1$ when $nto infty$, see en.wikipedia.org/wiki/With_high_probability.
$endgroup$
– R B
Dec 31 '18 at 21:05
$begingroup$
@greedoid - Probability that approaches $1$ when $nto infty$, see en.wikipedia.org/wiki/With_high_probability.
$endgroup$
– R B
Dec 31 '18 at 21:05
$begingroup$
@greedoid - thanks for your comments. I edited the post, can you please see if now it is clear? Thanks!
$endgroup$
– R B
Dec 31 '18 at 21:11
$begingroup$
@greedoid - thanks for your comments. I edited the post, can you please see if now it is clear? Thanks!
$endgroup$
– R B
Dec 31 '18 at 21:11
|
show 2 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057969%2fballs-and-bins-high-probability-bounds-on-the-sum-of-squared-loads%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057969%2fballs-and-bins-high-probability-bounds-on-the-sum-of-squared-loads%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What is high probability?
$endgroup$
– greedoid
Dec 31 '18 at 20:40
$begingroup$
@greedoid, $1-1/n$ would be good.
$endgroup$
– R B
Dec 31 '18 at 21:01
$begingroup$
No, what is the definition of high probability?
$endgroup$
– greedoid
Dec 31 '18 at 21:03
$begingroup$
@greedoid - Probability that approaches $1$ when $nto infty$, see en.wikipedia.org/wiki/With_high_probability.
$endgroup$
– R B
Dec 31 '18 at 21:05
$begingroup$
@greedoid - thanks for your comments. I edited the post, can you please see if now it is clear? Thanks!
$endgroup$
– R B
Dec 31 '18 at 21:11