3
$\begingroup$

Recently I was putting some socks on the clothing line after taking them from the laundry machine and I while I was doing that I came up with an interesting math problem.

I usually wash $30$ or so socks (amounting for $15$ or so pairs) and then I start putting them on clothing lines. On one clothing line I can put at most $8$ socks. Here's my method of ordering: I pick a random sock and I put it on the first line, in the same time "reserving" the place after it for it's partner. Next I pick another random sock and if it's partner is already on one of the lines I just put it in the already reserved place, otherwise I put it in the next free place. First I tend to use all the free space on the first line, then on the second and so on. For example if I have something like $x-x-x-x-$ on the first line (where $x$ is a slot filled with a sock and $-$ is an empty slot, reserved for the partner of the sock ahead of it) and I pick up a new sock from the basket then I will put it on the second line and so on.

Once while doing this I started wondering: what is the probability of filling the first line with $8$ socks before any other line is filled? What about the second line being filled first, and so on? Unfortunately I haven't been able to get anywhere close to a solution. In order to avoid inconvenience I assume I have $8n$ socks, where $n$ is the number of clothing line. My idea was to number the pairs and shuffle the $8n$ numbers, order them in a line and then look at the probability of the first four distinct numbers finding their partner before any other set of four doing it, as we go along the line of shuffled numbers. Unfortunately things start to get complicated and I can't achieve anything.

I even thought of calculating the probability of the first line NOT filling first. I set the position of the last sock from the first line to be $n$ and then I try to find all combinations of putting $4$ other pairs between the first and $n-$th place. But the calculation of this number isn't easy and I'm afraid of double counting.

Anyway I wrote a computer program and here's what I've got for which number will be filled first for $32$ socks and $4$ lines, running it three times for various amounts of tries:

$$ \begin{array}{c|lcr} Line & \text{#1} & \text{#2} & \text{#3} \\ \hline 1 & 4168 & 8388 & 21041 \\ 2 & 3281 & 6394 & 16634 \\ 3 & 2077 & 4243 & 10735 \\ 4 & 469 & 984 & 2632 \\ \hline Total & 9995 & 20009 & 51042 \end{array} $$

$\endgroup$
  • $\begingroup$ I'd start by thinking about the problem when there are $n$ lines and just one pair of socks fits on each line. Then the probability of finishing the first line before starting the second is the probability of matching the first pick with the second. That's just $1/(n-1)$. Can you figure out the probability of filling the first $2$ lines? The first $k$ lines? Then graduate to two pair of socks per line ... $\endgroup$ – Ethan Bolker Sep 30 '17 at 15:19
  • $\begingroup$ Two comments: (1) It's "clothesline," not "clothing line." (2) I don't get the distinction between "times" and "tries" in your table. What do you gain by keeping your data in three distinct columns? $\endgroup$ – Fabio Somenzi Sep 30 '17 at 15:52
  • $\begingroup$ @FabioSomenzi First I generated $9995$ random sequence and in $4165$ the first line was filled first. This is the first column. Afterwards I did it for $20009$ random sequence and finally I generated $51042$ random sequences. $\endgroup$ – Stefan4024 Sep 30 '17 at 16:10
0
$\begingroup$

EDIT: As pointed out in the comments, this solution is flawed.

Let $l$ be the number of lines, and let $s$ be the number of pairs of socks allowed in a line (in the case of the question, 8), and let $p$ be the number of socks in a pair (in this case 2). So, we should have $lsp$ socks.

Let $P_l$ denote the probability that line 1 gets finished first (in theory this method can be generalized to find the probability that the $n$th line gets finished first, but it becomes messier). I will describe a way to calculate $P_l$ recursively (note that this is probably not the best way; see my comment to this answer. However, this method is feasible and I would calculate it in your case if I did not have to leave soon; I will come back to this.).

$P_1=1$.

For larger values of $l$, we may use the principle of inclusion exclusion as follows:

\begin{align*} &P(\textrm{first line finishes before at least one other line})\\ &=\sum_{S\subseteq\{2,3,\dots,n\}}(-1)^{\lvert S\rvert+1}P(\textrm{first line finishes before all lines in } S)\\ &=\sum_{S\subseteq\{2,3,\dots,n\}}(-1)^{\lvert S\rvert+1}P_{\lvert S\rvert+1}\\ &= \sum_{i=1}^{n-1}\binom{n-1}{i}(-1)^{i+1}P_{l+1}. \end{align*}

(To get from the second line to the third line, interpret $i$ as $\lvert S\rvert$, so while the second line sums overt all sets, the third line sums over all possible sizes of the sets. The factor of $\binom{n-1}{i}$ counts the number of sets of size $i$.)

If we rearrange, we can get $P_l$ in terms of lower values of $P_l$ and the probability that the first line finishes before at least one other line.

To calculate the probability that the first line finishes before at least one other line, take 1 minus the probability that the first line finishes last. This is the probability that the last sock comes from one of the first $s$ pairs. This is equal to the probability that the last sock comes from the first pair, plus the probability that it comes from the second pair, plus... plus the probability that it comes from the $s$th pair.

To calculate the probability that the last sock comes from the $k$th pair, this is equal to the probability that the last sock does not come from the first $k-1$ pairs multiplied by the probability that it comes from the $k$-th pair given that it does not come from the $k$-th pair.

To calculate this, it is enough to calculate the probability that the last sock comes from the first pair where there are an arbitrary number of pairs. This is easy, because there are $ps-1$ socks that could be the last and there are $p-1$ remaining socks from the first pair (after the first one), so this probability is $\frac{p-1}{ps-1}$.

$\endgroup$
  • $\begingroup$ There is probably a better way to do this because if only 2 socks were allowed on a line with 2 socks per pair and there are $l$ lines, then the probability the first line finishes first is $\frac{(2l-2)!!}{(2l-1)!!}$ (where !! is double factorial, not factorial applied twice), at least for the first few terms. $\endgroup$ – alphacapture Sep 30 '17 at 17:56
  • $\begingroup$ Two quick questions. First, in the first equation of your probability calculation, should $(-1)^{|S|}$ be negated? Second, in your transition from line 2 to line 3, you assert that the probability of the first line completing before the lines in $S$ depends solely on $|S|$; can you please explain more thoroughly? If the socks were pre-ordered to go on a specific line independent of draw order, this would be obvious. But in this instance, it seems more intuitive that the probability of filling the first before the last is higher than the first finishing before the second. $\endgroup$ – Jeremy Dover Oct 1 '17 at 0:49
  • $\begingroup$ @JeremyDover Both objections are correct; The first one is minor, but the second one is a major problem. I think it can be fixed if we take the sum over something other than the lines, but I think I have a nonrecursive approach to the problem so I'll write that one up before fixing this one (if possible) $\endgroup$ – alphacapture Oct 1 '17 at 1:08
0
$\begingroup$

EDIT: This solution is also wrong.

This solution generalizes to an arbitrary number of lines, pairs per line, and socks per pair. But the amount of work required increases dramatically as socks per pair goes up, unless we can find a way to get rid of the casework.

Given a random permutation of the socks, name the socks $1_1,1_2,2_1,2_1,3_1,3_2,4_1,4_2,L_{1,1},L_{1,2}\dots,L_{1,7},E_1,L_{2,1},L_{2,2}\dots,L_{2,7},E_2,\dots,E_{\frac{n}{4}-1}$ (where $n$ is the number of pairs) as follows: Say that the first 4 pairs that get introduced are pair $1$, $2$, $3$, and $4$ (so they make up the first line). $1_1$ is then the first sock that gets introduced, and $1_2$ is the other sock in its pair, and the same for $2$, $3$, and $4$.

Now let $E_1$ be the last sock that gets put up on the first line to finish that is not the first line (regardless of whether the first line finishes first or not), $E_2$ the last sock that gets put up on the second line to finish that is not the first line, etc. Finally, label the rest of the socks from the first line to finish that is not the first line $L_{1,1}$ to $L_{1,7}$ randomly, and do a similar thing for the rest of the lines.

Example (order generated by http://www.jerrydallal.com/random/random_permutation.htm):

If the socks come in the following order (where two socks are in the same pair if they have the same letter)

lhcdiidjeaelkfcfakbgghbj

becomes

$1_12_13_14_1L_{2,2}L_{2,4}4_2L_{2,5}L_{2,7}L_{2,3}L_{2,6}1_2L_{1,5}L_{1,3}3_2L_{1,4}L_{2,1}L_{1,2}L_{1,7}L_{1,1}L_{1,6}2_2E_1E_2$

(In general, $E_1$ will not be the second last, but $E_{\frac{n}{4}-1}$ will be the last unless one of the socks from one of the first 4 pairs is the last.)

The first line is the first line to be finished if and only if $1_2,2_2,3_2,$ and $4_2$ all occur before $E_1$ (and hence before $E_2$, etc. as well).

All possible resulting permutations of $1_1,\dots,E_{\frac{n}{4}-1}$ are equally likely because they all come from the same number of permutations of the socks. (EDIT: The flaw is here; they are not equally likely. It is difficult to put in words how though.)

So, to calculate the probability that the first line finishes first, we will calculate the number of possible permutations where $1_2,2_2,3_2,4_2$ all come before $E_1$, and then divide by the number of possible permutations.

To calculate the number of possible permutations:

Any possible permutation has the following structure:

Take $1_1,2_1,3_1,4_1,E_1,E_2,\dots,E_{\frac{n}{4}-1}$ and then add the rest of them. $1_2$ comes after $1_1$, and the same for $2,3,$ and $4$. $L_{i,j}$ must come before $E_i$ and after $4_1$ (and hence after $1_1,2_1,3_1$ as well).

To count this: start by adding the $L_{1,j}$ one at a time, then the $L_{2,j}$ one at a time, etc. and then add $4_2,$ then $3_2$, then $2_2$, then $1_2$.

For the $L_{i,j}$, there are

\begin{align*} &1*2*\dots*7*9*10*\dots*15*17\dots*2n-9\\ &=\frac{(2n-8)!}{8*16*\dots*(2n-8)}\\ &=\frac{(1)_{2n-8,1}}{(8)_{\frac{n}{4}-1,8}} \end{align*}

ways where $(x)_{n,k}$ is the Pockhammer k-symbol (I'm using this symbol because we're going to see a lot of sums like this later). There are then $2n-7$ places to put $4_2$, $2n-5$ places to put $3_2$, $2n-3$ places to put $2_2$, and $2n-1$ places to put $1_2$. So in total there are

$$\frac{(1)_{2n-8,1}(2n-7)(2n-5)(2n-3)(2n-1)}{(8)_{\frac{n}{4}-1,8}}=\frac{(1)_{2n-8,1}(2n-7)_{4,2}}{(8)_{\frac{n}{4}-1,8}}$$

possible permutations.

To calculate the number of possible permutations where the first line finishes first:

We split into 5 cases, dependent on how many of the socks from the first 4 pairs show up after $4_1$.

By direct computation, for each integer $1\le i\le4$, the number of permutations of $1_12_13_14_11_22_23_24_2$ which are possible where $i$ of them are after $4_1$ is (0 is impossible because $4_2$ comes after $4_1$):

$i=1:15$

$i=2:30$

$i=3:36$

$i=4:24$

(I did this by computer. My code is in the appendix.)

For each case, all that's left to do is place the $L_{i,j}$. In all cases, we will choose positions for the $L_{1,j}$ first, one at a time, then $L_{2,j}$, etc.

Case $i=1$:

\begin{align*} &2*3*\dots*8*10*11\dots*16*18\dots*2n-8\\ &=\frac{(2n-7)!}{9*17*\dots*(2n-7)}\\ &=\frac{(2)_{2n-8,1}}{(9)_{\frac{n}{4}-1,8}} \end{align*}

ways.

Case $i=2$:

\begin{align*} &3*4*\dots*9*11*12\dots*17*19\dots*2n-7\\ &=\frac{(2n-6)!}{10*18*\dots*(2n-6)}\\ &=\frac{(3)_{2n-8,1}}{(10)_{\frac{n}{4}-1,8}} \end{align*}

ways.

Case $i=3$:

\begin{align*} &4*5*\dots*10*12*13\dots*18*20\dots*2n-6\\ &=\frac{(2n-5)!}{11*19*\dots*(2n-5)}\\ &=\frac{(4)_{2n-8,1}}{(11)_{\frac{n}{4}-1,8}} \end{align*}

ways.

Case $i=4$:

\begin{align*} &5*6*\dots*11*13*14\dots*19*21\dots*2n-5\\ &=\frac{(2n-4)!}{12*20*\dots*(2n-4)}\\ &=\frac{(5)_{2n-8,1}}{(12)_{\frac{n}{4}-1,8}} \end{align*}

ways.

In total:

$$15*\frac{(2)_{2n-8,1}}{(9)_{\frac{n}{4}-1,8}}+30*\frac{(3)_{2n-8,1}}{(10)_{\frac{n}{4}-1,8}}+36*\frac{(4)_{2n-8,1}}{(11)_{\frac{n}{4}-1,8}}+24*\frac{(5)_{2n-8,1}}{(12)_{\frac{n}{4}-1,8}}$$

possible permutations where the first line finishes first.

Finally, our answer is:

$$\boxed{\frac{15*\frac{(2)_{2n-8,1}}{(9)_{\frac{n}{4}-1,8}}+30*\frac{(3)_{2n-8,1}}{(10)_{\frac{n}{4}-1,8}}+36*\frac{(4)_{2n-8,1}}{(11)_{\frac{n}{4}-1,8}}+24*\frac{(5)_{2n-8,1}}{(12)_{\frac{n}{4}-1,8}}}{\frac{(1)_{2n-8,1}(2n-7)_{4,2}}{(8)_{\frac{n}{4}-1,8}}}}.$$

In the case of 32 socks, by plugging into WolframAlpha, the numerator becomes 58301463783867752448000000 and the denominator becomes 122559766074795905856000000 and the exact result becomes 1323392/2781999 or about 0.476. In comparison, the asker's data gives (4168+8388+21041)/(9995+20009+51042) which is about 0.41, which suggests that, almost certainly, either I made a mistake or the asker's pseudorandom number generator has some patterns (if my answer were exact, this result is something like 35 standard deviations below the mean). Given this, I might try to calculate small exact values at some point, but I'm too tired right now.

Appendix:

import java.util.*;
import java.lang.*;

class Rextester//Needless to say, I wrote this code on Rextester
{  
    public static void main(String args[])
    {
        int[] amounts = new int[4];
        for(int i = 0; i < 105; i++) {
            int one = i%7;
            int two = (i/7)%5;
            int three = (i/35);
            ArrayList<Integer> construct = new ArrayList<Integer>();
            construct.add(1);
            construct.add(2);
            construct.add(3);
            construct.add(4);
            construct.add(5);

            construct.add(3+three,6);
            construct.add(2+two,7);
            construct.add(1+one,8);

            amounts[sort(construct)-1]++;
        }
        System.out.println(Arrays.toString(amounts));
    }

    public static int sort(ArrayList<Integer> construct){
        return 7-construct.indexOf(4);
    }
}
$\endgroup$
  • $\begingroup$ I programmed the estimator of the probabilities in Python, C++, MATLAB, and Julia. All programs substantially agree with Stefan's conclusions. I'd rule out biases in the generators. $\endgroup$ – Fabio Somenzi Oct 1 '17 at 5:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.