Probability of 3 streams of data on same Compute Node
Assume there are 10 compute nodes and 6 sources of data which randomly assign a destination within 1:10 compute nodes. What is the probability that three sources (or more) go to the same compute node at the same time?
I tried using the 'birthday' paradox Poisson concept and came up with the following:
For [n=1] you have (10/10) or 100% probability that a single stream will be sent to a compute node
For [n=2] you have (10/10)*(1/10) or 10% probability that a two streams will be sent to the same compute node
For [n=3] you have (10/10)(1/10)(2/10) or 2% probability that three streams will be sent to the same compute node
Is this logic correct with a 2% probability?
probability probability-distributions
add a comment |
Assume there are 10 compute nodes and 6 sources of data which randomly assign a destination within 1:10 compute nodes. What is the probability that three sources (or more) go to the same compute node at the same time?
I tried using the 'birthday' paradox Poisson concept and came up with the following:
For [n=1] you have (10/10) or 100% probability that a single stream will be sent to a compute node
For [n=2] you have (10/10)*(1/10) or 10% probability that a two streams will be sent to the same compute node
For [n=3] you have (10/10)(1/10)(2/10) or 2% probability that three streams will be sent to the same compute node
Is this logic correct with a 2% probability?
probability probability-distributions
No, the reasoning is not correct even for the $n=3$ case because the factor $2$ is unjustified. It also falls short of reaching the six specified data sources. You do have the beginning of a correct approach. I remember answering a similar problem that was harder. I'll find a link for you.
– hardmath
Nov 29 at 19:43
Thanks, appreciate the assistance. Anything you can do to point me in the right direction.
– Robert
Nov 29 at 20:38
So how about we use something like the following: (6!) / (3!*(6-3)!) = 20 outcomes with a chance of 3 collisions For 6 sources and 10 destinations there are 10^6 outcomes, or 1,000,000 The probability would then be 20/1,000,000?
– Robert
Nov 29 at 22:56
I've added to my Answer a note which develops the solution along the line you suggest, using combinations to pick out the successful outcomes among $10^6$ possibilities.
– hardmath
Nov 30 at 17:41
add a comment |
Assume there are 10 compute nodes and 6 sources of data which randomly assign a destination within 1:10 compute nodes. What is the probability that three sources (or more) go to the same compute node at the same time?
I tried using the 'birthday' paradox Poisson concept and came up with the following:
For [n=1] you have (10/10) or 100% probability that a single stream will be sent to a compute node
For [n=2] you have (10/10)*(1/10) or 10% probability that a two streams will be sent to the same compute node
For [n=3] you have (10/10)(1/10)(2/10) or 2% probability that three streams will be sent to the same compute node
Is this logic correct with a 2% probability?
probability probability-distributions
Assume there are 10 compute nodes and 6 sources of data which randomly assign a destination within 1:10 compute nodes. What is the probability that three sources (or more) go to the same compute node at the same time?
I tried using the 'birthday' paradox Poisson concept and came up with the following:
For [n=1] you have (10/10) or 100% probability that a single stream will be sent to a compute node
For [n=2] you have (10/10)*(1/10) or 10% probability that a two streams will be sent to the same compute node
For [n=3] you have (10/10)(1/10)(2/10) or 2% probability that three streams will be sent to the same compute node
Is this logic correct with a 2% probability?
probability probability-distributions
probability probability-distributions
asked Nov 29 at 19:17
Robert
82
82
No, the reasoning is not correct even for the $n=3$ case because the factor $2$ is unjustified. It also falls short of reaching the six specified data sources. You do have the beginning of a correct approach. I remember answering a similar problem that was harder. I'll find a link for you.
– hardmath
Nov 29 at 19:43
Thanks, appreciate the assistance. Anything you can do to point me in the right direction.
– Robert
Nov 29 at 20:38
So how about we use something like the following: (6!) / (3!*(6-3)!) = 20 outcomes with a chance of 3 collisions For 6 sources and 10 destinations there are 10^6 outcomes, or 1,000,000 The probability would then be 20/1,000,000?
– Robert
Nov 29 at 22:56
I've added to my Answer a note which develops the solution along the line you suggest, using combinations to pick out the successful outcomes among $10^6$ possibilities.
– hardmath
Nov 30 at 17:41
add a comment |
No, the reasoning is not correct even for the $n=3$ case because the factor $2$ is unjustified. It also falls short of reaching the six specified data sources. You do have the beginning of a correct approach. I remember answering a similar problem that was harder. I'll find a link for you.
– hardmath
Nov 29 at 19:43
Thanks, appreciate the assistance. Anything you can do to point me in the right direction.
– Robert
Nov 29 at 20:38
So how about we use something like the following: (6!) / (3!*(6-3)!) = 20 outcomes with a chance of 3 collisions For 6 sources and 10 destinations there are 10^6 outcomes, or 1,000,000 The probability would then be 20/1,000,000?
– Robert
Nov 29 at 22:56
I've added to my Answer a note which develops the solution along the line you suggest, using combinations to pick out the successful outcomes among $10^6$ possibilities.
– hardmath
Nov 30 at 17:41
No, the reasoning is not correct even for the $n=3$ case because the factor $2$ is unjustified. It also falls short of reaching the six specified data sources. You do have the beginning of a correct approach. I remember answering a similar problem that was harder. I'll find a link for you.
– hardmath
Nov 29 at 19:43
No, the reasoning is not correct even for the $n=3$ case because the factor $2$ is unjustified. It also falls short of reaching the six specified data sources. You do have the beginning of a correct approach. I remember answering a similar problem that was harder. I'll find a link for you.
– hardmath
Nov 29 at 19:43
Thanks, appreciate the assistance. Anything you can do to point me in the right direction.
– Robert
Nov 29 at 20:38
Thanks, appreciate the assistance. Anything you can do to point me in the right direction.
– Robert
Nov 29 at 20:38
So how about we use something like the following: (6!) / (3!*(6-3)!) = 20 outcomes with a chance of 3 collisions For 6 sources and 10 destinations there are 10^6 outcomes, or 1,000,000 The probability would then be 20/1,000,000?
– Robert
Nov 29 at 22:56
So how about we use something like the following: (6!) / (3!*(6-3)!) = 20 outcomes with a chance of 3 collisions For 6 sources and 10 destinations there are 10^6 outcomes, or 1,000,000 The probability would then be 20/1,000,000?
– Robert
Nov 29 at 22:56
I've added to my Answer a note which develops the solution along the line you suggest, using combinations to pick out the successful outcomes among $10^6$ possibilities.
– hardmath
Nov 30 at 17:41
I've added to my Answer a note which develops the solution along the line you suggest, using combinations to pick out the successful outcomes among $10^6$ possibilities.
– hardmath
Nov 30 at 17:41
add a comment |
2 Answers
2
active
oldest
votes
It's possible to approach this problem in more than one way, but I think the following will be useful for more complicated problems despite its somewhat tedious recitation of steps. At the end I've added an alternative solution that closely resembles the approach suggested in a Comment by the OP above.
The problem is equivalent to asking the chance that some (compute) node will get assigned at least three (data) sources. Alternatively, we could work with the probability of the complementary outcome, that no node gets more than two sources (where random uniform and independent assignments are understood). For the sake of clarity we will consider the former outcomes "success" and the latter outcomes "failure".
As you intuitively started, we can consider the six source assignments to nodes as if they were decided serially. In particular the first assignment will give us "with probability one" that some node has one source (and the rest of them have as yet none):
$$ 1+0+0+0+0+0+0+0+0+0 = 1 tag{1}$$
where we sort the nodes by descending numbers of sources assigned.
Thinking of this as a state with probability one after the first assignment, we have only five more assignments to make. The second assignment could give us two different outcomes. If we hit the same node again, it will look like:
$$ 2+0+0+0+0+0+0+0+0+0 = 2 tag{2a}$$
which happens $0.1$ of the time, but if we hit a different node, it will look like:
$$ 1+1+0+0+0+0+0+0+0+0 = 2 tag{2b}$$
and that would occur $0.9$ of the time.
The third assignment would give any of the following results:
$$ 3+0+0+0+0+0+0+0+0+0 = 3 tag{3a}$$
$$ 2+1+0+0+0+0+0+0+0+0 = 3 tag{3b}$$
$$ 1+1+1+0+0+0+0+0+0+0 = 3 tag{3c}$$
We can figure out the probabilities of these states by considering how likely the states $2a,2b$ are to result in each of them. The chance of going from $2a$ to $3a$ is $0.1$, and this is the only way to arrive at $3a$. Since the probability of state $2a$ was $0.1$, the probability of arriving at $3a$ is $0.01$. Moreover any further assignments cannot decrease the "at least three" number of sources at a node, so we can go ahead and lump all the "descendents" of $3a$ into the bucket of "successful" assignments:
$$ mathbf{Pr}(3a) = 0.01 $$
On the other hand state $2a$ could transition to state $3b$ with probability $0.9$, while state $2b$ transitions to state $3b$ with probability $0.2$. Therefore the combined possibility to reach state $3b$ is:
$$ mathbf{Pr}(3b) = 0.27 $$
Then it should be obvious that the probability of reaching state $3c$ is:
$$ mathbf{Pr}(3c) = 0.72 $$
either by direct computation (of transition from $2b$ to $3c$) or taking the complementary event to the union of $3a$ and $3b$.
Since we've taken state $3a$ off the table, let's consider only the states that would arise from $3b,3c$. These are:
$$ 3+1+0+0+0+0+0+0+0+0 = 4 tag{4a}$$
$$ 2+2+0+0+0+0+0+0+0+0 = 4 tag{4b}$$
$$ 2+1+1+0+0+0+0+0+0+0 = 4 tag{4c}$$
$$ 1+1+1+1+0+0+0+0+0+0 = 4 tag{4d}$$
From state $3b$ we can reach state $4a$ with probability $0.1$ or state $4b$ with probability $0.1$ or state $4c$ with probability $0.8$. From state $3c$ we can reach state $4c$ with probability $0.3$ or state $4d$ with probability $0.7$. So (having excluded descending from $3a$), we have these probabilities of reaching the node/source assignments above:
$$ mathbf{Pr}(4a) = 0.027 $$
$$ mathbf{Pr}(4b) = 0.027 $$
$$ mathbf{Pr}(4c) = 0.432 $$
$$ mathbf{Pr}(4d) = 0.504 $$
Because we excluded state $3a$ from further consideration (which had probability $0.01$), the above descendent probabilities add up only to $0.99$. Likewise we will exclude descendents of $4a$ because it already has at least three sources for one node. But keeping track of our successful outcomes, we already have probability $0.01 + 0.027 = 0.037$ after assigning four sources.
The states that can be reached from $4b,4c,4d$ are these:
$$ 3+2+0+0+0+0+0+0+0+0 = 5 tag{5a}$$
$$ 3+1+1+0+0+0+0+0+0+0 = 5 tag{5b}$$
$$ 2+2+1+0+0+0+0+0+0+0 = 5 tag{5c}$$
$$ 2+1+1+1+0+0+0+0+0+0 = 5 tag{5d}$$
$$ 1+1+1+1+1+0+0+0+0+0 = 5 tag{5e}$$
We summarize the transition probabilities from $4b,4c,4d$ to $5a,5b,5c,5d,5e$ in this table:
$$ begin{array}{r|ccccc}
text{fromto} & 5a & 5b & 5c & 5d & 5e \
hline
4b & 0.2 & & 0.8 & & \
4c & & 0.1 & 0.2 & 0.7 & \
4d & & & & 0.4 & 0.6 end{array} $$
After multiplying the probabilities of states $4b,4c,4d$ by the above matrix, we get the probabilities of states $5a,5b,5c,5d,5e$:
$$ mathbf{Pr}(5a) = 0.0054 $$
$$ mathbf{Pr}(5b) = 0.0432 $$
$$ mathbf{Pr}(5c) = 0.1080 $$
$$ mathbf{Pr}(5d) = 0.5040 $$
$$ mathbf{Pr}(5e) = 0.3024 $$
These add up to $0.963$ as expected, and we will remove state $5a,5b$ from further calculations because they've already reached at least three sources assigned to a node. For those keeping track of our probability of success, it is $0.037 + 0.0486 = 0.0856$ after five sources are assigned.
Finally we can obtain the following from states $5c,5d,5e$:
$$ 3+2+1+0+0+0+0+0+0+0 = 6 tag{6a}$$
$$ 3+1+1+1+0+0+0+0+0+0 = 6 tag{6b}$$
$$ 2+2+2+0+0+0+0+0+0+0 = 6 tag{6c}$$
$$ 2+2+1+1+0+0+0+0+0+0 = 6 tag{6d}$$
$$ 2+1+1+1+1+0+0+0+0+0 = 6 tag{6e}$$
$$ 1+1+1+1+1+1+0+0+0+0 = 6 tag{6f}$$
As we've reached the final stage of assignments here, all we really need to compute are the probabilities to reach the states $6a,6b$ since those two are the only ones that achieve success (at least three sources on a node).
Checking the possible transitions, only state $5c$ can give us state $6a$ with probability $0.2$, and only state $5d$ can give use state $6b$ with probability $0.1$. From state $5e$ (all ones and zeros) there isn't a way to reach success.
$$ mathbf{Pr}(6a) = 0.0216 $$
$$ mathbf{Pr}(6b) = 0.0504 $$
Combining these with our previous running total, the overall chance that at least one of the ten nodes will have at least three of the six sources is $0.0856 + 0.072 = 0.1576$.
Alternative Solution
The probability state transition approach above can be adapted to many more complicated problems. See e.g. this previous Question. But the present problem, with $10$ distinguishable nodes and $6$ distinguishable sources, can be solved with a combinatorial approach like what the OP outlined in a Comment.
As there we consider all $10^6$ possible assignments of sources to nodes equally likely, so that it suffices to count the failure cases (those in which no nodes is assigned more than two sources).
In the end these failures are the cases we labeled as states $6c,6d,6e,6f$. The simplest to count is $6f$, where we have six nodes each with one source assigned to them. Keep in mind the sources are distinct, so there are $10$ ways to assign the first source, then $9$ ways to assign the second source, and so on:
$$ textbf{count}(6f) = 10cdot 9cdot 8cdot 7cdot 6cdot 5 = 151200 $$
For state $6e$ we choose one node to get two sources assigned, and then four of the remaining nodes to get one source apiece. Thus:
$$ textbf{count}(6e) = 10cdot binom{6}{2} cdot 9cdot 8cdot 7cdot 6 = 453600 $$
State $6d$ has two nodes with two sources and two nodes with one source. Thus:
$$ textbf{count}(6d) = binom{10}{2}cdot binom{6}{2}cdot binom{4}{2}cdot 8cdot 7 = 226800 $$
Finally state $6c$ requires a choice of three nodes, each getting a pair of sources. The count is:
$$ textbf{count}(6c) = binom{10}{3}cdot binom{6}{2}cdot binom{4}{2} = 10800 $$
The total count of failure cases is:
$$ 10800 + 226800 + 453600 + 151200 = 842400 $$
Subtracting these from $10^6$ gives us $157600$ success cases, so the probability of success is $0.1576$ (in agreement with the earlier calculation).
This is a brilliant answer and really appreciate you working through all the detail in making it so easy to follow.
– Robert
Dec 1 at 3:05
As an alternative I was looking at Bernoulli Trials and got close to the answer; but perhaps I was doing something wrong. For this example I set n (trials) = 6, k (number of successes) = calculated for when k is 3:6, p (p success) = .1 and q (p failure) = 1-p. Since there are 10 nodes I multiplied the answer (0.01585) by 10 to get a P(Success) = 0.1585. Thoughts on this approach and what might be slightly off?
– Robert
Dec 1 at 3:08
add a comment |
The following solution uses an exponential generating function (EGF).
It may be simpler to solve the complementary problem. What is the probability that all nodes have no more than 2 of the 6 sources assigned to them? The sources may be assigned to the nodes in $10^6$ possible ways, all of which we assume are equally likely. We would like to count the number of ways in which each node has 0, 1, or 2 sources assigned. More generally, we might count the number of ways that $r$ sources can be assigned. The EGF for the number of ways sources can be assigned to a single node is $1+x+(1/2!)x^2$, so the EGF for a sequence of $10$ such assignments is
$$f(x) = left( 1 + x + frac{1}{2!} x^2 right)^{10}$$
The EGF gives the number of ways any number of sources can be assigned to the nodes, but all we really need is the number of ways 6 sources can be assigned. Expanding $f(x)$, we find the coefficient of $x^6$ is $1,170$, so the number of ways 6 sources can be assigned to the nodes subject to the given constraints is $6! times 1170 = 842,400$, and the associated probability is $$frac{842,400}{10^6} = 0.8424$$
(I used a computer algebra system for the expansion, but I think that with a little work one could compute the coefficient with pencil and paper.)
So the answer to the original problem, the probability that at least one node has three or more sources assigned to it, is
$$1 - 0.8424 = boxed{0.1576}$$
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%2f3019062%2fprobability-of-3-streams-of-data-on-same-compute-node%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
It's possible to approach this problem in more than one way, but I think the following will be useful for more complicated problems despite its somewhat tedious recitation of steps. At the end I've added an alternative solution that closely resembles the approach suggested in a Comment by the OP above.
The problem is equivalent to asking the chance that some (compute) node will get assigned at least three (data) sources. Alternatively, we could work with the probability of the complementary outcome, that no node gets more than two sources (where random uniform and independent assignments are understood). For the sake of clarity we will consider the former outcomes "success" and the latter outcomes "failure".
As you intuitively started, we can consider the six source assignments to nodes as if they were decided serially. In particular the first assignment will give us "with probability one" that some node has one source (and the rest of them have as yet none):
$$ 1+0+0+0+0+0+0+0+0+0 = 1 tag{1}$$
where we sort the nodes by descending numbers of sources assigned.
Thinking of this as a state with probability one after the first assignment, we have only five more assignments to make. The second assignment could give us two different outcomes. If we hit the same node again, it will look like:
$$ 2+0+0+0+0+0+0+0+0+0 = 2 tag{2a}$$
which happens $0.1$ of the time, but if we hit a different node, it will look like:
$$ 1+1+0+0+0+0+0+0+0+0 = 2 tag{2b}$$
and that would occur $0.9$ of the time.
The third assignment would give any of the following results:
$$ 3+0+0+0+0+0+0+0+0+0 = 3 tag{3a}$$
$$ 2+1+0+0+0+0+0+0+0+0 = 3 tag{3b}$$
$$ 1+1+1+0+0+0+0+0+0+0 = 3 tag{3c}$$
We can figure out the probabilities of these states by considering how likely the states $2a,2b$ are to result in each of them. The chance of going from $2a$ to $3a$ is $0.1$, and this is the only way to arrive at $3a$. Since the probability of state $2a$ was $0.1$, the probability of arriving at $3a$ is $0.01$. Moreover any further assignments cannot decrease the "at least three" number of sources at a node, so we can go ahead and lump all the "descendents" of $3a$ into the bucket of "successful" assignments:
$$ mathbf{Pr}(3a) = 0.01 $$
On the other hand state $2a$ could transition to state $3b$ with probability $0.9$, while state $2b$ transitions to state $3b$ with probability $0.2$. Therefore the combined possibility to reach state $3b$ is:
$$ mathbf{Pr}(3b) = 0.27 $$
Then it should be obvious that the probability of reaching state $3c$ is:
$$ mathbf{Pr}(3c) = 0.72 $$
either by direct computation (of transition from $2b$ to $3c$) or taking the complementary event to the union of $3a$ and $3b$.
Since we've taken state $3a$ off the table, let's consider only the states that would arise from $3b,3c$. These are:
$$ 3+1+0+0+0+0+0+0+0+0 = 4 tag{4a}$$
$$ 2+2+0+0+0+0+0+0+0+0 = 4 tag{4b}$$
$$ 2+1+1+0+0+0+0+0+0+0 = 4 tag{4c}$$
$$ 1+1+1+1+0+0+0+0+0+0 = 4 tag{4d}$$
From state $3b$ we can reach state $4a$ with probability $0.1$ or state $4b$ with probability $0.1$ or state $4c$ with probability $0.8$. From state $3c$ we can reach state $4c$ with probability $0.3$ or state $4d$ with probability $0.7$. So (having excluded descending from $3a$), we have these probabilities of reaching the node/source assignments above:
$$ mathbf{Pr}(4a) = 0.027 $$
$$ mathbf{Pr}(4b) = 0.027 $$
$$ mathbf{Pr}(4c) = 0.432 $$
$$ mathbf{Pr}(4d) = 0.504 $$
Because we excluded state $3a$ from further consideration (which had probability $0.01$), the above descendent probabilities add up only to $0.99$. Likewise we will exclude descendents of $4a$ because it already has at least three sources for one node. But keeping track of our successful outcomes, we already have probability $0.01 + 0.027 = 0.037$ after assigning four sources.
The states that can be reached from $4b,4c,4d$ are these:
$$ 3+2+0+0+0+0+0+0+0+0 = 5 tag{5a}$$
$$ 3+1+1+0+0+0+0+0+0+0 = 5 tag{5b}$$
$$ 2+2+1+0+0+0+0+0+0+0 = 5 tag{5c}$$
$$ 2+1+1+1+0+0+0+0+0+0 = 5 tag{5d}$$
$$ 1+1+1+1+1+0+0+0+0+0 = 5 tag{5e}$$
We summarize the transition probabilities from $4b,4c,4d$ to $5a,5b,5c,5d,5e$ in this table:
$$ begin{array}{r|ccccc}
text{fromto} & 5a & 5b & 5c & 5d & 5e \
hline
4b & 0.2 & & 0.8 & & \
4c & & 0.1 & 0.2 & 0.7 & \
4d & & & & 0.4 & 0.6 end{array} $$
After multiplying the probabilities of states $4b,4c,4d$ by the above matrix, we get the probabilities of states $5a,5b,5c,5d,5e$:
$$ mathbf{Pr}(5a) = 0.0054 $$
$$ mathbf{Pr}(5b) = 0.0432 $$
$$ mathbf{Pr}(5c) = 0.1080 $$
$$ mathbf{Pr}(5d) = 0.5040 $$
$$ mathbf{Pr}(5e) = 0.3024 $$
These add up to $0.963$ as expected, and we will remove state $5a,5b$ from further calculations because they've already reached at least three sources assigned to a node. For those keeping track of our probability of success, it is $0.037 + 0.0486 = 0.0856$ after five sources are assigned.
Finally we can obtain the following from states $5c,5d,5e$:
$$ 3+2+1+0+0+0+0+0+0+0 = 6 tag{6a}$$
$$ 3+1+1+1+0+0+0+0+0+0 = 6 tag{6b}$$
$$ 2+2+2+0+0+0+0+0+0+0 = 6 tag{6c}$$
$$ 2+2+1+1+0+0+0+0+0+0 = 6 tag{6d}$$
$$ 2+1+1+1+1+0+0+0+0+0 = 6 tag{6e}$$
$$ 1+1+1+1+1+1+0+0+0+0 = 6 tag{6f}$$
As we've reached the final stage of assignments here, all we really need to compute are the probabilities to reach the states $6a,6b$ since those two are the only ones that achieve success (at least three sources on a node).
Checking the possible transitions, only state $5c$ can give us state $6a$ with probability $0.2$, and only state $5d$ can give use state $6b$ with probability $0.1$. From state $5e$ (all ones and zeros) there isn't a way to reach success.
$$ mathbf{Pr}(6a) = 0.0216 $$
$$ mathbf{Pr}(6b) = 0.0504 $$
Combining these with our previous running total, the overall chance that at least one of the ten nodes will have at least three of the six sources is $0.0856 + 0.072 = 0.1576$.
Alternative Solution
The probability state transition approach above can be adapted to many more complicated problems. See e.g. this previous Question. But the present problem, with $10$ distinguishable nodes and $6$ distinguishable sources, can be solved with a combinatorial approach like what the OP outlined in a Comment.
As there we consider all $10^6$ possible assignments of sources to nodes equally likely, so that it suffices to count the failure cases (those in which no nodes is assigned more than two sources).
In the end these failures are the cases we labeled as states $6c,6d,6e,6f$. The simplest to count is $6f$, where we have six nodes each with one source assigned to them. Keep in mind the sources are distinct, so there are $10$ ways to assign the first source, then $9$ ways to assign the second source, and so on:
$$ textbf{count}(6f) = 10cdot 9cdot 8cdot 7cdot 6cdot 5 = 151200 $$
For state $6e$ we choose one node to get two sources assigned, and then four of the remaining nodes to get one source apiece. Thus:
$$ textbf{count}(6e) = 10cdot binom{6}{2} cdot 9cdot 8cdot 7cdot 6 = 453600 $$
State $6d$ has two nodes with two sources and two nodes with one source. Thus:
$$ textbf{count}(6d) = binom{10}{2}cdot binom{6}{2}cdot binom{4}{2}cdot 8cdot 7 = 226800 $$
Finally state $6c$ requires a choice of three nodes, each getting a pair of sources. The count is:
$$ textbf{count}(6c) = binom{10}{3}cdot binom{6}{2}cdot binom{4}{2} = 10800 $$
The total count of failure cases is:
$$ 10800 + 226800 + 453600 + 151200 = 842400 $$
Subtracting these from $10^6$ gives us $157600$ success cases, so the probability of success is $0.1576$ (in agreement with the earlier calculation).
This is a brilliant answer and really appreciate you working through all the detail in making it so easy to follow.
– Robert
Dec 1 at 3:05
As an alternative I was looking at Bernoulli Trials and got close to the answer; but perhaps I was doing something wrong. For this example I set n (trials) = 6, k (number of successes) = calculated for when k is 3:6, p (p success) = .1 and q (p failure) = 1-p. Since there are 10 nodes I multiplied the answer (0.01585) by 10 to get a P(Success) = 0.1585. Thoughts on this approach and what might be slightly off?
– Robert
Dec 1 at 3:08
add a comment |
It's possible to approach this problem in more than one way, but I think the following will be useful for more complicated problems despite its somewhat tedious recitation of steps. At the end I've added an alternative solution that closely resembles the approach suggested in a Comment by the OP above.
The problem is equivalent to asking the chance that some (compute) node will get assigned at least three (data) sources. Alternatively, we could work with the probability of the complementary outcome, that no node gets more than two sources (where random uniform and independent assignments are understood). For the sake of clarity we will consider the former outcomes "success" and the latter outcomes "failure".
As you intuitively started, we can consider the six source assignments to nodes as if they were decided serially. In particular the first assignment will give us "with probability one" that some node has one source (and the rest of them have as yet none):
$$ 1+0+0+0+0+0+0+0+0+0 = 1 tag{1}$$
where we sort the nodes by descending numbers of sources assigned.
Thinking of this as a state with probability one after the first assignment, we have only five more assignments to make. The second assignment could give us two different outcomes. If we hit the same node again, it will look like:
$$ 2+0+0+0+0+0+0+0+0+0 = 2 tag{2a}$$
which happens $0.1$ of the time, but if we hit a different node, it will look like:
$$ 1+1+0+0+0+0+0+0+0+0 = 2 tag{2b}$$
and that would occur $0.9$ of the time.
The third assignment would give any of the following results:
$$ 3+0+0+0+0+0+0+0+0+0 = 3 tag{3a}$$
$$ 2+1+0+0+0+0+0+0+0+0 = 3 tag{3b}$$
$$ 1+1+1+0+0+0+0+0+0+0 = 3 tag{3c}$$
We can figure out the probabilities of these states by considering how likely the states $2a,2b$ are to result in each of them. The chance of going from $2a$ to $3a$ is $0.1$, and this is the only way to arrive at $3a$. Since the probability of state $2a$ was $0.1$, the probability of arriving at $3a$ is $0.01$. Moreover any further assignments cannot decrease the "at least three" number of sources at a node, so we can go ahead and lump all the "descendents" of $3a$ into the bucket of "successful" assignments:
$$ mathbf{Pr}(3a) = 0.01 $$
On the other hand state $2a$ could transition to state $3b$ with probability $0.9$, while state $2b$ transitions to state $3b$ with probability $0.2$. Therefore the combined possibility to reach state $3b$ is:
$$ mathbf{Pr}(3b) = 0.27 $$
Then it should be obvious that the probability of reaching state $3c$ is:
$$ mathbf{Pr}(3c) = 0.72 $$
either by direct computation (of transition from $2b$ to $3c$) or taking the complementary event to the union of $3a$ and $3b$.
Since we've taken state $3a$ off the table, let's consider only the states that would arise from $3b,3c$. These are:
$$ 3+1+0+0+0+0+0+0+0+0 = 4 tag{4a}$$
$$ 2+2+0+0+0+0+0+0+0+0 = 4 tag{4b}$$
$$ 2+1+1+0+0+0+0+0+0+0 = 4 tag{4c}$$
$$ 1+1+1+1+0+0+0+0+0+0 = 4 tag{4d}$$
From state $3b$ we can reach state $4a$ with probability $0.1$ or state $4b$ with probability $0.1$ or state $4c$ with probability $0.8$. From state $3c$ we can reach state $4c$ with probability $0.3$ or state $4d$ with probability $0.7$. So (having excluded descending from $3a$), we have these probabilities of reaching the node/source assignments above:
$$ mathbf{Pr}(4a) = 0.027 $$
$$ mathbf{Pr}(4b) = 0.027 $$
$$ mathbf{Pr}(4c) = 0.432 $$
$$ mathbf{Pr}(4d) = 0.504 $$
Because we excluded state $3a$ from further consideration (which had probability $0.01$), the above descendent probabilities add up only to $0.99$. Likewise we will exclude descendents of $4a$ because it already has at least three sources for one node. But keeping track of our successful outcomes, we already have probability $0.01 + 0.027 = 0.037$ after assigning four sources.
The states that can be reached from $4b,4c,4d$ are these:
$$ 3+2+0+0+0+0+0+0+0+0 = 5 tag{5a}$$
$$ 3+1+1+0+0+0+0+0+0+0 = 5 tag{5b}$$
$$ 2+2+1+0+0+0+0+0+0+0 = 5 tag{5c}$$
$$ 2+1+1+1+0+0+0+0+0+0 = 5 tag{5d}$$
$$ 1+1+1+1+1+0+0+0+0+0 = 5 tag{5e}$$
We summarize the transition probabilities from $4b,4c,4d$ to $5a,5b,5c,5d,5e$ in this table:
$$ begin{array}{r|ccccc}
text{fromto} & 5a & 5b & 5c & 5d & 5e \
hline
4b & 0.2 & & 0.8 & & \
4c & & 0.1 & 0.2 & 0.7 & \
4d & & & & 0.4 & 0.6 end{array} $$
After multiplying the probabilities of states $4b,4c,4d$ by the above matrix, we get the probabilities of states $5a,5b,5c,5d,5e$:
$$ mathbf{Pr}(5a) = 0.0054 $$
$$ mathbf{Pr}(5b) = 0.0432 $$
$$ mathbf{Pr}(5c) = 0.1080 $$
$$ mathbf{Pr}(5d) = 0.5040 $$
$$ mathbf{Pr}(5e) = 0.3024 $$
These add up to $0.963$ as expected, and we will remove state $5a,5b$ from further calculations because they've already reached at least three sources assigned to a node. For those keeping track of our probability of success, it is $0.037 + 0.0486 = 0.0856$ after five sources are assigned.
Finally we can obtain the following from states $5c,5d,5e$:
$$ 3+2+1+0+0+0+0+0+0+0 = 6 tag{6a}$$
$$ 3+1+1+1+0+0+0+0+0+0 = 6 tag{6b}$$
$$ 2+2+2+0+0+0+0+0+0+0 = 6 tag{6c}$$
$$ 2+2+1+1+0+0+0+0+0+0 = 6 tag{6d}$$
$$ 2+1+1+1+1+0+0+0+0+0 = 6 tag{6e}$$
$$ 1+1+1+1+1+1+0+0+0+0 = 6 tag{6f}$$
As we've reached the final stage of assignments here, all we really need to compute are the probabilities to reach the states $6a,6b$ since those two are the only ones that achieve success (at least three sources on a node).
Checking the possible transitions, only state $5c$ can give us state $6a$ with probability $0.2$, and only state $5d$ can give use state $6b$ with probability $0.1$. From state $5e$ (all ones and zeros) there isn't a way to reach success.
$$ mathbf{Pr}(6a) = 0.0216 $$
$$ mathbf{Pr}(6b) = 0.0504 $$
Combining these with our previous running total, the overall chance that at least one of the ten nodes will have at least three of the six sources is $0.0856 + 0.072 = 0.1576$.
Alternative Solution
The probability state transition approach above can be adapted to many more complicated problems. See e.g. this previous Question. But the present problem, with $10$ distinguishable nodes and $6$ distinguishable sources, can be solved with a combinatorial approach like what the OP outlined in a Comment.
As there we consider all $10^6$ possible assignments of sources to nodes equally likely, so that it suffices to count the failure cases (those in which no nodes is assigned more than two sources).
In the end these failures are the cases we labeled as states $6c,6d,6e,6f$. The simplest to count is $6f$, where we have six nodes each with one source assigned to them. Keep in mind the sources are distinct, so there are $10$ ways to assign the first source, then $9$ ways to assign the second source, and so on:
$$ textbf{count}(6f) = 10cdot 9cdot 8cdot 7cdot 6cdot 5 = 151200 $$
For state $6e$ we choose one node to get two sources assigned, and then four of the remaining nodes to get one source apiece. Thus:
$$ textbf{count}(6e) = 10cdot binom{6}{2} cdot 9cdot 8cdot 7cdot 6 = 453600 $$
State $6d$ has two nodes with two sources and two nodes with one source. Thus:
$$ textbf{count}(6d) = binom{10}{2}cdot binom{6}{2}cdot binom{4}{2}cdot 8cdot 7 = 226800 $$
Finally state $6c$ requires a choice of three nodes, each getting a pair of sources. The count is:
$$ textbf{count}(6c) = binom{10}{3}cdot binom{6}{2}cdot binom{4}{2} = 10800 $$
The total count of failure cases is:
$$ 10800 + 226800 + 453600 + 151200 = 842400 $$
Subtracting these from $10^6$ gives us $157600$ success cases, so the probability of success is $0.1576$ (in agreement with the earlier calculation).
This is a brilliant answer and really appreciate you working through all the detail in making it so easy to follow.
– Robert
Dec 1 at 3:05
As an alternative I was looking at Bernoulli Trials and got close to the answer; but perhaps I was doing something wrong. For this example I set n (trials) = 6, k (number of successes) = calculated for when k is 3:6, p (p success) = .1 and q (p failure) = 1-p. Since there are 10 nodes I multiplied the answer (0.01585) by 10 to get a P(Success) = 0.1585. Thoughts on this approach and what might be slightly off?
– Robert
Dec 1 at 3:08
add a comment |
It's possible to approach this problem in more than one way, but I think the following will be useful for more complicated problems despite its somewhat tedious recitation of steps. At the end I've added an alternative solution that closely resembles the approach suggested in a Comment by the OP above.
The problem is equivalent to asking the chance that some (compute) node will get assigned at least three (data) sources. Alternatively, we could work with the probability of the complementary outcome, that no node gets more than two sources (where random uniform and independent assignments are understood). For the sake of clarity we will consider the former outcomes "success" and the latter outcomes "failure".
As you intuitively started, we can consider the six source assignments to nodes as if they were decided serially. In particular the first assignment will give us "with probability one" that some node has one source (and the rest of them have as yet none):
$$ 1+0+0+0+0+0+0+0+0+0 = 1 tag{1}$$
where we sort the nodes by descending numbers of sources assigned.
Thinking of this as a state with probability one after the first assignment, we have only five more assignments to make. The second assignment could give us two different outcomes. If we hit the same node again, it will look like:
$$ 2+0+0+0+0+0+0+0+0+0 = 2 tag{2a}$$
which happens $0.1$ of the time, but if we hit a different node, it will look like:
$$ 1+1+0+0+0+0+0+0+0+0 = 2 tag{2b}$$
and that would occur $0.9$ of the time.
The third assignment would give any of the following results:
$$ 3+0+0+0+0+0+0+0+0+0 = 3 tag{3a}$$
$$ 2+1+0+0+0+0+0+0+0+0 = 3 tag{3b}$$
$$ 1+1+1+0+0+0+0+0+0+0 = 3 tag{3c}$$
We can figure out the probabilities of these states by considering how likely the states $2a,2b$ are to result in each of them. The chance of going from $2a$ to $3a$ is $0.1$, and this is the only way to arrive at $3a$. Since the probability of state $2a$ was $0.1$, the probability of arriving at $3a$ is $0.01$. Moreover any further assignments cannot decrease the "at least three" number of sources at a node, so we can go ahead and lump all the "descendents" of $3a$ into the bucket of "successful" assignments:
$$ mathbf{Pr}(3a) = 0.01 $$
On the other hand state $2a$ could transition to state $3b$ with probability $0.9$, while state $2b$ transitions to state $3b$ with probability $0.2$. Therefore the combined possibility to reach state $3b$ is:
$$ mathbf{Pr}(3b) = 0.27 $$
Then it should be obvious that the probability of reaching state $3c$ is:
$$ mathbf{Pr}(3c) = 0.72 $$
either by direct computation (of transition from $2b$ to $3c$) or taking the complementary event to the union of $3a$ and $3b$.
Since we've taken state $3a$ off the table, let's consider only the states that would arise from $3b,3c$. These are:
$$ 3+1+0+0+0+0+0+0+0+0 = 4 tag{4a}$$
$$ 2+2+0+0+0+0+0+0+0+0 = 4 tag{4b}$$
$$ 2+1+1+0+0+0+0+0+0+0 = 4 tag{4c}$$
$$ 1+1+1+1+0+0+0+0+0+0 = 4 tag{4d}$$
From state $3b$ we can reach state $4a$ with probability $0.1$ or state $4b$ with probability $0.1$ or state $4c$ with probability $0.8$. From state $3c$ we can reach state $4c$ with probability $0.3$ or state $4d$ with probability $0.7$. So (having excluded descending from $3a$), we have these probabilities of reaching the node/source assignments above:
$$ mathbf{Pr}(4a) = 0.027 $$
$$ mathbf{Pr}(4b) = 0.027 $$
$$ mathbf{Pr}(4c) = 0.432 $$
$$ mathbf{Pr}(4d) = 0.504 $$
Because we excluded state $3a$ from further consideration (which had probability $0.01$), the above descendent probabilities add up only to $0.99$. Likewise we will exclude descendents of $4a$ because it already has at least three sources for one node. But keeping track of our successful outcomes, we already have probability $0.01 + 0.027 = 0.037$ after assigning four sources.
The states that can be reached from $4b,4c,4d$ are these:
$$ 3+2+0+0+0+0+0+0+0+0 = 5 tag{5a}$$
$$ 3+1+1+0+0+0+0+0+0+0 = 5 tag{5b}$$
$$ 2+2+1+0+0+0+0+0+0+0 = 5 tag{5c}$$
$$ 2+1+1+1+0+0+0+0+0+0 = 5 tag{5d}$$
$$ 1+1+1+1+1+0+0+0+0+0 = 5 tag{5e}$$
We summarize the transition probabilities from $4b,4c,4d$ to $5a,5b,5c,5d,5e$ in this table:
$$ begin{array}{r|ccccc}
text{fromto} & 5a & 5b & 5c & 5d & 5e \
hline
4b & 0.2 & & 0.8 & & \
4c & & 0.1 & 0.2 & 0.7 & \
4d & & & & 0.4 & 0.6 end{array} $$
After multiplying the probabilities of states $4b,4c,4d$ by the above matrix, we get the probabilities of states $5a,5b,5c,5d,5e$:
$$ mathbf{Pr}(5a) = 0.0054 $$
$$ mathbf{Pr}(5b) = 0.0432 $$
$$ mathbf{Pr}(5c) = 0.1080 $$
$$ mathbf{Pr}(5d) = 0.5040 $$
$$ mathbf{Pr}(5e) = 0.3024 $$
These add up to $0.963$ as expected, and we will remove state $5a,5b$ from further calculations because they've already reached at least three sources assigned to a node. For those keeping track of our probability of success, it is $0.037 + 0.0486 = 0.0856$ after five sources are assigned.
Finally we can obtain the following from states $5c,5d,5e$:
$$ 3+2+1+0+0+0+0+0+0+0 = 6 tag{6a}$$
$$ 3+1+1+1+0+0+0+0+0+0 = 6 tag{6b}$$
$$ 2+2+2+0+0+0+0+0+0+0 = 6 tag{6c}$$
$$ 2+2+1+1+0+0+0+0+0+0 = 6 tag{6d}$$
$$ 2+1+1+1+1+0+0+0+0+0 = 6 tag{6e}$$
$$ 1+1+1+1+1+1+0+0+0+0 = 6 tag{6f}$$
As we've reached the final stage of assignments here, all we really need to compute are the probabilities to reach the states $6a,6b$ since those two are the only ones that achieve success (at least three sources on a node).
Checking the possible transitions, only state $5c$ can give us state $6a$ with probability $0.2$, and only state $5d$ can give use state $6b$ with probability $0.1$. From state $5e$ (all ones and zeros) there isn't a way to reach success.
$$ mathbf{Pr}(6a) = 0.0216 $$
$$ mathbf{Pr}(6b) = 0.0504 $$
Combining these with our previous running total, the overall chance that at least one of the ten nodes will have at least three of the six sources is $0.0856 + 0.072 = 0.1576$.
Alternative Solution
The probability state transition approach above can be adapted to many more complicated problems. See e.g. this previous Question. But the present problem, with $10$ distinguishable nodes and $6$ distinguishable sources, can be solved with a combinatorial approach like what the OP outlined in a Comment.
As there we consider all $10^6$ possible assignments of sources to nodes equally likely, so that it suffices to count the failure cases (those in which no nodes is assigned more than two sources).
In the end these failures are the cases we labeled as states $6c,6d,6e,6f$. The simplest to count is $6f$, where we have six nodes each with one source assigned to them. Keep in mind the sources are distinct, so there are $10$ ways to assign the first source, then $9$ ways to assign the second source, and so on:
$$ textbf{count}(6f) = 10cdot 9cdot 8cdot 7cdot 6cdot 5 = 151200 $$
For state $6e$ we choose one node to get two sources assigned, and then four of the remaining nodes to get one source apiece. Thus:
$$ textbf{count}(6e) = 10cdot binom{6}{2} cdot 9cdot 8cdot 7cdot 6 = 453600 $$
State $6d$ has two nodes with two sources and two nodes with one source. Thus:
$$ textbf{count}(6d) = binom{10}{2}cdot binom{6}{2}cdot binom{4}{2}cdot 8cdot 7 = 226800 $$
Finally state $6c$ requires a choice of three nodes, each getting a pair of sources. The count is:
$$ textbf{count}(6c) = binom{10}{3}cdot binom{6}{2}cdot binom{4}{2} = 10800 $$
The total count of failure cases is:
$$ 10800 + 226800 + 453600 + 151200 = 842400 $$
Subtracting these from $10^6$ gives us $157600$ success cases, so the probability of success is $0.1576$ (in agreement with the earlier calculation).
It's possible to approach this problem in more than one way, but I think the following will be useful for more complicated problems despite its somewhat tedious recitation of steps. At the end I've added an alternative solution that closely resembles the approach suggested in a Comment by the OP above.
The problem is equivalent to asking the chance that some (compute) node will get assigned at least three (data) sources. Alternatively, we could work with the probability of the complementary outcome, that no node gets more than two sources (where random uniform and independent assignments are understood). For the sake of clarity we will consider the former outcomes "success" and the latter outcomes "failure".
As you intuitively started, we can consider the six source assignments to nodes as if they were decided serially. In particular the first assignment will give us "with probability one" that some node has one source (and the rest of them have as yet none):
$$ 1+0+0+0+0+0+0+0+0+0 = 1 tag{1}$$
where we sort the nodes by descending numbers of sources assigned.
Thinking of this as a state with probability one after the first assignment, we have only five more assignments to make. The second assignment could give us two different outcomes. If we hit the same node again, it will look like:
$$ 2+0+0+0+0+0+0+0+0+0 = 2 tag{2a}$$
which happens $0.1$ of the time, but if we hit a different node, it will look like:
$$ 1+1+0+0+0+0+0+0+0+0 = 2 tag{2b}$$
and that would occur $0.9$ of the time.
The third assignment would give any of the following results:
$$ 3+0+0+0+0+0+0+0+0+0 = 3 tag{3a}$$
$$ 2+1+0+0+0+0+0+0+0+0 = 3 tag{3b}$$
$$ 1+1+1+0+0+0+0+0+0+0 = 3 tag{3c}$$
We can figure out the probabilities of these states by considering how likely the states $2a,2b$ are to result in each of them. The chance of going from $2a$ to $3a$ is $0.1$, and this is the only way to arrive at $3a$. Since the probability of state $2a$ was $0.1$, the probability of arriving at $3a$ is $0.01$. Moreover any further assignments cannot decrease the "at least three" number of sources at a node, so we can go ahead and lump all the "descendents" of $3a$ into the bucket of "successful" assignments:
$$ mathbf{Pr}(3a) = 0.01 $$
On the other hand state $2a$ could transition to state $3b$ with probability $0.9$, while state $2b$ transitions to state $3b$ with probability $0.2$. Therefore the combined possibility to reach state $3b$ is:
$$ mathbf{Pr}(3b) = 0.27 $$
Then it should be obvious that the probability of reaching state $3c$ is:
$$ mathbf{Pr}(3c) = 0.72 $$
either by direct computation (of transition from $2b$ to $3c$) or taking the complementary event to the union of $3a$ and $3b$.
Since we've taken state $3a$ off the table, let's consider only the states that would arise from $3b,3c$. These are:
$$ 3+1+0+0+0+0+0+0+0+0 = 4 tag{4a}$$
$$ 2+2+0+0+0+0+0+0+0+0 = 4 tag{4b}$$
$$ 2+1+1+0+0+0+0+0+0+0 = 4 tag{4c}$$
$$ 1+1+1+1+0+0+0+0+0+0 = 4 tag{4d}$$
From state $3b$ we can reach state $4a$ with probability $0.1$ or state $4b$ with probability $0.1$ or state $4c$ with probability $0.8$. From state $3c$ we can reach state $4c$ with probability $0.3$ or state $4d$ with probability $0.7$. So (having excluded descending from $3a$), we have these probabilities of reaching the node/source assignments above:
$$ mathbf{Pr}(4a) = 0.027 $$
$$ mathbf{Pr}(4b) = 0.027 $$
$$ mathbf{Pr}(4c) = 0.432 $$
$$ mathbf{Pr}(4d) = 0.504 $$
Because we excluded state $3a$ from further consideration (which had probability $0.01$), the above descendent probabilities add up only to $0.99$. Likewise we will exclude descendents of $4a$ because it already has at least three sources for one node. But keeping track of our successful outcomes, we already have probability $0.01 + 0.027 = 0.037$ after assigning four sources.
The states that can be reached from $4b,4c,4d$ are these:
$$ 3+2+0+0+0+0+0+0+0+0 = 5 tag{5a}$$
$$ 3+1+1+0+0+0+0+0+0+0 = 5 tag{5b}$$
$$ 2+2+1+0+0+0+0+0+0+0 = 5 tag{5c}$$
$$ 2+1+1+1+0+0+0+0+0+0 = 5 tag{5d}$$
$$ 1+1+1+1+1+0+0+0+0+0 = 5 tag{5e}$$
We summarize the transition probabilities from $4b,4c,4d$ to $5a,5b,5c,5d,5e$ in this table:
$$ begin{array}{r|ccccc}
text{fromto} & 5a & 5b & 5c & 5d & 5e \
hline
4b & 0.2 & & 0.8 & & \
4c & & 0.1 & 0.2 & 0.7 & \
4d & & & & 0.4 & 0.6 end{array} $$
After multiplying the probabilities of states $4b,4c,4d$ by the above matrix, we get the probabilities of states $5a,5b,5c,5d,5e$:
$$ mathbf{Pr}(5a) = 0.0054 $$
$$ mathbf{Pr}(5b) = 0.0432 $$
$$ mathbf{Pr}(5c) = 0.1080 $$
$$ mathbf{Pr}(5d) = 0.5040 $$
$$ mathbf{Pr}(5e) = 0.3024 $$
These add up to $0.963$ as expected, and we will remove state $5a,5b$ from further calculations because they've already reached at least three sources assigned to a node. For those keeping track of our probability of success, it is $0.037 + 0.0486 = 0.0856$ after five sources are assigned.
Finally we can obtain the following from states $5c,5d,5e$:
$$ 3+2+1+0+0+0+0+0+0+0 = 6 tag{6a}$$
$$ 3+1+1+1+0+0+0+0+0+0 = 6 tag{6b}$$
$$ 2+2+2+0+0+0+0+0+0+0 = 6 tag{6c}$$
$$ 2+2+1+1+0+0+0+0+0+0 = 6 tag{6d}$$
$$ 2+1+1+1+1+0+0+0+0+0 = 6 tag{6e}$$
$$ 1+1+1+1+1+1+0+0+0+0 = 6 tag{6f}$$
As we've reached the final stage of assignments here, all we really need to compute are the probabilities to reach the states $6a,6b$ since those two are the only ones that achieve success (at least three sources on a node).
Checking the possible transitions, only state $5c$ can give us state $6a$ with probability $0.2$, and only state $5d$ can give use state $6b$ with probability $0.1$. From state $5e$ (all ones and zeros) there isn't a way to reach success.
$$ mathbf{Pr}(6a) = 0.0216 $$
$$ mathbf{Pr}(6b) = 0.0504 $$
Combining these with our previous running total, the overall chance that at least one of the ten nodes will have at least three of the six sources is $0.0856 + 0.072 = 0.1576$.
Alternative Solution
The probability state transition approach above can be adapted to many more complicated problems. See e.g. this previous Question. But the present problem, with $10$ distinguishable nodes and $6$ distinguishable sources, can be solved with a combinatorial approach like what the OP outlined in a Comment.
As there we consider all $10^6$ possible assignments of sources to nodes equally likely, so that it suffices to count the failure cases (those in which no nodes is assigned more than two sources).
In the end these failures are the cases we labeled as states $6c,6d,6e,6f$. The simplest to count is $6f$, where we have six nodes each with one source assigned to them. Keep in mind the sources are distinct, so there are $10$ ways to assign the first source, then $9$ ways to assign the second source, and so on:
$$ textbf{count}(6f) = 10cdot 9cdot 8cdot 7cdot 6cdot 5 = 151200 $$
For state $6e$ we choose one node to get two sources assigned, and then four of the remaining nodes to get one source apiece. Thus:
$$ textbf{count}(6e) = 10cdot binom{6}{2} cdot 9cdot 8cdot 7cdot 6 = 453600 $$
State $6d$ has two nodes with two sources and two nodes with one source. Thus:
$$ textbf{count}(6d) = binom{10}{2}cdot binom{6}{2}cdot binom{4}{2}cdot 8cdot 7 = 226800 $$
Finally state $6c$ requires a choice of three nodes, each getting a pair of sources. The count is:
$$ textbf{count}(6c) = binom{10}{3}cdot binom{6}{2}cdot binom{4}{2} = 10800 $$
The total count of failure cases is:
$$ 10800 + 226800 + 453600 + 151200 = 842400 $$
Subtracting these from $10^6$ gives us $157600$ success cases, so the probability of success is $0.1576$ (in agreement with the earlier calculation).
edited Dec 1 at 5:37
answered Nov 30 at 2:14
hardmath
28.6k94994
28.6k94994
This is a brilliant answer and really appreciate you working through all the detail in making it so easy to follow.
– Robert
Dec 1 at 3:05
As an alternative I was looking at Bernoulli Trials and got close to the answer; but perhaps I was doing something wrong. For this example I set n (trials) = 6, k (number of successes) = calculated for when k is 3:6, p (p success) = .1 and q (p failure) = 1-p. Since there are 10 nodes I multiplied the answer (0.01585) by 10 to get a P(Success) = 0.1585. Thoughts on this approach and what might be slightly off?
– Robert
Dec 1 at 3:08
add a comment |
This is a brilliant answer and really appreciate you working through all the detail in making it so easy to follow.
– Robert
Dec 1 at 3:05
As an alternative I was looking at Bernoulli Trials and got close to the answer; but perhaps I was doing something wrong. For this example I set n (trials) = 6, k (number of successes) = calculated for when k is 3:6, p (p success) = .1 and q (p failure) = 1-p. Since there are 10 nodes I multiplied the answer (0.01585) by 10 to get a P(Success) = 0.1585. Thoughts on this approach and what might be slightly off?
– Robert
Dec 1 at 3:08
This is a brilliant answer and really appreciate you working through all the detail in making it so easy to follow.
– Robert
Dec 1 at 3:05
This is a brilliant answer and really appreciate you working through all the detail in making it so easy to follow.
– Robert
Dec 1 at 3:05
As an alternative I was looking at Bernoulli Trials and got close to the answer; but perhaps I was doing something wrong. For this example I set n (trials) = 6, k (number of successes) = calculated for when k is 3:6, p (p success) = .1 and q (p failure) = 1-p. Since there are 10 nodes I multiplied the answer (0.01585) by 10 to get a P(Success) = 0.1585. Thoughts on this approach and what might be slightly off?
– Robert
Dec 1 at 3:08
As an alternative I was looking at Bernoulli Trials and got close to the answer; but perhaps I was doing something wrong. For this example I set n (trials) = 6, k (number of successes) = calculated for when k is 3:6, p (p success) = .1 and q (p failure) = 1-p. Since there are 10 nodes I multiplied the answer (0.01585) by 10 to get a P(Success) = 0.1585. Thoughts on this approach and what might be slightly off?
– Robert
Dec 1 at 3:08
add a comment |
The following solution uses an exponential generating function (EGF).
It may be simpler to solve the complementary problem. What is the probability that all nodes have no more than 2 of the 6 sources assigned to them? The sources may be assigned to the nodes in $10^6$ possible ways, all of which we assume are equally likely. We would like to count the number of ways in which each node has 0, 1, or 2 sources assigned. More generally, we might count the number of ways that $r$ sources can be assigned. The EGF for the number of ways sources can be assigned to a single node is $1+x+(1/2!)x^2$, so the EGF for a sequence of $10$ such assignments is
$$f(x) = left( 1 + x + frac{1}{2!} x^2 right)^{10}$$
The EGF gives the number of ways any number of sources can be assigned to the nodes, but all we really need is the number of ways 6 sources can be assigned. Expanding $f(x)$, we find the coefficient of $x^6$ is $1,170$, so the number of ways 6 sources can be assigned to the nodes subject to the given constraints is $6! times 1170 = 842,400$, and the associated probability is $$frac{842,400}{10^6} = 0.8424$$
(I used a computer algebra system for the expansion, but I think that with a little work one could compute the coefficient with pencil and paper.)
So the answer to the original problem, the probability that at least one node has three or more sources assigned to it, is
$$1 - 0.8424 = boxed{0.1576}$$
add a comment |
The following solution uses an exponential generating function (EGF).
It may be simpler to solve the complementary problem. What is the probability that all nodes have no more than 2 of the 6 sources assigned to them? The sources may be assigned to the nodes in $10^6$ possible ways, all of which we assume are equally likely. We would like to count the number of ways in which each node has 0, 1, or 2 sources assigned. More generally, we might count the number of ways that $r$ sources can be assigned. The EGF for the number of ways sources can be assigned to a single node is $1+x+(1/2!)x^2$, so the EGF for a sequence of $10$ such assignments is
$$f(x) = left( 1 + x + frac{1}{2!} x^2 right)^{10}$$
The EGF gives the number of ways any number of sources can be assigned to the nodes, but all we really need is the number of ways 6 sources can be assigned. Expanding $f(x)$, we find the coefficient of $x^6$ is $1,170$, so the number of ways 6 sources can be assigned to the nodes subject to the given constraints is $6! times 1170 = 842,400$, and the associated probability is $$frac{842,400}{10^6} = 0.8424$$
(I used a computer algebra system for the expansion, but I think that with a little work one could compute the coefficient with pencil and paper.)
So the answer to the original problem, the probability that at least one node has three or more sources assigned to it, is
$$1 - 0.8424 = boxed{0.1576}$$
add a comment |
The following solution uses an exponential generating function (EGF).
It may be simpler to solve the complementary problem. What is the probability that all nodes have no more than 2 of the 6 sources assigned to them? The sources may be assigned to the nodes in $10^6$ possible ways, all of which we assume are equally likely. We would like to count the number of ways in which each node has 0, 1, or 2 sources assigned. More generally, we might count the number of ways that $r$ sources can be assigned. The EGF for the number of ways sources can be assigned to a single node is $1+x+(1/2!)x^2$, so the EGF for a sequence of $10$ such assignments is
$$f(x) = left( 1 + x + frac{1}{2!} x^2 right)^{10}$$
The EGF gives the number of ways any number of sources can be assigned to the nodes, but all we really need is the number of ways 6 sources can be assigned. Expanding $f(x)$, we find the coefficient of $x^6$ is $1,170$, so the number of ways 6 sources can be assigned to the nodes subject to the given constraints is $6! times 1170 = 842,400$, and the associated probability is $$frac{842,400}{10^6} = 0.8424$$
(I used a computer algebra system for the expansion, but I think that with a little work one could compute the coefficient with pencil and paper.)
So the answer to the original problem, the probability that at least one node has three or more sources assigned to it, is
$$1 - 0.8424 = boxed{0.1576}$$
The following solution uses an exponential generating function (EGF).
It may be simpler to solve the complementary problem. What is the probability that all nodes have no more than 2 of the 6 sources assigned to them? The sources may be assigned to the nodes in $10^6$ possible ways, all of which we assume are equally likely. We would like to count the number of ways in which each node has 0, 1, or 2 sources assigned. More generally, we might count the number of ways that $r$ sources can be assigned. The EGF for the number of ways sources can be assigned to a single node is $1+x+(1/2!)x^2$, so the EGF for a sequence of $10$ such assignments is
$$f(x) = left( 1 + x + frac{1}{2!} x^2 right)^{10}$$
The EGF gives the number of ways any number of sources can be assigned to the nodes, but all we really need is the number of ways 6 sources can be assigned. Expanding $f(x)$, we find the coefficient of $x^6$ is $1,170$, so the number of ways 6 sources can be assigned to the nodes subject to the given constraints is $6! times 1170 = 842,400$, and the associated probability is $$frac{842,400}{10^6} = 0.8424$$
(I used a computer algebra system for the expansion, but I think that with a little work one could compute the coefficient with pencil and paper.)
So the answer to the original problem, the probability that at least one node has three or more sources assigned to it, is
$$1 - 0.8424 = boxed{0.1576}$$
answered Nov 30 at 15:29
awkward
5,82111022
5,82111022
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%2f3019062%2fprobability-of-3-streams-of-data-on-same-compute-node%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
No, the reasoning is not correct even for the $n=3$ case because the factor $2$ is unjustified. It also falls short of reaching the six specified data sources. You do have the beginning of a correct approach. I remember answering a similar problem that was harder. I'll find a link for you.
– hardmath
Nov 29 at 19:43
Thanks, appreciate the assistance. Anything you can do to point me in the right direction.
– Robert
Nov 29 at 20:38
So how about we use something like the following: (6!) / (3!*(6-3)!) = 20 outcomes with a chance of 3 collisions For 6 sources and 10 destinations there are 10^6 outcomes, or 1,000,000 The probability would then be 20/1,000,000?
– Robert
Nov 29 at 22:56
I've added to my Answer a note which develops the solution along the line you suggest, using combinations to pick out the successful outcomes among $10^6$ possibilities.
– hardmath
Nov 30 at 17:41