Probability of getting a chain size of atleast 3
$begingroup$
Consider a hash table with 9 slots that use collision-resolution with chaining and the table is initially empty. What is the probability that after 4 insertions, at least a chain of size 3 is created?
My Analysis
I have broken this into 2 parts
Case1: Chain size 3 is created:
Here Any of the 3 keys out of 4 can go into the same slot and the left 1 key goes into remaining slots.
So here probability must be
$binom{4}{3}times frac{1}{9^3} times frac{8}{9}$
Case 2:Chain of size 4 is created: This can happen when all 4 insertions are made into the same slot and this can happen with probability $frac{1}{9^4}$
So, final answer must be
$ Bigl(binom{4}{3} times frac{8}{9^4}Bigr)+frac{1}{9^4}$
Am I correct in my reasoning and the answer?
The above question was in one of the practice tests I had gave to prepare for Competitive Exam.I was not convinced by their answer, so wanted to discuss my approach.
probability
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
$endgroup$
add a comment |
$begingroup$
Consider a hash table with 9 slots that use collision-resolution with chaining and the table is initially empty. What is the probability that after 4 insertions, at least a chain of size 3 is created?
My Analysis
I have broken this into 2 parts
Case1: Chain size 3 is created:
Here Any of the 3 keys out of 4 can go into the same slot and the left 1 key goes into remaining slots.
So here probability must be
$binom{4}{3}times frac{1}{9^3} times frac{8}{9}$
Case 2:Chain of size 4 is created: This can happen when all 4 insertions are made into the same slot and this can happen with probability $frac{1}{9^4}$
So, final answer must be
$ Bigl(binom{4}{3} times frac{8}{9^4}Bigr)+frac{1}{9^4}$
Am I correct in my reasoning and the answer?
The above question was in one of the practice tests I had gave to prepare for Competitive Exam.I was not convinced by their answer, so wanted to discuss my approach.
probability
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
$endgroup$
add a comment |
$begingroup$
Consider a hash table with 9 slots that use collision-resolution with chaining and the table is initially empty. What is the probability that after 4 insertions, at least a chain of size 3 is created?
My Analysis
I have broken this into 2 parts
Case1: Chain size 3 is created:
Here Any of the 3 keys out of 4 can go into the same slot and the left 1 key goes into remaining slots.
So here probability must be
$binom{4}{3}times frac{1}{9^3} times frac{8}{9}$
Case 2:Chain of size 4 is created: This can happen when all 4 insertions are made into the same slot and this can happen with probability $frac{1}{9^4}$
So, final answer must be
$ Bigl(binom{4}{3} times frac{8}{9^4}Bigr)+frac{1}{9^4}$
Am I correct in my reasoning and the answer?
The above question was in one of the practice tests I had gave to prepare for Competitive Exam.I was not convinced by their answer, so wanted to discuss my approach.
probability
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
$endgroup$
Consider a hash table with 9 slots that use collision-resolution with chaining and the table is initially empty. What is the probability that after 4 insertions, at least a chain of size 3 is created?
My Analysis
I have broken this into 2 parts
Case1: Chain size 3 is created:
Here Any of the 3 keys out of 4 can go into the same slot and the left 1 key goes into remaining slots.
So here probability must be
$binom{4}{3}times frac{1}{9^3} times frac{8}{9}$
Case 2:Chain of size 4 is created: This can happen when all 4 insertions are made into the same slot and this can happen with probability $frac{1}{9^4}$
So, final answer must be
$ Bigl(binom{4}{3} times frac{8}{9^4}Bigr)+frac{1}{9^4}$
Am I correct in my reasoning and the answer?
The above question was in one of the practice tests I had gave to prepare for Competitive Exam.I was not convinced by their answer, so wanted to discuss my approach.
probability
probability
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
asked Dec 19 '18 at 2:04
user3767495user3767495
4028
4028
add a comment |
add a comment |
0
active
oldest
votes
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%2f3045908%2fprobability-of-getting-a-chain-size-of-atleast-3%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%2f3045908%2fprobability-of-getting-a-chain-size-of-atleast-3%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
