Expected maximum number of collisions for universal hash function
$begingroup$
If we hash a set $S$ of $n$ keys into a table of size $n$ with a universal hash function $h$, what is the expected maximum number of keys that collide?
We break down this computation into a sequence of easier steps, as follows.
Let $A_j$ be the event that at least one slot in the hash table has ≥ j keys. We compute
the largest $j$ for which $Prob[A_j] ≤ 1/2$; that $j$ is our answer. Calculating $A_j$ directly
is not straightforward, so we proceed as follows.
(a) Let $A^1_j$ be the event that the table slot 1 gets ≥ $j$ keys under $h$. Supposing you
know $Prob[A^1_j]$, give an upper bound on $Prob[A_j]$.
(b) Let $B$ be the event that a fixed subset $C ⊂ S$ of size $|C| = j$ hashes into slot 1.
That is, each key of $C$ maps to slot 1 under $h$. Calculate the probability $Prob[B]$.
(c) Use $Prob[B]$ to get an upper bound on the probability $Prob[A^1_j]$.
(d) Compute the largest value of j for which $Prob[A^1_j] ≤ frac{1}{2n}$. Explain how in combination with (a), this $j$ is the expected maximum number of collisions.
I am not sure how to solve this problem using the steps shown. I have managed to find some resources to solve the slot-size bound for hash chaining but I am unable to follow the given steps logically.
probability hash-function
asked Jan 25 at 1:36
kncknc
1
$endgroup$
add a comment |
$begingroup$
If we hash a set $S$ of $n$ keys into a table of size $n$ with a universal hash function $h$, what is the expected maximum number of keys that collide?
We break down this computation into a sequence of easier steps, as follows.
Let $A_j$ be the event that at least one slot in the hash table has ≥ j keys. We compute
the largest $j$ for which $Prob[A_j] ≤ 1/2$; that $j$ is our answer. Calculating $A_j$ directly
is not straightforward, so we proceed as follows.
(a) Let $A^1_j$ be the event that the table slot 1 gets ≥ $j$ keys under $h$. Supposing you
know $Prob[A^1_j]$, give an upper bound on $Prob[A_j]$.
(b) Let $B$ be the event that a fixed subset $C ⊂ S$ of size $|C| = j$ hashes into slot 1.
That is, each key of $C$ maps to slot 1 under $h$. Calculate the probability $Prob[B]$.
(c) Use $Prob[B]$ to get an upper bound on the probability $Prob[A^1_j]$.
(d) Compute the largest value of j for which $Prob[A^1_j] ≤ frac{1}{2n}$. Explain how in combination with (a), this $j$ is the expected maximum number of collisions.
I am not sure how to solve this problem using the steps shown. I have managed to find some resources to solve the slot-size bound for hash chaining but I am unable to follow the given steps logically.
probability hash-function
asked Jan 25 at 1:36
kncknc
1
$endgroup$
$begingroup$
It should be that you are computing the largest $j$ such that $Prob [A_j] ge frac 12$ because the probability is a decreasing function of $j$
$endgroup$
– Ross Millikan
Jan 25 at 1:42
add a comment |
$begingroup$
If we hash a set $S$ of $n$ keys into a table of size $n$ with a universal hash function $h$, what is the expected maximum number of keys that collide?
We break down this computation into a sequence of easier steps, as follows.
Let $A_j$ be the event that at least one slot in the hash table has ≥ j keys. We compute
the largest $j$ for which $Prob[A_j] ≤ 1/2$; that $j$ is our answer. Calculating $A_j$ directly
is not straightforward, so we proceed as follows.
(a) Let $A^1_j$ be the event that the table slot 1 gets ≥ $j$ keys under $h$. Supposing you
know $Prob[A^1_j]$, give an upper bound on $Prob[A_j]$.
(b) Let $B$ be the event that a fixed subset $C ⊂ S$ of size $|C| = j$ hashes into slot 1.
That is, each key of $C$ maps to slot 1 under $h$. Calculate the probability $Prob[B]$.
(c) Use $Prob[B]$ to get an upper bound on the probability $Prob[A^1_j]$.
(d) Compute the largest value of j for which $Prob[A^1_j] ≤ frac{1}{2n}$. Explain how in combination with (a), this $j$ is the expected maximum number of collisions.
I am not sure how to solve this problem using the steps shown. I have managed to find some resources to solve the slot-size bound for hash chaining but I am unable to follow the given steps logically.
probability hash-function
asked Jan 25 at 1:36
kncknc
1
$endgroup$
If we hash a set $S$ of $n$ keys into a table of size $n$ with a universal hash function $h$, what is the expected maximum number of keys that collide?
We break down this computation into a sequence of easier steps, as follows.
Let $A_j$ be the event that at least one slot in the hash table has ≥ j keys. We compute
the largest $j$ for which $Prob[A_j] ≤ 1/2$; that $j$ is our answer. Calculating $A_j$ directly
is not straightforward, so we proceed as follows.
(a) Let $A^1_j$ be the event that the table slot 1 gets ≥ $j$ keys under $h$. Supposing you
know $Prob[A^1_j]$, give an upper bound on $Prob[A_j]$.
(b) Let $B$ be the event that a fixed subset $C ⊂ S$ of size $|C| = j$ hashes into slot 1.
That is, each key of $C$ maps to slot 1 under $h$. Calculate the probability $Prob[B]$.
(c) Use $Prob[B]$ to get an upper bound on the probability $Prob[A^1_j]$.
(d) Compute the largest value of j for which $Prob[A^1_j] ≤ frac{1}{2n}$. Explain how in combination with (a), this $j$ is the expected maximum number of collisions.
I am not sure how to solve this problem using the steps shown. I have managed to find some resources to solve the slot-size bound for hash chaining but I am unable to follow the given steps logically.
probability hash-function
probability hash-function
asked Jan 25 at 1:36
kncknc
1
asked Jan 25 at 1:36
kncknc
1
asked Jan 25 at 1:36
kncknc
1
asked Jan 25 at 1:36
kncknc
1
asked Jan 25 at 1:36
kncknc
1
1
$begingroup$
It should be that you are computing the largest $j$ such that $Prob [A_j] ge frac 12$ because the probability is a decreasing function of $j$
$endgroup$
– Ross Millikan
Jan 25 at 1:42
add a comment |
$begingroup$
It should be that you are computing the largest $j$ such that $Prob [A_j] ge frac 12$ because the probability is a decreasing function of $j$
$endgroup$
– Ross Millikan
Jan 25 at 1:42
$begingroup$
It should be that you are computing the largest $j$ such that $Prob [A_j] ge frac 12$ because the probability is a decreasing function of $j$
$endgroup$
– Ross Millikan
Jan 25 at 1:42
$begingroup$
It should be that you are computing the largest $j$ such that $Prob [A_j] ge frac 12$ because the probability is a decreasing function of $j$
$endgroup$
– Ross Millikan
Jan 25 at 1:42
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For $a$ the point is that $Prob[A_j] le nProb[A_j^1]$ because each slot has the same chance to have at least $j$ entries. It will actually be less than this because the right side counts cases where two slots each have $j$ entries twice while the left side counts them once. We were asked for an upper bound, so this is not a problem.
For $b$ the idea is to assume that each key maps to a slot randomly, so the chance a given key maps to slot $1$ is $frac 1n$
For $c$ you just use $b$ and multiply by the number of subsets of size $j$
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
$endgroup$
add a comment |
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%2f3086595%2fexpected-maximum-number-of-collisions-for-universal-hash-function%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For $a$ the point is that $Prob[A_j] le nProb[A_j^1]$ because each slot has the same chance to have at least $j$ entries. It will actually be less than this because the right side counts cases where two slots each have $j$ entries twice while the left side counts them once. We were asked for an upper bound, so this is not a problem.
For $b$ the idea is to assume that each key maps to a slot randomly, so the chance a given key maps to slot $1$ is $frac 1n$
For $c$ you just use $b$ and multiply by the number of subsets of size $j$
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
$endgroup$
add a comment |
$begingroup$
For $a$ the point is that $Prob[A_j] le nProb[A_j^1]$ because each slot has the same chance to have at least $j$ entries. It will actually be less than this because the right side counts cases where two slots each have $j$ entries twice while the left side counts them once. We were asked for an upper bound, so this is not a problem.
For $b$ the idea is to assume that each key maps to a slot randomly, so the chance a given key maps to slot $1$ is $frac 1n$
For $c$ you just use $b$ and multiply by the number of subsets of size $j$
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
$endgroup$
add a comment |
$begingroup$
For $a$ the point is that $Prob[A_j] le nProb[A_j^1]$ because each slot has the same chance to have at least $j$ entries. It will actually be less than this because the right side counts cases where two slots each have $j$ entries twice while the left side counts them once. We were asked for an upper bound, so this is not a problem.
For $b$ the idea is to assume that each key maps to a slot randomly, so the chance a given key maps to slot $1$ is $frac 1n$
For $c$ you just use $b$ and multiply by the number of subsets of size $j$
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
$endgroup$
For $a$ the point is that $Prob[A_j] le nProb[A_j^1]$ because each slot has the same chance to have at least $j$ entries. It will actually be less than this because the right side counts cases where two slots each have $j$ entries twice while the left side counts them once. We were asked for an upper bound, so this is not a problem.
For $b$ the idea is to assume that each key maps to a slot randomly, so the chance a given key maps to slot $1$ is $frac 1n$
For $c$ you just use $b$ and multiply by the number of subsets of size $j$
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
answered Jan 25 at 1:47
Ross MillikanRoss Millikan
299k24200374
299k24200374
add a comment |
add a comment |
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%2f3086595%2fexpected-maximum-number-of-collisions-for-universal-hash-function%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$
It should be that you are computing the largest $j$ such that $Prob [A_j] ge frac 12$ because the probability is a decreasing function of $j$
$endgroup$
– Ross Millikan
Jan 25 at 1:42