Urn problem, probability of drawing 2 balls of the same color
$begingroup$
Here is my question:
Having an urn with $frac{n}{2}$ black balls and $frac{n}{2}$ red balls. What is the probability when drawing two balls at the same time to draw two balls of the same color if you repeatedly draw and put one ball back until only two balls are left in the urn.
$Pr[$Drawing only pairs of the same color$] = ? $
This problem originates from a graph problem. Having two graphs A and B each with $|V|= frac{n}{2}$ vertices. Picking two vertices from the combined vertices of A and B uniformly at random and merging them into one vertice (which is then again in the set as type A or B or AB). Doing this until there are only two vertices left. What is the probability to always pick two vertices from A or two vertices from B.
For the first draw the probability is, I believe, $2∗frac{1}{2}*frac{frac{n}{2}-1}{n−1} $but then the possible combinations grow exponentially large and I don't know how to combine them in a closed form.
combinatorics probability-theory
asked Dec 6 '18 at 17:51
dave4422dave4422
11
$endgroup$
add a comment |
$begingroup$
Here is my question:
Having an urn with $frac{n}{2}$ black balls and $frac{n}{2}$ red balls. What is the probability when drawing two balls at the same time to draw two balls of the same color if you repeatedly draw and put one ball back until only two balls are left in the urn.
$Pr[$Drawing only pairs of the same color$] = ? $
This problem originates from a graph problem. Having two graphs A and B each with $|V|= frac{n}{2}$ vertices. Picking two vertices from the combined vertices of A and B uniformly at random and merging them into one vertice (which is then again in the set as type A or B or AB). Doing this until there are only two vertices left. What is the probability to always pick two vertices from A or two vertices from B.
For the first draw the probability is, I believe, $2∗frac{1}{2}*frac{frac{n}{2}-1}{n−1} $but then the possible combinations grow exponentially large and I don't know how to combine them in a closed form.
combinatorics probability-theory
asked Dec 6 '18 at 17:51
dave4422dave4422
11
$endgroup$
1
$begingroup$
Just to be sure, you want the probability that every draw comprises two balls of the same color?
$endgroup$
– saulspatz
Dec 6 '18 at 18:06
$begingroup$
yes, I need to show that this propability is exponentially small (dependent on n)
$endgroup$
– dave4422
Dec 6 '18 at 18:08
$begingroup$
What have you done so far? How far have you gotten? Where are you stuck?
$endgroup$
– saulspatz
Dec 6 '18 at 18:12
$begingroup$
You ought to put your thoughts on the problem into the body of the question. Also, include the graph problem you are modeling. With no more context than you have given, you are liable have the question closed. Many people browsing the question will vote to close without reading the comments, so be sure to edit the question.
$endgroup$
– saulspatz
Dec 6 '18 at 19:11
$begingroup$
Just to clarify, do you need an exact expression for the probability or just to show that it is exponentially small as a function of $n$?
$endgroup$
– saulspatz
Dec 7 '18 at 13:52
add a comment |
$begingroup$
Here is my question:
Having an urn with $frac{n}{2}$ black balls and $frac{n}{2}$ red balls. What is the probability when drawing two balls at the same time to draw two balls of the same color if you repeatedly draw and put one ball back until only two balls are left in the urn.
$Pr[$Drawing only pairs of the same color$] = ? $
This problem originates from a graph problem. Having two graphs A and B each with $|V|= frac{n}{2}$ vertices. Picking two vertices from the combined vertices of A and B uniformly at random and merging them into one vertice (which is then again in the set as type A or B or AB). Doing this until there are only two vertices left. What is the probability to always pick two vertices from A or two vertices from B.
For the first draw the probability is, I believe, $2∗frac{1}{2}*frac{frac{n}{2}-1}{n−1} $but then the possible combinations grow exponentially large and I don't know how to combine them in a closed form.
combinatorics probability-theory
asked Dec 6 '18 at 17:51
dave4422dave4422
11
$endgroup$
Here is my question:
Having an urn with $frac{n}{2}$ black balls and $frac{n}{2}$ red balls. What is the probability when drawing two balls at the same time to draw two balls of the same color if you repeatedly draw and put one ball back until only two balls are left in the urn.
$Pr[$Drawing only pairs of the same color$] = ? $
This problem originates from a graph problem. Having two graphs A and B each with $|V|= frac{n}{2}$ vertices. Picking two vertices from the combined vertices of A and B uniformly at random and merging them into one vertice (which is then again in the set as type A or B or AB). Doing this until there are only two vertices left. What is the probability to always pick two vertices from A or two vertices from B.
For the first draw the probability is, I believe, $2∗frac{1}{2}*frac{frac{n}{2}-1}{n−1} $but then the possible combinations grow exponentially large and I don't know how to combine them in a closed form.
combinatorics probability-theory
combinatorics probability-theory
asked Dec 6 '18 at 17:51
dave4422dave4422
11
asked Dec 6 '18 at 17:51
dave4422dave4422
11
edited Dec 6 '18 at 19:17
dave4422
asked Dec 6 '18 at 17:51
dave4422dave4422
11
asked Dec 6 '18 at 17:51
dave4422dave4422
11
asked Dec 6 '18 at 17:51
dave4422dave4422
11
11
1
$begingroup$
Just to be sure, you want the probability that every draw comprises two balls of the same color?
$endgroup$
– saulspatz
Dec 6 '18 at 18:06
$begingroup$
yes, I need to show that this propability is exponentially small (dependent on n)
$endgroup$
– dave4422
Dec 6 '18 at 18:08
$begingroup$
What have you done so far? How far have you gotten? Where are you stuck?
$endgroup$
– saulspatz
Dec 6 '18 at 18:12
$begingroup$
You ought to put your thoughts on the problem into the body of the question. Also, include the graph problem you are modeling. With no more context than you have given, you are liable have the question closed. Many people browsing the question will vote to close without reading the comments, so be sure to edit the question.
$endgroup$
– saulspatz
Dec 6 '18 at 19:11
$begingroup$
Just to clarify, do you need an exact expression for the probability or just to show that it is exponentially small as a function of $n$?
$endgroup$
– saulspatz
Dec 7 '18 at 13:52
add a comment |
1
$begingroup$
Just to be sure, you want the probability that every draw comprises two balls of the same color?
$endgroup$
– saulspatz
Dec 6 '18 at 18:06
$begingroup$
yes, I need to show that this propability is exponentially small (dependent on n)
$endgroup$
– dave4422
Dec 6 '18 at 18:08
$begingroup$
What have you done so far? How far have you gotten? Where are you stuck?
$endgroup$
– saulspatz
Dec 6 '18 at 18:12
$begingroup$
You ought to put your thoughts on the problem into the body of the question. Also, include the graph problem you are modeling. With no more context than you have given, you are liable have the question closed. Many people browsing the question will vote to close without reading the comments, so be sure to edit the question.
$endgroup$
– saulspatz
Dec 6 '18 at 19:11
$begingroup$
Just to clarify, do you need an exact expression for the probability or just to show that it is exponentially small as a function of $n$?
$endgroup$
– saulspatz
Dec 7 '18 at 13:52
1
1
$begingroup$
Just to be sure, you want the probability that every draw comprises two balls of the same color?
$endgroup$
– saulspatz
Dec 6 '18 at 18:06
$begingroup$
Just to be sure, you want the probability that every draw comprises two balls of the same color?
$endgroup$
– saulspatz
Dec 6 '18 at 18:06
$begingroup$
yes, I need to show that this propability is exponentially small (dependent on n)
$endgroup$
– dave4422
Dec 6 '18 at 18:08
$begingroup$
yes, I need to show that this propability is exponentially small (dependent on n)
$endgroup$
– dave4422
Dec 6 '18 at 18:08
$begingroup$
What have you done so far? How far have you gotten? Where are you stuck?
$endgroup$
– saulspatz
Dec 6 '18 at 18:12
$begingroup$
What have you done so far? How far have you gotten? Where are you stuck?
$endgroup$
– saulspatz
Dec 6 '18 at 18:12
$begingroup$
You ought to put your thoughts on the problem into the body of the question. Also, include the graph problem you are modeling. With no more context than you have given, you are liable have the question closed. Many people browsing the question will vote to close without reading the comments, so be sure to edit the question.
$endgroup$
– saulspatz
Dec 6 '18 at 19:11
$begingroup$
You ought to put your thoughts on the problem into the body of the question. Also, include the graph problem you are modeling. With no more context than you have given, you are liable have the question closed. Many people browsing the question will vote to close without reading the comments, so be sure to edit the question.
$endgroup$
– saulspatz
Dec 6 '18 at 19:11
$begingroup$
Just to clarify, do you need an exact expression for the probability or just to show that it is exponentially small as a function of $n$?
$endgroup$
– saulspatz
Dec 7 '18 at 13:52
$begingroup$
Just to clarify, do you need an exact expression for the probability or just to show that it is exponentially small as a function of $n$?
$endgroup$
– saulspatz
Dec 7 '18 at 13:52
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I haven't been able to find an expression for the probability, or even an approach to it, so I'm trying to prove that the probability is exponentially small as a function of $n$. I think I have the right idea, but I can't quite dispose of it. Suppose we have $r$ red balls and $b$ black balls. Say that the red balls are in the minority if $rle b,$ and in the majority if $r>b$ and similarly for the black balls. The probability of choosing two balls of the same color is $${{rchoose2}+{bchoose2}over{r+bchoose2}}le1$$ If the red balls are in the minority, then the probability of choosing two red balls is $$
{{rchoose2}over{r+bchoose2}}<=frac12{{rchoose2}+{bchoose2}over{r+bchoose2}}lefrac12cdot1=frac12$$ It seems intuitively clear that, to fulfill the conditions in the problem, we must choose balls in the minority at least as often as balls in the majority (with perhaps some minor adjustment) so that we can say that the probability of overall success is $le left(frac12right)^{n/2}.$ I haven't seen how to prove this formally though. Some kind of inductive argument perhaps?
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
$endgroup$
$begingroup$
@dave4422 Please delete your prior comments, as they don't relate to my revised answer.
$endgroup$
– saulspatz
Dec 7 '18 at 15:11
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%2f3028823%2furn-problem-probability-of-drawing-2-balls-of-the-same-color%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$
I haven't been able to find an expression for the probability, or even an approach to it, so I'm trying to prove that the probability is exponentially small as a function of $n$. I think I have the right idea, but I can't quite dispose of it. Suppose we have $r$ red balls and $b$ black balls. Say that the red balls are in the minority if $rle b,$ and in the majority if $r>b$ and similarly for the black balls. The probability of choosing two balls of the same color is $${{rchoose2}+{bchoose2}over{r+bchoose2}}le1$$ If the red balls are in the minority, then the probability of choosing two red balls is $$
{{rchoose2}over{r+bchoose2}}<=frac12{{rchoose2}+{bchoose2}over{r+bchoose2}}lefrac12cdot1=frac12$$ It seems intuitively clear that, to fulfill the conditions in the problem, we must choose balls in the minority at least as often as balls in the majority (with perhaps some minor adjustment) so that we can say that the probability of overall success is $le left(frac12right)^{n/2}.$ I haven't seen how to prove this formally though. Some kind of inductive argument perhaps?
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
$endgroup$
$begingroup$
@dave4422 Please delete your prior comments, as they don't relate to my revised answer.
$endgroup$
– saulspatz
Dec 7 '18 at 15:11
add a comment |
$begingroup$
I haven't been able to find an expression for the probability, or even an approach to it, so I'm trying to prove that the probability is exponentially small as a function of $n$. I think I have the right idea, but I can't quite dispose of it. Suppose we have $r$ red balls and $b$ black balls. Say that the red balls are in the minority if $rle b,$ and in the majority if $r>b$ and similarly for the black balls. The probability of choosing two balls of the same color is $${{rchoose2}+{bchoose2}over{r+bchoose2}}le1$$ If the red balls are in the minority, then the probability of choosing two red balls is $$
{{rchoose2}over{r+bchoose2}}<=frac12{{rchoose2}+{bchoose2}over{r+bchoose2}}lefrac12cdot1=frac12$$ It seems intuitively clear that, to fulfill the conditions in the problem, we must choose balls in the minority at least as often as balls in the majority (with perhaps some minor adjustment) so that we can say that the probability of overall success is $le left(frac12right)^{n/2}.$ I haven't seen how to prove this formally though. Some kind of inductive argument perhaps?
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
$endgroup$
$begingroup$
@dave4422 Please delete your prior comments, as they don't relate to my revised answer.
$endgroup$
– saulspatz
Dec 7 '18 at 15:11
add a comment |
$begingroup$
I haven't been able to find an expression for the probability, or even an approach to it, so I'm trying to prove that the probability is exponentially small as a function of $n$. I think I have the right idea, but I can't quite dispose of it. Suppose we have $r$ red balls and $b$ black balls. Say that the red balls are in the minority if $rle b,$ and in the majority if $r>b$ and similarly for the black balls. The probability of choosing two balls of the same color is $${{rchoose2}+{bchoose2}over{r+bchoose2}}le1$$ If the red balls are in the minority, then the probability of choosing two red balls is $$
{{rchoose2}over{r+bchoose2}}<=frac12{{rchoose2}+{bchoose2}over{r+bchoose2}}lefrac12cdot1=frac12$$ It seems intuitively clear that, to fulfill the conditions in the problem, we must choose balls in the minority at least as often as balls in the majority (with perhaps some minor adjustment) so that we can say that the probability of overall success is $le left(frac12right)^{n/2}.$ I haven't seen how to prove this formally though. Some kind of inductive argument perhaps?
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
$endgroup$
I haven't been able to find an expression for the probability, or even an approach to it, so I'm trying to prove that the probability is exponentially small as a function of $n$. I think I have the right idea, but I can't quite dispose of it. Suppose we have $r$ red balls and $b$ black balls. Say that the red balls are in the minority if $rle b,$ and in the majority if $r>b$ and similarly for the black balls. The probability of choosing two balls of the same color is $${{rchoose2}+{bchoose2}over{r+bchoose2}}le1$$ If the red balls are in the minority, then the probability of choosing two red balls is $$
{{rchoose2}over{r+bchoose2}}<=frac12{{rchoose2}+{bchoose2}over{r+bchoose2}}lefrac12cdot1=frac12$$ It seems intuitively clear that, to fulfill the conditions in the problem, we must choose balls in the minority at least as often as balls in the majority (with perhaps some minor adjustment) so that we can say that the probability of overall success is $le left(frac12right)^{n/2}.$ I haven't seen how to prove this formally though. Some kind of inductive argument perhaps?
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
edited Dec 7 '18 at 15:08
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
answered Dec 6 '18 at 18:34
saulspatzsaulspatz
16.6k31333
16.6k31333
$begingroup$
@dave4422 Please delete your prior comments, as they don't relate to my revised answer.
$endgroup$
– saulspatz
Dec 7 '18 at 15:11
add a comment |
$begingroup$
@dave4422 Please delete your prior comments, as they don't relate to my revised answer.
$endgroup$
– saulspatz
Dec 7 '18 at 15:11
$begingroup$
@dave4422 Please delete your prior comments, as they don't relate to my revised answer.
$endgroup$
– saulspatz
Dec 7 '18 at 15:11
$begingroup$
@dave4422 Please delete your prior comments, as they don't relate to my revised answer.
$endgroup$
– saulspatz
Dec 7 '18 at 15:11
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%2f3028823%2furn-problem-probability-of-drawing-2-balls-of-the-same-color%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
1
$begingroup$
Just to be sure, you want the probability that every draw comprises two balls of the same color?
$endgroup$
– saulspatz
Dec 6 '18 at 18:06
$begingroup$
yes, I need to show that this propability is exponentially small (dependent on n)
$endgroup$
– dave4422
Dec 6 '18 at 18:08
$begingroup$
What have you done so far? How far have you gotten? Where are you stuck?
$endgroup$
– saulspatz
Dec 6 '18 at 18:12
$begingroup$
You ought to put your thoughts on the problem into the body of the question. Also, include the graph problem you are modeling. With no more context than you have given, you are liable have the question closed. Many people browsing the question will vote to close without reading the comments, so be sure to edit the question.
$endgroup$
– saulspatz
Dec 6 '18 at 19:11
$begingroup$
Just to clarify, do you need an exact expression for the probability or just to show that it is exponentially small as a function of $n$?
$endgroup$
– saulspatz
Dec 7 '18 at 13:52