Everyone's favorite part of Laundry day

I've never been the best with combinatorics, but I could always at least get by. I thought of a problem that has really sparked an interest with me, though.

(I will start with a specific example, then move on to generalize)

Say you are doing laundry and get to the part where you are matching socks. Assume that you have 4 pairs of white socks, 3 pairs of black socks, 2 pairs of red socks, and 1 pair of yellow socks. You proceed to match socks in the following way:

You start with all of the socks in a basket (and every sock has a matching pair!). You randomly pull the first sock out and lay it in front of you. One at a time, you randomly pull each sock from the basket and do one of two things. If there is no sock laying in front of you that matches that sock, you also lay it in front of you. However, if there is a sock laying in front of you that matches it, you put those two together and put them away into your drawer. (Here, we assume that any two white socks will match each other, any two black sock will match each other, etc.)

What is the expected value of the largest number of socks you will have in front of you throughout this entire process?

To generalize, say we have $a_1$ pairs of socks of the first color, $a_2$ pairs of socks of the second color, up to $a_n$ pairs of socks of the $n$ th color, and you match your socks by the same method described above. What is the expected value of the largest number of socks you will have laying in front of you for this process? Is there a general method to determine this expected value?

I have attempted this question myself, but find my mediocrity within the subject of Combinatorics to prove to strong for me to work with more than 3 different colors of socks. Any help?

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Thanks for sharing! I've found that some of my favorite combinatorics and expected value problems come from pondering situations like this...

I haven't worked it out, but here's a framework that I suspect will help:

Think of all $\sum a_i$ socks laid out in a row (this is just one of the random permutations of the socks)
Let $X_k$ be the number of unpaired socks after the $k$ th sock has been pulled
Note that $X_k$ is the number of colors which appear an odd number of times in socks $1,2,\ldots,k$

You could use this framework to construct a probability function for $X_k.$ In other words, for all $k,$ what is the probability that $X_k = 0,1,2,\ldots, n$ ? (It can't exceed $n$ since you can't have more than 1 unpaired sock per color.)

However, you are looking for the expected value of the maximum $X_k.$ This gets a bit trickier because the $X_k$ aren't independent, so having their individual distributions won't get you directly to the EV of the maximum $X_k.$

That being said... I think this general framework is still probably useful. After $k$ socks, there is some subset of colors $C$ which are unpaired, so $X_k = |C|.$ Then, after $k+1$ socks, $X_{k+1} = X_{k} - 1$ if the color of the $k+1$ sock was in $C$ and $X_{k+1} = X_{k} + 1$ otherwise. Maybe stringing together the $X_k$ in this way will give better insights into the distribution of the maximum value.

Anyone have ideas for next steps or an alternate approach? :)

Eli Ross Staff - 5 years, 1 month ago

Another approach (that I started, but didn't get to work too much with) would be writing a recursion for each case. Like, writing the number of situations of sock size $n$ with largest size $k$ as a function of situations of smaller socks and other largest sizes. Again, I need to find time to actually work out with that kind of calculation.

Anthony Kirckof - 5 years, 1 month ago

I think, the largest value would be n, in case the first n socks chosen are all different by color.Indeed, it's a very rare case, but the number of socks laying in front of you can't be more than n, because the (n+1)'st sock's color would mach one from the others(Dirchlet's theorem)

Imi Mali - 5 years, 1 month ago

While that is true, my question is asking what the expected value for the largest number is. That is, over all possible orders of choosing socks, what is the average of each "largest number" in each case.

that's indeed a more difficult question to answer

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$