Probability of a Network Collision between 2 computers
Consider a network with a bus topology where $2$ computers, $A$ and $B$, wish to transmit
messages at the same time. After a collision is detected each computer stops transmitting and waits for a random time selected from $left{1, 2, ldots, dright}$. Upon waiting for the randomly selected time each computer checks the bus to to see if is free, and if so it starts transmitting again. If a new collision is detected the above process is repeated, until one of the processors is able to successfully transmit. Assume that $d = 3$ and that the value of $d$ never changes.
Assume that only computers $A$ and $B$ wish to transmit. After detecting the first collision...
1) What is the probability that there will not be a second collision?
There are $9$ potential outcomes as $d=3$ and $3*3$ possibilities exist since we are comparing $2$ numbers in the range of $left{1, 2, 3 right}$. There is a $1/3$ chance of a collision, therefore the chance that there will not be a collision is $2/3$ . Is this correct?
2) What is the probability that exactly $k$ rounds of the above procedure are needed
before one of the computers can transmit?
Hint. During $k −1$ rounds there will be collisions and in the $k$ round the computers choose different random waiting times. Hence, the probability that $k$ rounds are needed is probability of a collision in first round × probability of collision in second round × · · ·
For this one I think it is $(2/3)^k$ because of the hint given.
What do you guys think? This is for a CS class, not statistics, so I am trying not to overthink it.
probability
asked Sep 30 '18 at 22:59
user2312844
306
add a comment |
Consider a network with a bus topology where $2$ computers, $A$ and $B$, wish to transmit
messages at the same time. After a collision is detected each computer stops transmitting and waits for a random time selected from $left{1, 2, ldots, dright}$. Upon waiting for the randomly selected time each computer checks the bus to to see if is free, and if so it starts transmitting again. If a new collision is detected the above process is repeated, until one of the processors is able to successfully transmit. Assume that $d = 3$ and that the value of $d$ never changes.
Assume that only computers $A$ and $B$ wish to transmit. After detecting the first collision...
1) What is the probability that there will not be a second collision?
There are $9$ potential outcomes as $d=3$ and $3*3$ possibilities exist since we are comparing $2$ numbers in the range of $left{1, 2, 3 right}$. There is a $1/3$ chance of a collision, therefore the chance that there will not be a collision is $2/3$ . Is this correct?
2) What is the probability that exactly $k$ rounds of the above procedure are needed
before one of the computers can transmit?
Hint. During $k −1$ rounds there will be collisions and in the $k$ round the computers choose different random waiting times. Hence, the probability that $k$ rounds are needed is probability of a collision in first round × probability of collision in second round × · · ·
For this one I think it is $(2/3)^k$ because of the hint given.
What do you guys think? This is for a CS class, not statistics, so I am trying not to overthink it.
probability
asked Sep 30 '18 at 22:59
user2312844
306
add a comment |
Consider a network with a bus topology where $2$ computers, $A$ and $B$, wish to transmit
messages at the same time. After a collision is detected each computer stops transmitting and waits for a random time selected from $left{1, 2, ldots, dright}$. Upon waiting for the randomly selected time each computer checks the bus to to see if is free, and if so it starts transmitting again. If a new collision is detected the above process is repeated, until one of the processors is able to successfully transmit. Assume that $d = 3$ and that the value of $d$ never changes.
Assume that only computers $A$ and $B$ wish to transmit. After detecting the first collision...
1) What is the probability that there will not be a second collision?
There are $9$ potential outcomes as $d=3$ and $3*3$ possibilities exist since we are comparing $2$ numbers in the range of $left{1, 2, 3 right}$. There is a $1/3$ chance of a collision, therefore the chance that there will not be a collision is $2/3$ . Is this correct?
2) What is the probability that exactly $k$ rounds of the above procedure are needed
before one of the computers can transmit?
Hint. During $k −1$ rounds there will be collisions and in the $k$ round the computers choose different random waiting times. Hence, the probability that $k$ rounds are needed is probability of a collision in first round × probability of collision in second round × · · ·
For this one I think it is $(2/3)^k$ because of the hint given.
What do you guys think? This is for a CS class, not statistics, so I am trying not to overthink it.
probability
asked Sep 30 '18 at 22:59
user2312844
306
Consider a network with a bus topology where $2$ computers, $A$ and $B$, wish to transmit
messages at the same time. After a collision is detected each computer stops transmitting and waits for a random time selected from $left{1, 2, ldots, dright}$. Upon waiting for the randomly selected time each computer checks the bus to to see if is free, and if so it starts transmitting again. If a new collision is detected the above process is repeated, until one of the processors is able to successfully transmit. Assume that $d = 3$ and that the value of $d$ never changes.
Assume that only computers $A$ and $B$ wish to transmit. After detecting the first collision...
1) What is the probability that there will not be a second collision?
There are $9$ potential outcomes as $d=3$ and $3*3$ possibilities exist since we are comparing $2$ numbers in the range of $left{1, 2, 3 right}$. There is a $1/3$ chance of a collision, therefore the chance that there will not be a collision is $2/3$ . Is this correct?
2) What is the probability that exactly $k$ rounds of the above procedure are needed
before one of the computers can transmit?
Hint. During $k −1$ rounds there will be collisions and in the $k$ round the computers choose different random waiting times. Hence, the probability that $k$ rounds are needed is probability of a collision in first round × probability of collision in second round × · · ·
For this one I think it is $(2/3)^k$ because of the hint given.
What do you guys think? This is for a CS class, not statistics, so I am trying not to overthink it.
probability
probability
asked Sep 30 '18 at 22:59
user2312844
306
asked Sep 30 '18 at 22:59
user2312844
306
edited Sep 30 '18 at 23:05
asked Sep 30 '18 at 22:59
user2312844
306
asked Sep 30 '18 at 22:59
user2312844
306
asked Sep 30 '18 at 22:59
user2312844
306
306
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
I understand the first part as there will be no second collision for the very next attempt. Then $frac23$ is correct.
For the second part, it is a Geometric Distribution. We need $k-1$ failures followed by $1$ success.
Hence
$$left( frac13right)^{k-1}left(frac23 right)=frac{2}{3^k}$$
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
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%2f2937302%2fprobability-of-a-network-collision-between-2-computers%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
I understand the first part as there will be no second collision for the very next attempt. Then $frac23$ is correct.
For the second part, it is a Geometric Distribution. We need $k-1$ failures followed by $1$ success.
Hence
$$left( frac13right)^{k-1}left(frac23 right)=frac{2}{3^k}$$
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
add a comment |
I understand the first part as there will be no second collision for the very next attempt. Then $frac23$ is correct.
For the second part, it is a Geometric Distribution. We need $k-1$ failures followed by $1$ success.
Hence
$$left( frac13right)^{k-1}left(frac23 right)=frac{2}{3^k}$$
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
add a comment |
I understand the first part as there will be no second collision for the very next attempt. Then $frac23$ is correct.
For the second part, it is a Geometric Distribution. We need $k-1$ failures followed by $1$ success.
Hence
$$left( frac13right)^{k-1}left(frac23 right)=frac{2}{3^k}$$
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
I understand the first part as there will be no second collision for the very next attempt. Then $frac23$ is correct.
For the second part, it is a Geometric Distribution. We need $k-1$ failures followed by $1$ success.
Hence
$$left( frac13right)^{k-1}left(frac23 right)=frac{2}{3^k}$$
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
answered Nov 29 '18 at 1:49
Siong Thye Goh
99.5k1464117
99.5k1464117
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f2937302%2fprobability-of-a-network-collision-between-2-computers%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
