Mixing
Expected Number of Single Socks when Matching Socks
$begingroup$
Whenever I go through the big pile of socks that just went through the laundry, and have to find the matching pairs, I usually do this like I am a simple automaton:
I randomly pick a sock, and see if it matches any of the single socks I picked out earlier and that haven't found a match yet. If there is a match, I will fold the two socks together and put them in the 'done' pile, otherwise I will add the single sock to the 'no match yet' pile of single socks, and pick out another random sock.
So, as I was doing this last night, I started thinking about this, and figured that the following would be true: The 'no match yet' pile can be expected to slowly grow, up to some point somewhere in the 'middle' of the process, after which the pile will gradually shrink, and eventually go down back to $0$. In fact, my intuition is that the expected number of loose socks as a function of the number of socks picked so far, is a symmetric function, with the maximum being when I have picked half of the socks.
So, my questions are:
With $n$ pairs of socks, what is the expected number of loose socks that are in my 'no match yet' pile after having picked $k$ socks?
Is it true that this function is a symmetric function, and that the maximum is for $k=n$? (if so, I figure there must be a conceptual way of looking at the problem that makes this immediately clear, without using any formulas ... what is that way? Is it just that I can think of reversing the process?)
Of course, this is all assuming there are $n$ pairs of socks total, and that there are no single socks in the original pile, and while this is something that never seems to apply to the pile of socks coming through my actual laundry, let's assume for the sake of mathematical simplicity that there really just are $n$ pairs of socks.
probability
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
$endgroup$
|
show 5 more comments
$begingroup$
Whenever I go through the big pile of socks that just went through the laundry, and have to find the matching pairs, I usually do this like I am a simple automaton:
I randomly pick a sock, and see if it matches any of the single socks I picked out earlier and that haven't found a match yet. If there is a match, I will fold the two socks together and put them in the 'done' pile, otherwise I will add the single sock to the 'no match yet' pile of single socks, and pick out another random sock.
So, as I was doing this last night, I started thinking about this, and figured that the following would be true: The 'no match yet' pile can be expected to slowly grow, up to some point somewhere in the 'middle' of the process, after which the pile will gradually shrink, and eventually go down back to $0$. In fact, my intuition is that the expected number of loose socks as a function of the number of socks picked so far, is a symmetric function, with the maximum being when I have picked half of the socks.
So, my questions are:
With $n$ pairs of socks, what is the expected number of loose socks that are in my 'no match yet' pile after having picked $k$ socks?
Is it true that this function is a symmetric function, and that the maximum is for $k=n$? (if so, I figure there must be a conceptual way of looking at the problem that makes this immediately clear, without using any formulas ... what is that way? Is it just that I can think of reversing the process?)
Of course, this is all assuming there are $n$ pairs of socks total, and that there are no single socks in the original pile, and while this is something that never seems to apply to the pile of socks coming through my actual laundry, let's assume for the sake of mathematical simplicity that there really just are $n$ pairs of socks.
probability
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
$endgroup$
1
$begingroup$
See also this question.
$endgroup$
– John Bentin
Jul 6 '17 at 20:30
2
$begingroup$
Zero for me, I use sock locks
$endgroup$
– Barmar
Jul 6 '17 at 22:35
3
$begingroup$
If the number of socks is large, I arrange the unpaired socks in buckets (based on color and/or pattern type) as I go. Also, don't miss the sibling question in SO: stackoverflow.com/questions/14415881/…
$endgroup$
– Klas Lindbäck
Jul 7 '17 at 11:20
$begingroup$
Do you have more than one pair of the same kind of socks? :) In that case, there will be a higher probability that you find a match each time you pick a new sock and the expected number of socks in the 'no match yet' pile will be lower that if there is only one pair of each kind of socks.
$endgroup$
– HelloGoodbye
Jul 7 '17 at 15:33
2
$begingroup$
It is a well known fact that socks are not subject to the conventional rules of mathematics :)
$endgroup$
– Chris Johns
Jul 7 '17 at 17:51
|
show 5 more comments
$begingroup$
Whenever I go through the big pile of socks that just went through the laundry, and have to find the matching pairs, I usually do this like I am a simple automaton:
I randomly pick a sock, and see if it matches any of the single socks I picked out earlier and that haven't found a match yet. If there is a match, I will fold the two socks together and put them in the 'done' pile, otherwise I will add the single sock to the 'no match yet' pile of single socks, and pick out another random sock.
So, as I was doing this last night, I started thinking about this, and figured that the following would be true: The 'no match yet' pile can be expected to slowly grow, up to some point somewhere in the 'middle' of the process, after which the pile will gradually shrink, and eventually go down back to $0$. In fact, my intuition is that the expected number of loose socks as a function of the number of socks picked so far, is a symmetric function, with the maximum being when I have picked half of the socks.
So, my questions are:
With $n$ pairs of socks, what is the expected number of loose socks that are in my 'no match yet' pile after having picked $k$ socks?
Is it true that this function is a symmetric function, and that the maximum is for $k=n$? (if so, I figure there must be a conceptual way of looking at the problem that makes this immediately clear, without using any formulas ... what is that way? Is it just that I can think of reversing the process?)
Of course, this is all assuming there are $n$ pairs of socks total, and that there are no single socks in the original pile, and while this is something that never seems to apply to the pile of socks coming through my actual laundry, let's assume for the sake of mathematical simplicity that there really just are $n$ pairs of socks.
probability
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
$endgroup$
Whenever I go through the big pile of socks that just went through the laundry, and have to find the matching pairs, I usually do this like I am a simple automaton:
I randomly pick a sock, and see if it matches any of the single socks I picked out earlier and that haven't found a match yet. If there is a match, I will fold the two socks together and put them in the 'done' pile, otherwise I will add the single sock to the 'no match yet' pile of single socks, and pick out another random sock.
So, as I was doing this last night, I started thinking about this, and figured that the following would be true: The 'no match yet' pile can be expected to slowly grow, up to some point somewhere in the 'middle' of the process, after which the pile will gradually shrink, and eventually go down back to $0$. In fact, my intuition is that the expected number of loose socks as a function of the number of socks picked so far, is a symmetric function, with the maximum being when I have picked half of the socks.
So, my questions are:
With $n$ pairs of socks, what is the expected number of loose socks that are in my 'no match yet' pile after having picked $k$ socks?
Is it true that this function is a symmetric function, and that the maximum is for $k=n$? (if so, I figure there must be a conceptual way of looking at the problem that makes this immediately clear, without using any formulas ... what is that way? Is it just that I can think of reversing the process?)
Of course, this is all assuming there are $n$ pairs of socks total, and that there are no single socks in the original pile, and while this is something that never seems to apply to the pile of socks coming through my actual laundry, let's assume for the sake of mathematical simplicity that there really just are $n$ pairs of socks.
probability
probability
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
asked Jul 6 '17 at 19:29
Bram28Bram28
60.6k44590
60.6k44590
1
$begingroup$
See also this question.
$endgroup$
– John Bentin
Jul 6 '17 at 20:30
2
$begingroup$
Zero for me, I use sock locks
$endgroup$
– Barmar
Jul 6 '17 at 22:35
3
$begingroup$
If the number of socks is large, I arrange the unpaired socks in buckets (based on color and/or pattern type) as I go. Also, don't miss the sibling question in SO: stackoverflow.com/questions/14415881/…
$endgroup$
– Klas Lindbäck
Jul 7 '17 at 11:20
$begingroup$
Do you have more than one pair of the same kind of socks? :) In that case, there will be a higher probability that you find a match each time you pick a new sock and the expected number of socks in the 'no match yet' pile will be lower that if there is only one pair of each kind of socks.
$endgroup$
– HelloGoodbye
Jul 7 '17 at 15:33
2
$begingroup$
It is a well known fact that socks are not subject to the conventional rules of mathematics :)
$endgroup$
– Chris Johns
Jul 7 '17 at 17:51
|
show 5 more comments
1
$begingroup$
See also this question.
$endgroup$
– John Bentin
Jul 6 '17 at 20:30
2
$begingroup$
Zero for me, I use sock locks
$endgroup$
– Barmar
Jul 6 '17 at 22:35
3
$begingroup$
If the number of socks is large, I arrange the unpaired socks in buckets (based on color and/or pattern type) as I go. Also, don't miss the sibling question in SO: stackoverflow.com/questions/14415881/…
$endgroup$
– Klas Lindbäck
Jul 7 '17 at 11:20
$begingroup$
Do you have more than one pair of the same kind of socks? :) In that case, there will be a higher probability that you find a match each time you pick a new sock and the expected number of socks in the 'no match yet' pile will be lower that if there is only one pair of each kind of socks.
$endgroup$
– HelloGoodbye
Jul 7 '17 at 15:33
2
$begingroup$
It is a well known fact that socks are not subject to the conventional rules of mathematics :)
$endgroup$
– Chris Johns
Jul 7 '17 at 17:51
1
1
$begingroup$
See also this question.
$endgroup$
– John Bentin
Jul 6 '17 at 20:30
$begingroup$
See also this question.
$endgroup$
– John Bentin
Jul 6 '17 at 20:30
2
2
$begingroup$
Zero for me, I use sock locks
$endgroup$
– Barmar
Jul 6 '17 at 22:35
$begingroup$
Zero for me, I use sock locks
$endgroup$
– Barmar
Jul 6 '17 at 22:35
3
3
$begingroup$
If the number of socks is large, I arrange the unpaired socks in buckets (based on color and/or pattern type) as I go. Also, don't miss the sibling question in SO: stackoverflow.com/questions/14415881/…
$endgroup$
– Klas Lindbäck
Jul 7 '17 at 11:20
$begingroup$
If the number of socks is large, I arrange the unpaired socks in buckets (based on color and/or pattern type) as I go. Also, don't miss the sibling question in SO: stackoverflow.com/questions/14415881/…
$endgroup$
– Klas Lindbäck
Jul 7 '17 at 11:20
$begingroup$
Do you have more than one pair of the same kind of socks? :) In that case, there will be a higher probability that you find a match each time you pick a new sock and the expected number of socks in the 'no match yet' pile will be lower that if there is only one pair of each kind of socks.
$endgroup$
– HelloGoodbye
Jul 7 '17 at 15:33
$begingroup$
Do you have more than one pair of the same kind of socks? :) In that case, there will be a higher probability that you find a match each time you pick a new sock and the expected number of socks in the 'no match yet' pile will be lower that if there is only one pair of each kind of socks.
$endgroup$
– HelloGoodbye
Jul 7 '17 at 15:33
2
2
$begingroup$
It is a well known fact that socks are not subject to the conventional rules of mathematics :)
$endgroup$
– Chris Johns
Jul 7 '17 at 17:51
$begingroup$
It is a well known fact that socks are not subject to the conventional rules of mathematics :)
$endgroup$
– Chris Johns
Jul 7 '17 at 17:51
|
show 5 more comments
3 Answers
3
active
oldest
votes
$begingroup$
The expected number can be computed via Linearity of Expectation. Let $E[n,k]$ denote the answer and let ${X_i}_{i=1}^n$ denote the indicator variable for the $i^{th}$ pair. Thus $X_i=1$ if exactly one member of the $i^{th}$ pair has been chosen in your $k$ trials, and $X_i=0$ otherwise. It is easy to see that $$E[X_i]=2times frac k{2n}times left(1-frac {k-1}{2n-1}right)$$ from which it follows that $$E[n,k]=Eleft[sum X_iright] =sum E[X_i]= ktimes left(1-frac {k-1}{2n-1}right)$$
Sanity check: $k=1implies E[n,1]=1$ as it should. Also $k=2nimplies E[n,2n]=0$ as it should.
Remark: it is easily seen that this function is maximized with $k=n$, confirming your intuition. Also the expression can be written as $$E[n,k]=frac {k(2n-k)}{2n-1}$$ which is symmetric under the exchange of $k,2n - k$ also in line with your expectations.
Remark: more strongly, it is clear that at any time the number of unmatched socks in one pile is the same as the number in the other pile (indeed it's exactly the same pairs of socks which are split between the piles). That provides clear justification for the symmetry.
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
$endgroup$
1
$begingroup$
But here's the real test: if n is the number of pairs, and k is how many socks you've picked, the expectation for the number of unmatched socks as k->2n must be non-zero in order to fit experimental data. Any model which presumes that all socks are matched by the time k=2n is clearly not an accurate model of reality!
$endgroup$
– Cort Ammon
Jul 7 '17 at 19:36
$begingroup$
@CortAmmon true, with the standing counterexample for color blind sorters or other individuals who have enjoy a non-standard notion of "match".
$endgroup$
– lulu
Jul 7 '17 at 19:41
add a comment |
$begingroup$
We can verify the accepted answer using the methodology from this MSE
link where we see
that the problem is very similar to a coupon collector without
replacement and two instances of $n$ types of coupons. Suppose we have
$j$ instances. Start by asking about the probability of getting the
following distribution of coupons:
$$prod_{q=1}^n C_q^{alpha_a}$$
where $alpha_q$ says we have that many instances of type $q$ and is
at most $j.$ We get from first principles the probability
$$frac{(nj-sum_{q=1}^n alpha_q)!}{(nj)!}
prod_{q=1}^n frac{j!}{(j-alpha_q)!}.$$
Now when we multiply a probability by the total number of events we get
the favorable events. Therefore the EGF for a given coupon type is
$$sum_{k=0}^j frac{j!}{(j-k)!} frac{z^k}{k!} =
sum_{k=0}^j {jchoose k} z^k = (1+z)^j.$$
With $j=2$ and $n$ types of coupons we get
$$m! [z^m] (1+z)^{2n}$$
and asking for the total count after $m$ coupons have been drawn yields
$$m! times {2nchoose m}.$$
Placing a marker on the singletons we find
$$m! [z^m] left.frac{partial}{partial u} (1+2uz+z^2)^nright|_{u=1}
\ = m! [z^m] ; left. n times
(1+2uz+z^2)^{n-1} times 2z right|_{u=1}
\ = m! [z^m ] 2nz (1+z)^{2n-2}
\ = m! times 2n {2n-2choose m-1}.$$
Divide to get the expectation
$$ {2nchoose m}^{-1} 2n {2n-2choose m-1}
= 2n frac{m! times (2n-m)!}{(2n)!}
frac{(2n-2)!}{(m-1)! times (2n-m-1)!}
\ = 2n times m times (2n-m) frac{1}{(2n)(2n-1)}
\ = frac{mtimes (2n-m)}{2n-1}.$$
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
$endgroup$
add a comment |
$begingroup$
If you let your function that gives the expected number of socks in your 'no match yet' pile take $k$ and $2n-k$ as arguments, i.e.
$$f,=,f(k,,2n-k),$$
it will be symmetric. The 'no match yet' pile is just the subset of all $k$ socks that have been picked that have their matching sock among all $2n-k$ socks that have not been picked yet.
Therefore, we can make the following reinterpretation of $f$:
Out of $n$ pairs of socks, $f(a,,b)$, where $a+b=2n$, is the expected number of pairs of socks for which the two socks in the pair end up in different piles when all $2n$ socks are randomly divided into two piles of sizes $a$ and $b$, respectively.
Since the piles don't have any order, the order of the arguments to $f$, which are just the sizes of the piles, doesn't matter. Hence, $f$ is symmetric.
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
$endgroup$
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%2f2348811%2fexpected-number-of-single-socks-when-matching-socks%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The expected number can be computed via Linearity of Expectation. Let $E[n,k]$ denote the answer and let ${X_i}_{i=1}^n$ denote the indicator variable for the $i^{th}$ pair. Thus $X_i=1$ if exactly one member of the $i^{th}$ pair has been chosen in your $k$ trials, and $X_i=0$ otherwise. It is easy to see that $$E[X_i]=2times frac k{2n}times left(1-frac {k-1}{2n-1}right)$$ from which it follows that $$E[n,k]=Eleft[sum X_iright] =sum E[X_i]= ktimes left(1-frac {k-1}{2n-1}right)$$
Sanity check: $k=1implies E[n,1]=1$ as it should. Also $k=2nimplies E[n,2n]=0$ as it should.
Remark: it is easily seen that this function is maximized with $k=n$, confirming your intuition. Also the expression can be written as $$E[n,k]=frac {k(2n-k)}{2n-1}$$ which is symmetric under the exchange of $k,2n - k$ also in line with your expectations.
Remark: more strongly, it is clear that at any time the number of unmatched socks in one pile is the same as the number in the other pile (indeed it's exactly the same pairs of socks which are split between the piles). That provides clear justification for the symmetry.
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
$endgroup$
1
$begingroup$
But here's the real test: if n is the number of pairs, and k is how many socks you've picked, the expectation for the number of unmatched socks as k->2n must be non-zero in order to fit experimental data. Any model which presumes that all socks are matched by the time k=2n is clearly not an accurate model of reality!
$endgroup$
– Cort Ammon
Jul 7 '17 at 19:36
$begingroup$
@CortAmmon true, with the standing counterexample for color blind sorters or other individuals who have enjoy a non-standard notion of "match".
$endgroup$
– lulu
Jul 7 '17 at 19:41
add a comment |
$begingroup$
The expected number can be computed via Linearity of Expectation. Let $E[n,k]$ denote the answer and let ${X_i}_{i=1}^n$ denote the indicator variable for the $i^{th}$ pair. Thus $X_i=1$ if exactly one member of the $i^{th}$ pair has been chosen in your $k$ trials, and $X_i=0$ otherwise. It is easy to see that $$E[X_i]=2times frac k{2n}times left(1-frac {k-1}{2n-1}right)$$ from which it follows that $$E[n,k]=Eleft[sum X_iright] =sum E[X_i]= ktimes left(1-frac {k-1}{2n-1}right)$$
Sanity check: $k=1implies E[n,1]=1$ as it should. Also $k=2nimplies E[n,2n]=0$ as it should.
Remark: it is easily seen that this function is maximized with $k=n$, confirming your intuition. Also the expression can be written as $$E[n,k]=frac {k(2n-k)}{2n-1}$$ which is symmetric under the exchange of $k,2n - k$ also in line with your expectations.
Remark: more strongly, it is clear that at any time the number of unmatched socks in one pile is the same as the number in the other pile (indeed it's exactly the same pairs of socks which are split between the piles). That provides clear justification for the symmetry.
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
$endgroup$
1
$begingroup$
But here's the real test: if n is the number of pairs, and k is how many socks you've picked, the expectation for the number of unmatched socks as k->2n must be non-zero in order to fit experimental data. Any model which presumes that all socks are matched by the time k=2n is clearly not an accurate model of reality!
$endgroup$
– Cort Ammon
Jul 7 '17 at 19:36
$begingroup$
@CortAmmon true, with the standing counterexample for color blind sorters or other individuals who have enjoy a non-standard notion of "match".
$endgroup$
– lulu
Jul 7 '17 at 19:41
add a comment |
$begingroup$
The expected number can be computed via Linearity of Expectation. Let $E[n,k]$ denote the answer and let ${X_i}_{i=1}^n$ denote the indicator variable for the $i^{th}$ pair. Thus $X_i=1$ if exactly one member of the $i^{th}$ pair has been chosen in your $k$ trials, and $X_i=0$ otherwise. It is easy to see that $$E[X_i]=2times frac k{2n}times left(1-frac {k-1}{2n-1}right)$$ from which it follows that $$E[n,k]=Eleft[sum X_iright] =sum E[X_i]= ktimes left(1-frac {k-1}{2n-1}right)$$
Sanity check: $k=1implies E[n,1]=1$ as it should. Also $k=2nimplies E[n,2n]=0$ as it should.
Remark: it is easily seen that this function is maximized with $k=n$, confirming your intuition. Also the expression can be written as $$E[n,k]=frac {k(2n-k)}{2n-1}$$ which is symmetric under the exchange of $k,2n - k$ also in line with your expectations.
Remark: more strongly, it is clear that at any time the number of unmatched socks in one pile is the same as the number in the other pile (indeed it's exactly the same pairs of socks which are split between the piles). That provides clear justification for the symmetry.
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
$endgroup$
The expected number can be computed via Linearity of Expectation. Let $E[n,k]$ denote the answer and let ${X_i}_{i=1}^n$ denote the indicator variable for the $i^{th}$ pair. Thus $X_i=1$ if exactly one member of the $i^{th}$ pair has been chosen in your $k$ trials, and $X_i=0$ otherwise. It is easy to see that $$E[X_i]=2times frac k{2n}times left(1-frac {k-1}{2n-1}right)$$ from which it follows that $$E[n,k]=Eleft[sum X_iright] =sum E[X_i]= ktimes left(1-frac {k-1}{2n-1}right)$$
Sanity check: $k=1implies E[n,1]=1$ as it should. Also $k=2nimplies E[n,2n]=0$ as it should.
Remark: it is easily seen that this function is maximized with $k=n$, confirming your intuition. Also the expression can be written as $$E[n,k]=frac {k(2n-k)}{2n-1}$$ which is symmetric under the exchange of $k,2n - k$ also in line with your expectations.
Remark: more strongly, it is clear that at any time the number of unmatched socks in one pile is the same as the number in the other pile (indeed it's exactly the same pairs of socks which are split between the piles). That provides clear justification for the symmetry.
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
edited Jul 7 '17 at 15:43
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
answered Jul 6 '17 at 20:26
lulululu
39.7k24778
39.7k24778
1
$begingroup$
But here's the real test: if n is the number of pairs, and k is how many socks you've picked, the expectation for the number of unmatched socks as k->2n must be non-zero in order to fit experimental data. Any model which presumes that all socks are matched by the time k=2n is clearly not an accurate model of reality!
$endgroup$
– Cort Ammon
Jul 7 '17 at 19:36
$begingroup$
@CortAmmon true, with the standing counterexample for color blind sorters or other individuals who have enjoy a non-standard notion of "match".
$endgroup$
– lulu
Jul 7 '17 at 19:41
add a comment |
1
$begingroup$
But here's the real test: if n is the number of pairs, and k is how many socks you've picked, the expectation for the number of unmatched socks as k->2n must be non-zero in order to fit experimental data. Any model which presumes that all socks are matched by the time k=2n is clearly not an accurate model of reality!
$endgroup$
– Cort Ammon
Jul 7 '17 at 19:36
$begingroup$
@CortAmmon true, with the standing counterexample for color blind sorters or other individuals who have enjoy a non-standard notion of "match".
$endgroup$
– lulu
Jul 7 '17 at 19:41
1
1
$begingroup$
But here's the real test: if n is the number of pairs, and k is how many socks you've picked, the expectation for the number of unmatched socks as k->2n must be non-zero in order to fit experimental data. Any model which presumes that all socks are matched by the time k=2n is clearly not an accurate model of reality!
$endgroup$
– Cort Ammon
Jul 7 '17 at 19:36
$begingroup$
But here's the real test: if n is the number of pairs, and k is how many socks you've picked, the expectation for the number of unmatched socks as k->2n must be non-zero in order to fit experimental data. Any model which presumes that all socks are matched by the time k=2n is clearly not an accurate model of reality!
$endgroup$
– Cort Ammon
Jul 7 '17 at 19:36
$begingroup$
@CortAmmon true, with the standing counterexample for color blind sorters or other individuals who have enjoy a non-standard notion of "match".
$endgroup$
– lulu
Jul 7 '17 at 19:41
$begingroup$
@CortAmmon true, with the standing counterexample for color blind sorters or other individuals who have enjoy a non-standard notion of "match".
$endgroup$
– lulu
Jul 7 '17 at 19:41
add a comment |
$begingroup$
We can verify the accepted answer using the methodology from this MSE
link where we see
that the problem is very similar to a coupon collector without
replacement and two instances of $n$ types of coupons. Suppose we have
$j$ instances. Start by asking about the probability of getting the
following distribution of coupons:
$$prod_{q=1}^n C_q^{alpha_a}$$
where $alpha_q$ says we have that many instances of type $q$ and is
at most $j.$ We get from first principles the probability
$$frac{(nj-sum_{q=1}^n alpha_q)!}{(nj)!}
prod_{q=1}^n frac{j!}{(j-alpha_q)!}.$$
Now when we multiply a probability by the total number of events we get
the favorable events. Therefore the EGF for a given coupon type is
$$sum_{k=0}^j frac{j!}{(j-k)!} frac{z^k}{k!} =
sum_{k=0}^j {jchoose k} z^k = (1+z)^j.$$
With $j=2$ and $n$ types of coupons we get
$$m! [z^m] (1+z)^{2n}$$
and asking for the total count after $m$ coupons have been drawn yields
$$m! times {2nchoose m}.$$
Placing a marker on the singletons we find
$$m! [z^m] left.frac{partial}{partial u} (1+2uz+z^2)^nright|_{u=1}
\ = m! [z^m] ; left. n times
(1+2uz+z^2)^{n-1} times 2z right|_{u=1}
\ = m! [z^m ] 2nz (1+z)^{2n-2}
\ = m! times 2n {2n-2choose m-1}.$$
Divide to get the expectation
$$ {2nchoose m}^{-1} 2n {2n-2choose m-1}
= 2n frac{m! times (2n-m)!}{(2n)!}
frac{(2n-2)!}{(m-1)! times (2n-m-1)!}
\ = 2n times m times (2n-m) frac{1}{(2n)(2n-1)}
\ = frac{mtimes (2n-m)}{2n-1}.$$
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
$endgroup$
add a comment |
$begingroup$
We can verify the accepted answer using the methodology from this MSE
link where we see
that the problem is very similar to a coupon collector without
replacement and two instances of $n$ types of coupons. Suppose we have
$j$ instances. Start by asking about the probability of getting the
following distribution of coupons:
$$prod_{q=1}^n C_q^{alpha_a}$$
where $alpha_q$ says we have that many instances of type $q$ and is
at most $j.$ We get from first principles the probability
$$frac{(nj-sum_{q=1}^n alpha_q)!}{(nj)!}
prod_{q=1}^n frac{j!}{(j-alpha_q)!}.$$
Now when we multiply a probability by the total number of events we get
the favorable events. Therefore the EGF for a given coupon type is
$$sum_{k=0}^j frac{j!}{(j-k)!} frac{z^k}{k!} =
sum_{k=0}^j {jchoose k} z^k = (1+z)^j.$$
With $j=2$ and $n$ types of coupons we get
$$m! [z^m] (1+z)^{2n}$$
and asking for the total count after $m$ coupons have been drawn yields
$$m! times {2nchoose m}.$$
Placing a marker on the singletons we find
$$m! [z^m] left.frac{partial}{partial u} (1+2uz+z^2)^nright|_{u=1}
\ = m! [z^m] ; left. n times
(1+2uz+z^2)^{n-1} times 2z right|_{u=1}
\ = m! [z^m ] 2nz (1+z)^{2n-2}
\ = m! times 2n {2n-2choose m-1}.$$
Divide to get the expectation
$$ {2nchoose m}^{-1} 2n {2n-2choose m-1}
= 2n frac{m! times (2n-m)!}{(2n)!}
frac{(2n-2)!}{(m-1)! times (2n-m-1)!}
\ = 2n times m times (2n-m) frac{1}{(2n)(2n-1)}
\ = frac{mtimes (2n-m)}{2n-1}.$$
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
$endgroup$
add a comment |
$begingroup$
We can verify the accepted answer using the methodology from this MSE
link where we see
that the problem is very similar to a coupon collector without
replacement and two instances of $n$ types of coupons. Suppose we have
$j$ instances. Start by asking about the probability of getting the
following distribution of coupons:
$$prod_{q=1}^n C_q^{alpha_a}$$
where $alpha_q$ says we have that many instances of type $q$ and is
at most $j.$ We get from first principles the probability
$$frac{(nj-sum_{q=1}^n alpha_q)!}{(nj)!}
prod_{q=1}^n frac{j!}{(j-alpha_q)!}.$$
Now when we multiply a probability by the total number of events we get
the favorable events. Therefore the EGF for a given coupon type is
$$sum_{k=0}^j frac{j!}{(j-k)!} frac{z^k}{k!} =
sum_{k=0}^j {jchoose k} z^k = (1+z)^j.$$
With $j=2$ and $n$ types of coupons we get
$$m! [z^m] (1+z)^{2n}$$
and asking for the total count after $m$ coupons have been drawn yields
$$m! times {2nchoose m}.$$
Placing a marker on the singletons we find
$$m! [z^m] left.frac{partial}{partial u} (1+2uz+z^2)^nright|_{u=1}
\ = m! [z^m] ; left. n times
(1+2uz+z^2)^{n-1} times 2z right|_{u=1}
\ = m! [z^m ] 2nz (1+z)^{2n-2}
\ = m! times 2n {2n-2choose m-1}.$$
Divide to get the expectation
$$ {2nchoose m}^{-1} 2n {2n-2choose m-1}
= 2n frac{m! times (2n-m)!}{(2n)!}
frac{(2n-2)!}{(m-1)! times (2n-m-1)!}
\ = 2n times m times (2n-m) frac{1}{(2n)(2n-1)}
\ = frac{mtimes (2n-m)}{2n-1}.$$
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
$endgroup$
We can verify the accepted answer using the methodology from this MSE
link where we see
that the problem is very similar to a coupon collector without
replacement and two instances of $n$ types of coupons. Suppose we have
$j$ instances. Start by asking about the probability of getting the
following distribution of coupons:
$$prod_{q=1}^n C_q^{alpha_a}$$
where $alpha_q$ says we have that many instances of type $q$ and is
at most $j.$ We get from first principles the probability
$$frac{(nj-sum_{q=1}^n alpha_q)!}{(nj)!}
prod_{q=1}^n frac{j!}{(j-alpha_q)!}.$$
Now when we multiply a probability by the total number of events we get
the favorable events. Therefore the EGF for a given coupon type is
$$sum_{k=0}^j frac{j!}{(j-k)!} frac{z^k}{k!} =
sum_{k=0}^j {jchoose k} z^k = (1+z)^j.$$
With $j=2$ and $n$ types of coupons we get
$$m! [z^m] (1+z)^{2n}$$
and asking for the total count after $m$ coupons have been drawn yields
$$m! times {2nchoose m}.$$
Placing a marker on the singletons we find
$$m! [z^m] left.frac{partial}{partial u} (1+2uz+z^2)^nright|_{u=1}
\ = m! [z^m] ; left. n times
(1+2uz+z^2)^{n-1} times 2z right|_{u=1}
\ = m! [z^m ] 2nz (1+z)^{2n-2}
\ = m! times 2n {2n-2choose m-1}.$$
Divide to get the expectation
$$ {2nchoose m}^{-1} 2n {2n-2choose m-1}
= 2n frac{m! times (2n-m)!}{(2n)!}
frac{(2n-2)!}{(m-1)! times (2n-m-1)!}
\ = 2n times m times (2n-m) frac{1}{(2n)(2n-1)}
\ = frac{mtimes (2n-m)}{2n-1}.$$
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
answered Jul 6 '17 at 23:50
Marko RiedelMarko Riedel
39.4k339108
39.4k339108
add a comment |
add a comment |
$begingroup$
If you let your function that gives the expected number of socks in your 'no match yet' pile take $k$ and $2n-k$ as arguments, i.e.
$$f,=,f(k,,2n-k),$$
it will be symmetric. The 'no match yet' pile is just the subset of all $k$ socks that have been picked that have their matching sock among all $2n-k$ socks that have not been picked yet.
Therefore, we can make the following reinterpretation of $f$:
Out of $n$ pairs of socks, $f(a,,b)$, where $a+b=2n$, is the expected number of pairs of socks for which the two socks in the pair end up in different piles when all $2n$ socks are randomly divided into two piles of sizes $a$ and $b$, respectively.
Since the piles don't have any order, the order of the arguments to $f$, which are just the sizes of the piles, doesn't matter. Hence, $f$ is symmetric.
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
$endgroup$
add a comment |
$begingroup$
If you let your function that gives the expected number of socks in your 'no match yet' pile take $k$ and $2n-k$ as arguments, i.e.
$$f,=,f(k,,2n-k),$$
it will be symmetric. The 'no match yet' pile is just the subset of all $k$ socks that have been picked that have their matching sock among all $2n-k$ socks that have not been picked yet.
Therefore, we can make the following reinterpretation of $f$:
Out of $n$ pairs of socks, $f(a,,b)$, where $a+b=2n$, is the expected number of pairs of socks for which the two socks in the pair end up in different piles when all $2n$ socks are randomly divided into two piles of sizes $a$ and $b$, respectively.
Since the piles don't have any order, the order of the arguments to $f$, which are just the sizes of the piles, doesn't matter. Hence, $f$ is symmetric.
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
$endgroup$
add a comment |
$begingroup$
If you let your function that gives the expected number of socks in your 'no match yet' pile take $k$ and $2n-k$ as arguments, i.e.
$$f,=,f(k,,2n-k),$$
it will be symmetric. The 'no match yet' pile is just the subset of all $k$ socks that have been picked that have their matching sock among all $2n-k$ socks that have not been picked yet.
Therefore, we can make the following reinterpretation of $f$:
Out of $n$ pairs of socks, $f(a,,b)$, where $a+b=2n$, is the expected number of pairs of socks for which the two socks in the pair end up in different piles when all $2n$ socks are randomly divided into two piles of sizes $a$ and $b$, respectively.
Since the piles don't have any order, the order of the arguments to $f$, which are just the sizes of the piles, doesn't matter. Hence, $f$ is symmetric.
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
$endgroup$
If you let your function that gives the expected number of socks in your 'no match yet' pile take $k$ and $2n-k$ as arguments, i.e.
$$f,=,f(k,,2n-k),$$
it will be symmetric. The 'no match yet' pile is just the subset of all $k$ socks that have been picked that have their matching sock among all $2n-k$ socks that have not been picked yet.
Therefore, we can make the following reinterpretation of $f$:
Out of $n$ pairs of socks, $f(a,,b)$, where $a+b=2n$, is the expected number of pairs of socks for which the two socks in the pair end up in different piles when all $2n$ socks are randomly divided into two piles of sizes $a$ and $b$, respectively.
Since the piles don't have any order, the order of the arguments to $f$, which are just the sizes of the piles, doesn't matter. Hence, $f$ is symmetric.
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
answered Jul 7 '17 at 16:21
HelloGoodbyeHelloGoodbye
1905
1905
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.
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%2f2348811%2fexpected-number-of-single-socks-when-matching-socks%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$
See also this question.
$endgroup$
– John Bentin
Jul 6 '17 at 20:30
2
$begingroup$
Zero for me, I use sock locks
$endgroup$
– Barmar
Jul 6 '17 at 22:35
3
$begingroup$
If the number of socks is large, I arrange the unpaired socks in buckets (based on color and/or pattern type) as I go. Also, don't miss the sibling question in SO: stackoverflow.com/questions/14415881/…
$endgroup$
– Klas Lindbäck
Jul 7 '17 at 11:20
$begingroup$
Do you have more than one pair of the same kind of socks? :) In that case, there will be a higher probability that you find a match each time you pick a new sock and the expected number of socks in the 'no match yet' pile will be lower that if there is only one pair of each kind of socks.
$endgroup$
– HelloGoodbye
Jul 7 '17 at 15:33
2
$begingroup$
It is a well known fact that socks are not subject to the conventional rules of mathematics :)
$endgroup$
– Chris Johns
Jul 7 '17 at 17:51