Mixing
The Classic Matching Problem in Probability
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I have some questions about the solution to this problem for $n=3$. The problem goes:
"Suppose that each of three men at a party throws his
hat into the center of the room. The hats are first mixed up and then each man randomly selects a hat. What is the probability that none of the three men selects his own hat?"
One of the solutions reads Equation 1
$P($no man selects his hat$) = 1 - P($at least one man selects his own hat$) = 1 - P(E1∪E2∪E3)$
I am having a hard time understanding why
$P($at least one man selects his own hat$) = P(E1∪E2∪E3)$
I can understand the complement, basically if $E_i$ is the event that man $i$ picks his own hat, then we are looking for the complement of $cap E_i$ which equals $cup E_i^c$. However is the union of events to be used when we answer the question of at least one event occurring?
My second question is this:
while I was trying to solve this problem for $n=3$, I used the following reasoning:
$P($no man selects his hat $) = 1 - P(E_1) - P(E_1E_2) - P(E_1E_2E_3)$
where $E_1$ is the event that only one man picks his own hat
$E_1E_2$ is the event that two men pick their own hat, and $E_1E_2E_3$ the event that all did.
In my computations, I ended up with $1/3$, which is the same probability we get if we use $ $
Equation 1. Is my reasoning correct?
probability probability-theory statistics
asked Jul 23 at 23:09
Note
206
add a comment |Â
up vote
0
down vote
favorite
I have some questions about the solution to this problem for $n=3$. The problem goes:
"Suppose that each of three men at a party throws his
hat into the center of the room. The hats are first mixed up and then each man randomly selects a hat. What is the probability that none of the three men selects his own hat?"
One of the solutions reads Equation 1
$P($no man selects his hat$) = 1 - P($at least one man selects his own hat$) = 1 - P(E1∪E2∪E3)$
I am having a hard time understanding why
$P($at least one man selects his own hat$) = P(E1∪E2∪E3)$
I can understand the complement, basically if $E_i$ is the event that man $i$ picks his own hat, then we are looking for the complement of $cap E_i$ which equals $cup E_i^c$. However is the union of events to be used when we answer the question of at least one event occurring?
My second question is this:
while I was trying to solve this problem for $n=3$, I used the following reasoning:
$P($no man selects his hat $) = 1 - P(E_1) - P(E_1E_2) - P(E_1E_2E_3)$
where $E_1$ is the event that only one man picks his own hat
$E_1E_2$ is the event that two men pick their own hat, and $E_1E_2E_3$ the event that all did.
In my computations, I ended up with $1/3$, which is the same probability we get if we use $ $
Equation 1. Is my reasoning correct?
probability probability-theory statistics
asked Jul 23 at 23:09
Note
206
That looks like the number of derangement divided by all permutations. To put into a formula $$frac!nn!~=~sum_k=0^n frac(-1)^kk!$$ In your case $n=3$. Derangements are permutations without fixed points (See en.wikipedia.org/wiki/Derangement).
– mrtaurho
Jul 23 at 23:16
For your first question: Yes, when you consider the union of two elements $x,y$ as another way to say $x$ or $y$. In a context of probability this equals to that the union of events denotes that at least on event is occurring. For your second I want to clarify something: Do you want to verify the equation $P(E_1cup E_2 cup E_3)~=~P(E_1)+P(E_1cap E_2)+P(E_1cap E_2 cap E_3)$?
– mrtaurho
Jul 23 at 23:49
@mrtaurho, yes. Does the equation make sense?
– Note
Jul 24 at 0:28
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have some questions about the solution to this problem for $n=3$. The problem goes:
"Suppose that each of three men at a party throws his
hat into the center of the room. The hats are first mixed up and then each man randomly selects a hat. What is the probability that none of the three men selects his own hat?"
One of the solutions reads Equation 1
$P($no man selects his hat$) = 1 - P($at least one man selects his own hat$) = 1 - P(E1∪E2∪E3)$
I am having a hard time understanding why
$P($at least one man selects his own hat$) = P(E1∪E2∪E3)$
I can understand the complement, basically if $E_i$ is the event that man $i$ picks his own hat, then we are looking for the complement of $cap E_i$ which equals $cup E_i^c$. However is the union of events to be used when we answer the question of at least one event occurring?
My second question is this:
while I was trying to solve this problem for $n=3$, I used the following reasoning:
$P($no man selects his hat $) = 1 - P(E_1) - P(E_1E_2) - P(E_1E_2E_3)$
where $E_1$ is the event that only one man picks his own hat
$E_1E_2$ is the event that two men pick their own hat, and $E_1E_2E_3$ the event that all did.
In my computations, I ended up with $1/3$, which is the same probability we get if we use $ $
Equation 1. Is my reasoning correct?
probability probability-theory statistics
asked Jul 23 at 23:09
Note
206
I have some questions about the solution to this problem for $n=3$. The problem goes:
"Suppose that each of three men at a party throws his
hat into the center of the room. The hats are first mixed up and then each man randomly selects a hat. What is the probability that none of the three men selects his own hat?"
One of the solutions reads Equation 1
$P($no man selects his hat$) = 1 - P($at least one man selects his own hat$) = 1 - P(E1∪E2∪E3)$
I am having a hard time understanding why
$P($at least one man selects his own hat$) = P(E1∪E2∪E3)$
I can understand the complement, basically if $E_i$ is the event that man $i$ picks his own hat, then we are looking for the complement of $cap E_i$ which equals $cup E_i^c$. However is the union of events to be used when we answer the question of at least one event occurring?
My second question is this:
while I was trying to solve this problem for $n=3$, I used the following reasoning:
$P($no man selects his hat $) = 1 - P(E_1) - P(E_1E_2) - P(E_1E_2E_3)$
where $E_1$ is the event that only one man picks his own hat
$E_1E_2$ is the event that two men pick their own hat, and $E_1E_2E_3$ the event that all did.
In my computations, I ended up with $1/3$, which is the same probability we get if we use $ $
Equation 1. Is my reasoning correct?
probability probability-theory statistics
asked Jul 23 at 23:09
Note
206
asked Jul 23 at 23:09
Note
206
asked Jul 23 at 23:09
Note
206
asked Jul 23 at 23:09
Note
206
206
That looks like the number of derangement divided by all permutations. To put into a formula $$frac!nn!~=~sum_k=0^n frac(-1)^kk!$$ In your case $n=3$. Derangements are permutations without fixed points (See en.wikipedia.org/wiki/Derangement).
– mrtaurho
Jul 23 at 23:16
For your first question: Yes, when you consider the union of two elements $x,y$ as another way to say $x$ or $y$. In a context of probability this equals to that the union of events denotes that at least on event is occurring. For your second I want to clarify something: Do you want to verify the equation $P(E_1cup E_2 cup E_3)~=~P(E_1)+P(E_1cap E_2)+P(E_1cap E_2 cap E_3)$?
– mrtaurho
Jul 23 at 23:49
@mrtaurho, yes. Does the equation make sense?
– Note
Jul 24 at 0:28
add a comment |Â
That looks like the number of derangement divided by all permutations. To put into a formula $$frac!nn!~=~sum_k=0^n frac(-1)^kk!$$ In your case $n=3$. Derangements are permutations without fixed points (See en.wikipedia.org/wiki/Derangement).
– mrtaurho
Jul 23 at 23:16
For your first question: Yes, when you consider the union of two elements $x,y$ as another way to say $x$ or $y$. In a context of probability this equals to that the union of events denotes that at least on event is occurring. For your second I want to clarify something: Do you want to verify the equation $P(E_1cup E_2 cup E_3)~=~P(E_1)+P(E_1cap E_2)+P(E_1cap E_2 cap E_3)$?
– mrtaurho
Jul 23 at 23:49
@mrtaurho, yes. Does the equation make sense?
– Note
Jul 24 at 0:28
That looks like the number of derangement divided by all permutations. To put into a formula $$frac!nn!~=~sum_k=0^n frac(-1)^kk!$$ In your case $n=3$. Derangements are permutations without fixed points (See en.wikipedia.org/wiki/Derangement).
– mrtaurho
Jul 23 at 23:16
That looks like the number of derangement divided by all permutations. To put into a formula $$frac!nn!~=~sum_k=0^n frac(-1)^kk!$$ In your case $n=3$. Derangements are permutations without fixed points (See en.wikipedia.org/wiki/Derangement).
– mrtaurho
Jul 23 at 23:16
For your first question: Yes, when you consider the union of two elements $x,y$ as another way to say $x$ or $y$. In a context of probability this equals to that the union of events denotes that at least on event is occurring. For your second I want to clarify something: Do you want to verify the equation $P(E_1cup E_2 cup E_3)~=~P(E_1)+P(E_1cap E_2)+P(E_1cap E_2 cap E_3)$?
– mrtaurho
Jul 23 at 23:49
For your first question: Yes, when you consider the union of two elements $x,y$ as another way to say $x$ or $y$. In a context of probability this equals to that the union of events denotes that at least on event is occurring. For your second I want to clarify something: Do you want to verify the equation $P(E_1cup E_2 cup E_3)~=~P(E_1)+P(E_1cap E_2)+P(E_1cap E_2 cap E_3)$?
– mrtaurho
Jul 23 at 23:49
@mrtaurho, yes. Does the equation make sense?
– Note
Jul 24 at 0:28
@mrtaurho, yes. Does the equation make sense?
– Note
Jul 24 at 0:28
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
You have to think about what kind of outcomes are possible when we say "at least one man selects his own hat." If $E_i$ represents the outcome that man $i$ selects his own hat, then $E_1 cup E_2 cup E_3$ includes the outcome where all three select their own hat; it also includes the outcome where exactly one man selects his own hat. Note it is impossible for exactly two men to select their own hat--since if this happens, the remaining hat is necessarily selected by its owner. So it just so happens in this case that $$beginalign*
Pr[E_1 cup E_2 cup E_3] &= Pr[E_1 cap bar E_2 cap bar E_3] + Pr[bar E_1 cap E_2 cap bar E_3] + Pr[bar E_1 cap bar E_2 cap E_3] \ &quad + Pr[E_1 cap E_2 cap E_3].
endalign*$$
I recommend that you draw a Venn diagram to understand this.
In regard to your second question, you are being sloppy with your notation, and as a result, you are not enumerating all of the relevant outcomes. Your calculation worked only because of coincidence. A correct calculation requires you to consider the outcomes of all three men's selections, so if you write $Pr[E_1]$, this is just the unconditional probability of the first man selecting his own hat, which is $1/3$. But this probability also counts the event where all three men select their own hat, since $$E_1 cap E_2 cap E_3 subset E_1.$$
As an exercise, try to perform the same computation for four men.
answered Jul 24 at 5:59
heropup
59.7k65895
heropup Thank you
– Note
Jul 30 at 5:36
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
You have to think about what kind of outcomes are possible when we say "at least one man selects his own hat." If $E_i$ represents the outcome that man $i$ selects his own hat, then $E_1 cup E_2 cup E_3$ includes the outcome where all three select their own hat; it also includes the outcome where exactly one man selects his own hat. Note it is impossible for exactly two men to select their own hat--since if this happens, the remaining hat is necessarily selected by its owner. So it just so happens in this case that $$beginalign*
Pr[E_1 cup E_2 cup E_3] &= Pr[E_1 cap bar E_2 cap bar E_3] + Pr[bar E_1 cap E_2 cap bar E_3] + Pr[bar E_1 cap bar E_2 cap E_3] \ &quad + Pr[E_1 cap E_2 cap E_3].
endalign*$$
I recommend that you draw a Venn diagram to understand this.
In regard to your second question, you are being sloppy with your notation, and as a result, you are not enumerating all of the relevant outcomes. Your calculation worked only because of coincidence. A correct calculation requires you to consider the outcomes of all three men's selections, so if you write $Pr[E_1]$, this is just the unconditional probability of the first man selecting his own hat, which is $1/3$. But this probability also counts the event where all three men select their own hat, since $$E_1 cap E_2 cap E_3 subset E_1.$$
As an exercise, try to perform the same computation for four men.
answered Jul 24 at 5:59
heropup
59.7k65895
heropup Thank you
– Note
Jul 30 at 5:36
add a comment |Â
up vote
2
down vote
accepted
You have to think about what kind of outcomes are possible when we say "at least one man selects his own hat." If $E_i$ represents the outcome that man $i$ selects his own hat, then $E_1 cup E_2 cup E_3$ includes the outcome where all three select their own hat; it also includes the outcome where exactly one man selects his own hat. Note it is impossible for exactly two men to select their own hat--since if this happens, the remaining hat is necessarily selected by its owner. So it just so happens in this case that $$beginalign*
Pr[E_1 cup E_2 cup E_3] &= Pr[E_1 cap bar E_2 cap bar E_3] + Pr[bar E_1 cap E_2 cap bar E_3] + Pr[bar E_1 cap bar E_2 cap E_3] \ &quad + Pr[E_1 cap E_2 cap E_3].
endalign*$$
I recommend that you draw a Venn diagram to understand this.
In regard to your second question, you are being sloppy with your notation, and as a result, you are not enumerating all of the relevant outcomes. Your calculation worked only because of coincidence. A correct calculation requires you to consider the outcomes of all three men's selections, so if you write $Pr[E_1]$, this is just the unconditional probability of the first man selecting his own hat, which is $1/3$. But this probability also counts the event where all three men select their own hat, since $$E_1 cap E_2 cap E_3 subset E_1.$$
As an exercise, try to perform the same computation for four men.
answered Jul 24 at 5:59
heropup
59.7k65895
heropup Thank you
– Note
Jul 30 at 5:36
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
You have to think about what kind of outcomes are possible when we say "at least one man selects his own hat." If $E_i$ represents the outcome that man $i$ selects his own hat, then $E_1 cup E_2 cup E_3$ includes the outcome where all three select their own hat; it also includes the outcome where exactly one man selects his own hat. Note it is impossible for exactly two men to select their own hat--since if this happens, the remaining hat is necessarily selected by its owner. So it just so happens in this case that $$beginalign*
Pr[E_1 cup E_2 cup E_3] &= Pr[E_1 cap bar E_2 cap bar E_3] + Pr[bar E_1 cap E_2 cap bar E_3] + Pr[bar E_1 cap bar E_2 cap E_3] \ &quad + Pr[E_1 cap E_2 cap E_3].
endalign*$$
I recommend that you draw a Venn diagram to understand this.
In regard to your second question, you are being sloppy with your notation, and as a result, you are not enumerating all of the relevant outcomes. Your calculation worked only because of coincidence. A correct calculation requires you to consider the outcomes of all three men's selections, so if you write $Pr[E_1]$, this is just the unconditional probability of the first man selecting his own hat, which is $1/3$. But this probability also counts the event where all three men select their own hat, since $$E_1 cap E_2 cap E_3 subset E_1.$$
As an exercise, try to perform the same computation for four men.
answered Jul 24 at 5:59
heropup
59.7k65895
You have to think about what kind of outcomes are possible when we say "at least one man selects his own hat." If $E_i$ represents the outcome that man $i$ selects his own hat, then $E_1 cup E_2 cup E_3$ includes the outcome where all three select their own hat; it also includes the outcome where exactly one man selects his own hat. Note it is impossible for exactly two men to select their own hat--since if this happens, the remaining hat is necessarily selected by its owner. So it just so happens in this case that $$beginalign*
Pr[E_1 cup E_2 cup E_3] &= Pr[E_1 cap bar E_2 cap bar E_3] + Pr[bar E_1 cap E_2 cap bar E_3] + Pr[bar E_1 cap bar E_2 cap E_3] \ &quad + Pr[E_1 cap E_2 cap E_3].
endalign*$$
I recommend that you draw a Venn diagram to understand this.
In regard to your second question, you are being sloppy with your notation, and as a result, you are not enumerating all of the relevant outcomes. Your calculation worked only because of coincidence. A correct calculation requires you to consider the outcomes of all three men's selections, so if you write $Pr[E_1]$, this is just the unconditional probability of the first man selecting his own hat, which is $1/3$. But this probability also counts the event where all three men select their own hat, since $$E_1 cap E_2 cap E_3 subset E_1.$$
As an exercise, try to perform the same computation for four men.
answered Jul 24 at 5:59
heropup
59.7k65895
answered Jul 24 at 5:59
heropup
59.7k65895
answered Jul 24 at 5:59
heropup
59.7k65895
answered Jul 24 at 5:59
heropup
59.7k65895
59.7k65895
heropup Thank you
– Note
Jul 30 at 5:36
add a comment |Â
heropup Thank you
– Note
Jul 30 at 5:36
heropup Thank you
– Note
Jul 30 at 5:36
heropup Thank you
– Note
Jul 30 at 5:36
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860852%2fthe-classic-matching-problem-in-probability%23new-answer', 'question_page');
);
Post as a guest
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
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
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
That looks like the number of derangement divided by all permutations. To put into a formula $$frac!nn!~=~sum_k=0^n frac(-1)^kk!$$ In your case $n=3$. Derangements are permutations without fixed points (See en.wikipedia.org/wiki/Derangement).
– mrtaurho
Jul 23 at 23:16
For your first question: Yes, when you consider the union of two elements $x,y$ as another way to say $x$ or $y$. In a context of probability this equals to that the union of events denotes that at least on event is occurring. For your second I want to clarify something: Do you want to verify the equation $P(E_1cup E_2 cup E_3)~=~P(E_1)+P(E_1cap E_2)+P(E_1cap E_2 cap E_3)$?
– mrtaurho
Jul 23 at 23:49
@mrtaurho, yes. Does the equation make sense?
– Note
Jul 24 at 0:28