Mixing
Secret Santa Probability Question
$begingroup$
In a Secret Santa game, a group of N friends each write their name on a slip of paper and place these slips in a bowl. The slips are mixed and each person draws a slip from the bowl. If anyone draws their own name then the whole process is repeated until each person draws some other person's name. Now that each person has another person's name, this is the name of the recipient of a gift from their Secret Santa. What is the probability that this process can be effected in 3 or fewer tries? Lex $X_i=1$ if person i does not draw their own name and $X_i=0$ if person i does draw their name. Do this for each $i=1,2,...,N$. What is $E[X]$? What is $E[X_1X_2]$? What is $E[X_1+...+X_N]$ for large N (i.e. as N goes to inf)?
It may help to envision this process as a random directed graph. This is a graph with a finite vertex set V. There is also a collection of arrows that is a subset of V x V. IIf (u,v) is in this subset then we draw an arrow from vertex u to vertex v. Notice that the rules imply that every vertex has an arrow departing from it and each vertex has an arrow pointing toward it. Use this representation to prove what the probability is.
I honestly have no idea where to star with this or what I'm even supposed to do... Any help is appreciated.
probability expectation
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
$endgroup$
add a comment |
$begingroup$
In a Secret Santa game, a group of N friends each write their name on a slip of paper and place these slips in a bowl. The slips are mixed and each person draws a slip from the bowl. If anyone draws their own name then the whole process is repeated until each person draws some other person's name. Now that each person has another person's name, this is the name of the recipient of a gift from their Secret Santa. What is the probability that this process can be effected in 3 or fewer tries? Lex $X_i=1$ if person i does not draw their own name and $X_i=0$ if person i does draw their name. Do this for each $i=1,2,...,N$. What is $E[X]$? What is $E[X_1X_2]$? What is $E[X_1+...+X_N]$ for large N (i.e. as N goes to inf)?
It may help to envision this process as a random directed graph. This is a graph with a finite vertex set V. There is also a collection of arrows that is a subset of V x V. IIf (u,v) is in this subset then we draw an arrow from vertex u to vertex v. Notice that the rules imply that every vertex has an arrow departing from it and each vertex has an arrow pointing toward it. Use this representation to prove what the probability is.
I honestly have no idea where to star with this or what I'm even supposed to do... Any help is appreciated.
probability expectation
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
$endgroup$
$begingroup$
omg 1/e i watched it in a video
$endgroup$
– Saketh Malyala
Jan 5 '18 at 17:45
add a comment |
$begingroup$
In a Secret Santa game, a group of N friends each write their name on a slip of paper and place these slips in a bowl. The slips are mixed and each person draws a slip from the bowl. If anyone draws their own name then the whole process is repeated until each person draws some other person's name. Now that each person has another person's name, this is the name of the recipient of a gift from their Secret Santa. What is the probability that this process can be effected in 3 or fewer tries? Lex $X_i=1$ if person i does not draw their own name and $X_i=0$ if person i does draw their name. Do this for each $i=1,2,...,N$. What is $E[X]$? What is $E[X_1X_2]$? What is $E[X_1+...+X_N]$ for large N (i.e. as N goes to inf)?
It may help to envision this process as a random directed graph. This is a graph with a finite vertex set V. There is also a collection of arrows that is a subset of V x V. IIf (u,v) is in this subset then we draw an arrow from vertex u to vertex v. Notice that the rules imply that every vertex has an arrow departing from it and each vertex has an arrow pointing toward it. Use this representation to prove what the probability is.
I honestly have no idea where to star with this or what I'm even supposed to do... Any help is appreciated.
probability expectation
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
$endgroup$
In a Secret Santa game, a group of N friends each write their name on a slip of paper and place these slips in a bowl. The slips are mixed and each person draws a slip from the bowl. If anyone draws their own name then the whole process is repeated until each person draws some other person's name. Now that each person has another person's name, this is the name of the recipient of a gift from their Secret Santa. What is the probability that this process can be effected in 3 or fewer tries? Lex $X_i=1$ if person i does not draw their own name and $X_i=0$ if person i does draw their name. Do this for each $i=1,2,...,N$. What is $E[X]$? What is $E[X_1X_2]$? What is $E[X_1+...+X_N]$ for large N (i.e. as N goes to inf)?
It may help to envision this process as a random directed graph. This is a graph with a finite vertex set V. There is also a collection of arrows that is a subset of V x V. IIf (u,v) is in this subset then we draw an arrow from vertex u to vertex v. Notice that the rules imply that every vertex has an arrow departing from it and each vertex has an arrow pointing toward it. Use this representation to prove what the probability is.
I honestly have no idea where to star with this or what I'm even supposed to do... Any help is appreciated.
probability expectation
probability expectation
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
asked Dec 11 '14 at 1:50
BryyoBryyo
14411
14411
$begingroup$
omg 1/e i watched it in a video
$endgroup$
– Saketh Malyala
Jan 5 '18 at 17:45
add a comment |
$begingroup$
omg 1/e i watched it in a video
$endgroup$
– Saketh Malyala
Jan 5 '18 at 17:45
$begingroup$
omg 1/e i watched it in a video
$endgroup$
– Saketh Malyala
Jan 5 '18 at 17:45
$begingroup$
omg 1/e i watched it in a video
$endgroup$
– Saketh Malyala
Jan 5 '18 at 17:45
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint: You are picking a random permutation and success is when you get a derangement. The chance of that is essentially $frac 1e$
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
$endgroup$
$begingroup$
Wait, so using derangement I can say that $!n = [frac{n!}e]$? And does that mean that the expected value is $E[X]=frac{!n}{n!}$ But what would $E[X_1X_2]$ be? Like how do I determine the value for each X?
$endgroup$
– Bryyo
Dec 11 '14 at 2:35
$begingroup$
That gives you the probability that you need to draw again. $E[X_1]$ is just the probability that the first person does not draw their own name. Can you calculate that?By symmetry, $E[X_i]$ is the same for all $i$ because you can just imagine reordering the drawing. $E[X_1X_2]$ is the chance that neither of the first two drew their own name. Can you calculate that? For the last, use the linearity of expectation.
$endgroup$
– Ross Millikan
Dec 11 '14 at 4:22
$begingroup$
Wait, why would it be the probability you need to draw again if !n is the number of ways in which they don't draw their own name and thus wouldn't need to draw again? And I don't really get how to do $E[X_i]$...
$endgroup$
– Bryyo
Dec 11 '14 at 7:21
$begingroup$
as $frac 1e$ of the permutations are derangements, you draw again with chance $1-frac 1e$. When the first person draws, (we are not talking about acceptable draws, but all draws), the chance of getting his own name is $frac 1n$, so $E[X_1]=frac 1n$
$endgroup$
– Ross Millikan
Dec 11 '14 at 14:25
$begingroup$
So if $E[X_1]=frac{1}n$, what is the part of the problem that "$X_i=1$ if a person doesn't draw their name and $X_i=0$ if they do?
$endgroup$
– Bryyo
Dec 11 '14 at 18:15
|
show 2 more comments
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%2f1061787%2fsecret-santa-probability-question%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$
Hint: You are picking a random permutation and success is when you get a derangement. The chance of that is essentially $frac 1e$
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
$endgroup$
$begingroup$
Wait, so using derangement I can say that $!n = [frac{n!}e]$? And does that mean that the expected value is $E[X]=frac{!n}{n!}$ But what would $E[X_1X_2]$ be? Like how do I determine the value for each X?
$endgroup$
– Bryyo
Dec 11 '14 at 2:35
$begingroup$
That gives you the probability that you need to draw again. $E[X_1]$ is just the probability that the first person does not draw their own name. Can you calculate that?By symmetry, $E[X_i]$ is the same for all $i$ because you can just imagine reordering the drawing. $E[X_1X_2]$ is the chance that neither of the first two drew their own name. Can you calculate that? For the last, use the linearity of expectation.
$endgroup$
– Ross Millikan
Dec 11 '14 at 4:22
$begingroup$
Wait, why would it be the probability you need to draw again if !n is the number of ways in which they don't draw their own name and thus wouldn't need to draw again? And I don't really get how to do $E[X_i]$...
$endgroup$
– Bryyo
Dec 11 '14 at 7:21
$begingroup$
as $frac 1e$ of the permutations are derangements, you draw again with chance $1-frac 1e$. When the first person draws, (we are not talking about acceptable draws, but all draws), the chance of getting his own name is $frac 1n$, so $E[X_1]=frac 1n$
$endgroup$
– Ross Millikan
Dec 11 '14 at 14:25
$begingroup$
So if $E[X_1]=frac{1}n$, what is the part of the problem that "$X_i=1$ if a person doesn't draw their name and $X_i=0$ if they do?
$endgroup$
– Bryyo
Dec 11 '14 at 18:15
|
show 2 more comments
$begingroup$
Hint: You are picking a random permutation and success is when you get a derangement. The chance of that is essentially $frac 1e$
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
$endgroup$
$begingroup$
Wait, so using derangement I can say that $!n = [frac{n!}e]$? And does that mean that the expected value is $E[X]=frac{!n}{n!}$ But what would $E[X_1X_2]$ be? Like how do I determine the value for each X?
$endgroup$
– Bryyo
Dec 11 '14 at 2:35
$begingroup$
That gives you the probability that you need to draw again. $E[X_1]$ is just the probability that the first person does not draw their own name. Can you calculate that?By symmetry, $E[X_i]$ is the same for all $i$ because you can just imagine reordering the drawing. $E[X_1X_2]$ is the chance that neither of the first two drew their own name. Can you calculate that? For the last, use the linearity of expectation.
$endgroup$
– Ross Millikan
Dec 11 '14 at 4:22
$begingroup$
Wait, why would it be the probability you need to draw again if !n is the number of ways in which they don't draw their own name and thus wouldn't need to draw again? And I don't really get how to do $E[X_i]$...
$endgroup$
– Bryyo
Dec 11 '14 at 7:21
$begingroup$
as $frac 1e$ of the permutations are derangements, you draw again with chance $1-frac 1e$. When the first person draws, (we are not talking about acceptable draws, but all draws), the chance of getting his own name is $frac 1n$, so $E[X_1]=frac 1n$
$endgroup$
– Ross Millikan
Dec 11 '14 at 14:25
$begingroup$
So if $E[X_1]=frac{1}n$, what is the part of the problem that "$X_i=1$ if a person doesn't draw their name and $X_i=0$ if they do?
$endgroup$
– Bryyo
Dec 11 '14 at 18:15
|
show 2 more comments
$begingroup$
Hint: You are picking a random permutation and success is when you get a derangement. The chance of that is essentially $frac 1e$
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
$endgroup$
Hint: You are picking a random permutation and success is when you get a derangement. The chance of that is essentially $frac 1e$
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
answered Dec 11 '14 at 1:58
Ross MillikanRoss Millikan
296k23198371
296k23198371
$begingroup$
Wait, so using derangement I can say that $!n = [frac{n!}e]$? And does that mean that the expected value is $E[X]=frac{!n}{n!}$ But what would $E[X_1X_2]$ be? Like how do I determine the value for each X?
$endgroup$
– Bryyo
Dec 11 '14 at 2:35
$begingroup$
That gives you the probability that you need to draw again. $E[X_1]$ is just the probability that the first person does not draw their own name. Can you calculate that?By symmetry, $E[X_i]$ is the same for all $i$ because you can just imagine reordering the drawing. $E[X_1X_2]$ is the chance that neither of the first two drew their own name. Can you calculate that? For the last, use the linearity of expectation.
$endgroup$
– Ross Millikan
Dec 11 '14 at 4:22
$begingroup$
Wait, why would it be the probability you need to draw again if !n is the number of ways in which they don't draw their own name and thus wouldn't need to draw again? And I don't really get how to do $E[X_i]$...
$endgroup$
– Bryyo
Dec 11 '14 at 7:21
$begingroup$
as $frac 1e$ of the permutations are derangements, you draw again with chance $1-frac 1e$. When the first person draws, (we are not talking about acceptable draws, but all draws), the chance of getting his own name is $frac 1n$, so $E[X_1]=frac 1n$
$endgroup$
– Ross Millikan
Dec 11 '14 at 14:25
$begingroup$
So if $E[X_1]=frac{1}n$, what is the part of the problem that "$X_i=1$ if a person doesn't draw their name and $X_i=0$ if they do?
$endgroup$
– Bryyo
Dec 11 '14 at 18:15
|
show 2 more comments
$begingroup$
Wait, so using derangement I can say that $!n = [frac{n!}e]$? And does that mean that the expected value is $E[X]=frac{!n}{n!}$ But what would $E[X_1X_2]$ be? Like how do I determine the value for each X?
$endgroup$
– Bryyo
Dec 11 '14 at 2:35
$begingroup$
That gives you the probability that you need to draw again. $E[X_1]$ is just the probability that the first person does not draw their own name. Can you calculate that?By symmetry, $E[X_i]$ is the same for all $i$ because you can just imagine reordering the drawing. $E[X_1X_2]$ is the chance that neither of the first two drew their own name. Can you calculate that? For the last, use the linearity of expectation.
$endgroup$
– Ross Millikan
Dec 11 '14 at 4:22
$begingroup$
Wait, why would it be the probability you need to draw again if !n is the number of ways in which they don't draw their own name and thus wouldn't need to draw again? And I don't really get how to do $E[X_i]$...
$endgroup$
– Bryyo
Dec 11 '14 at 7:21
$begingroup$
as $frac 1e$ of the permutations are derangements, you draw again with chance $1-frac 1e$. When the first person draws, (we are not talking about acceptable draws, but all draws), the chance of getting his own name is $frac 1n$, so $E[X_1]=frac 1n$
$endgroup$
– Ross Millikan
Dec 11 '14 at 14:25
$begingroup$
So if $E[X_1]=frac{1}n$, what is the part of the problem that "$X_i=1$ if a person doesn't draw their name and $X_i=0$ if they do?
$endgroup$
– Bryyo
Dec 11 '14 at 18:15
$begingroup$
Wait, so using derangement I can say that $!n = [frac{n!}e]$? And does that mean that the expected value is $E[X]=frac{!n}{n!}$ But what would $E[X_1X_2]$ be? Like how do I determine the value for each X?
$endgroup$
– Bryyo
Dec 11 '14 at 2:35
$begingroup$
Wait, so using derangement I can say that $!n = [frac{n!}e]$? And does that mean that the expected value is $E[X]=frac{!n}{n!}$ But what would $E[X_1X_2]$ be? Like how do I determine the value for each X?
$endgroup$
– Bryyo
Dec 11 '14 at 2:35
$begingroup$
That gives you the probability that you need to draw again. $E[X_1]$ is just the probability that the first person does not draw their own name. Can you calculate that?By symmetry, $E[X_i]$ is the same for all $i$ because you can just imagine reordering the drawing. $E[X_1X_2]$ is the chance that neither of the first two drew their own name. Can you calculate that? For the last, use the linearity of expectation.
$endgroup$
– Ross Millikan
Dec 11 '14 at 4:22
$begingroup$
That gives you the probability that you need to draw again. $E[X_1]$ is just the probability that the first person does not draw their own name. Can you calculate that?By symmetry, $E[X_i]$ is the same for all $i$ because you can just imagine reordering the drawing. $E[X_1X_2]$ is the chance that neither of the first two drew their own name. Can you calculate that? For the last, use the linearity of expectation.
$endgroup$
– Ross Millikan
Dec 11 '14 at 4:22
$begingroup$
Wait, why would it be the probability you need to draw again if !n is the number of ways in which they don't draw their own name and thus wouldn't need to draw again? And I don't really get how to do $E[X_i]$...
$endgroup$
– Bryyo
Dec 11 '14 at 7:21
$begingroup$
Wait, why would it be the probability you need to draw again if !n is the number of ways in which they don't draw their own name and thus wouldn't need to draw again? And I don't really get how to do $E[X_i]$...
$endgroup$
– Bryyo
Dec 11 '14 at 7:21
$begingroup$
as $frac 1e$ of the permutations are derangements, you draw again with chance $1-frac 1e$. When the first person draws, (we are not talking about acceptable draws, but all draws), the chance of getting his own name is $frac 1n$, so $E[X_1]=frac 1n$
$endgroup$
– Ross Millikan
Dec 11 '14 at 14:25
$begingroup$
as $frac 1e$ of the permutations are derangements, you draw again with chance $1-frac 1e$. When the first person draws, (we are not talking about acceptable draws, but all draws), the chance of getting his own name is $frac 1n$, so $E[X_1]=frac 1n$
$endgroup$
– Ross Millikan
Dec 11 '14 at 14:25
$begingroup$
So if $E[X_1]=frac{1}n$, what is the part of the problem that "$X_i=1$ if a person doesn't draw their name and $X_i=0$ if they do?
$endgroup$
– Bryyo
Dec 11 '14 at 18:15
$begingroup$
So if $E[X_1]=frac{1}n$, what is the part of the problem that "$X_i=1$ if a person doesn't draw their name and $X_i=0$ if they do?
$endgroup$
– Bryyo
Dec 11 '14 at 18:15
|
show 2 more comments
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%2f1061787%2fsecret-santa-probability-question%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
$begingroup$
omg 1/e i watched it in a video
$endgroup$
– Saketh Malyala
Jan 5 '18 at 17:45