I have recently bought “7 Pairs of Cotton Rich Freshfeet Days of the Week Socks” from Marks & Spencer. Essentially, these are standard socks with the name of the day printed on them, from Monday to Sunday (i.e.: I have two socks marked “Monday”, two socks marked “Tuesday”, etc). They also come in different colours so that you don’t risk mixing socks from different days…
For the first week I tried to wear the correct socks for the correct day, but I immediately gave up and now I just pick a random pair from my drawer. After a few weeks I have noticed that the days in which I’m wearing the “correct” socks are a lot more than I expected (for instance, today is Monday and I have the correct pair, and last week I had the correct pair on two days of the week!). This looks like an interesting instance of the “Availability Heuristic” at work… What’s the probability of having the correct pair of socks?
Let’s simplify the problem: suppose that the week starts on Monday and all the 7 pairs of socks are available on that day. Suppose that every day you pick a random pair and you remove it from the available socks for the rest of the week (you obviously need to wash them…). What is the probability that at least once that during the week you have the right pair of socks for the correct day?
I’m going to show you 2 ways to compute this number (which is probably higher than you’d expect, and consistent with my surprise when I pick the correct pair of socks during the week):
1) The “I don’t have time to think of a solution / I hate Maths” way. Just write a simple Monte Carlo simulation and let the computer do the job. The idea is the following: start from the list (1 2 3 4 5 6 7), randomly shuffle the numbers around to obtain something like (3 4 7 2 1 6 5) (this is called a permutation and it represents the order in which you pick the socks: in this case, on Monday I pick the socks for Wednesday, on Tuesday those for Thursday, etc.), check if one of the numbers is in the right position (in this case yes: number 6 is in position 6, meaning that on Saturday I get the socks for Saturday), repeat the process N times and keep a counter of how many times the shuffled list has at least one number in the right position. At the end, just compute the ratio of this counter with respect to N. Let’s do it in Racket (obviously):
#lang racket ;; The number of days in the week (define DOW 7) ;; The total number of iterations (define N 1000000) ;; A simple function that takes a list and returns ;; True if one of the elements is in the right place (define (oneIsOK myList) ;; The ormap builds first of all a new list by ;; comparing the values of the list (1 2 ... DOW) ;; with the values of the input parameter myList, one ;; by one, thus producing a list of Boolean values. ;; It then compute the disjunction of this new list of ;; Boolean values (ormap (lambda (value1 value2) (= value1 value2)) (range 1 (+ 1 DOW)) myList)) ;; This is a simple for loop that repeats N random ;; shuffles of the list (1 2 ... DOW) and increments ;; a counter when at least one element is in the right place. (define (simulation) (define counter 0) (for ([i (range 0 N)]) (cond ( (oneIsOK (shuffle (range 1 (+ 1 DOW)))) (set! counter (+ 1 counter))) ) ) ;; at the end we just print the percentage (printf "The percentage is: ~a" (* 100.0 (/ counter N))) )
The code isn’t too difficult, check the comments above. The code runs 1 million shuffles and computes the results, which is 63% (more or less). Sixty-three percent! Wow, this means that it is more likely that in a week I have at least once the correct pair of socks! You can change the number of socks and see how this ratio changes. For instance, with 3 pairs of socks the probability is 66.6%: this is what you would expect, just check the 6 possible permutations of 3 elements.
2) The second method is the “I get a pen and a piece of paper“: let’s look again at the notion of permutation. What is needed here is to compute the number of permutations of (1 2 3 4 5 6 7) in which at least one of the elements “does not move” (more precisely, you should say “all the permutations with at least one fix-point”). One way to compute this number is to count the number of permutations in which all elements move (i.e., the number of permutations without fix-points): a permutation without fix-points is called a derangement. The notation !n is used to denote the number of derangements of n elements. Overall, we want to compute (n! – !n)/n!: this is the total number of permutations, minus the number of derangements, divided by the total number of permutations. To compute the number of derangements, observe that on Monday I can choose between 6 pairs of socks (i.e., all the ones not marked with Monday). Suppose that on Monday I get the Wednesday socks. There are now two options:
- I have a derangement in which on Wednesday I get the Monday socks. This leaves me with 5 pairs of socks to be arranged without fix-points, and there are !(n-2) ways for doing this.
- I have a derangement in which on Wednesday I do not get Monday’s socks, and there are !(n-1) ways for doing this.
Thus, there are (!(n-2)+!(n-1)) derangements in which on Monday I have the Wednesday socks. But Wednesday was just one of the possible (n-1) choices, so overall the number of derangements for n elements is:
!n = (n-1)(!(n-2) + !(n-1))
This is a nice recursive definition (just set !0=1 and !1=0), which we can compute with the following Racket code:
(define (der n) (cond ( (= n 0) 1) ( (= n 1) 0 ) (else (* (- n 1) (+ (der (- n 1)) (der (- n 2))))) ) )
With this function you can now compute the exact probability for 7 pairs of socks, which is 63.21%.
EXERCISE: compute the average number of days per week in which I wear the correct pair of socks. HINT: the solution is 1, and this is equivalent to the claim that “the average number of fix-points in a random permutation is 1“, irrespective of the size of the list…
I really like this problem and, being a lazy man, I went for the simulation. But, I first computed the total number of permutations, and found that they are only 7! = 5040, so there is no point in doing one million iterations (of course, if you buy socks associated to days of the month, that’s a different story …).
So I wrote this Prolog program (runs on SWI, but should be fairly standard):
Ratio is C/Nperm.
-> Ctemp is Cin+1
; Ctemp = Cin),
and it immediately gives R=0.6321428571428571.
Using a little bit of not-so-standard predicates, one can shorten the code to 7 lines of code:
Ratio is Nok/Nperm.
To compute the average, one can exploit aggregates:
Lin = [1,2,3,4,5,6,7],
A is Total/Nperm.
I have also considered this problem – Interestingly enoough becase I also have a set of “days of the week” socks from M&S.
Whilst the probability that you would get at least one pair of “correct” socks in a week is 63%, Can you expand on that and let us all know what the probability of getting a correct sock on any particular day is.
Or to put it another way…. Out of the 5040 permutations, how many fixed points are there?
Using the formula above, there are 1854 deragements. As a result, there are 5040-1854 permutations with at least one fix point. Does this answer the question :-)?
It sort of answers my question (Thankyou btw)
OK There are are 3186 permutations that have at least one fixed point – but that doesn’t tell me much except the probability that in a particular week I get at least 1 match.
The approach I was going to take was to count the number of fixed points in those 3186 permutations – call it F, and then divide by the number of days (5040*7) to get the probablility that on any particular day I get the right sock.
I guess I have two questions
1) Is this approach flawed? (I fully accept that I am frequently wrong)
2) Is there a smart way to calculate F, or do I need to iterate through the 5040 perms to count the fix points…..
My thanks for your replies so far, and for future replies also!
Sorry I think I misunderstood your original question! Let me rephrase it to see if I get it right now: you would like to know the probability that, say, on Monday you pick the “Monday” pair, on Tuesday the “Tuesday” pair, etc.
Let’s start from the easy and intuitive case: day 1. The probability of getting pair 1 on day 1 is 1/N (where N is the number of pairs). So this is 1/7th for M&S socks.
Consider now any other day of the week, say Thursday. You are interested in all the permutations in which the fourth element is a fix point. If N=7, when the fourth element is fixed you are left with 6!=720 possible permutations. So, again, you have that the probability that on Thursday you have the Thursday pair is 6!/7!=720/5040=1/7.
This assumes that you don’t know anything about what happened on that particular week before Thursday; you are simply answering the question “what is the probability that, in any given week, I have the “Thursday” pair on Thursday?”.
Put it in another way: suppose you repeat the process of picking up random pairs of socks for 7,000,000 weeks, starting every Monday with a fresh batch of 7 pairs. At the end of the 7,000,000 weeks you count “how many times did I get the “Thursday” pair on Thursday? The result should be more or less 1,000,000 (and the same for all the other days).
Going back to the original problem: in 63% of those 7,000,000 weeks you had at least one pair of socks in the correct day. Finally, if you add how many times per week you had the correct pair of socks and you divide it by 7,000,000, you should get 1.
I have a related question!
Lets suppose that on Monday I randomly pick a pair of socks and put them on. I do not look to see if they are Monday socks or not but I can ask my wife and she is only allowed to say ‘Yes, they are Monday socks’ or ‘No, they are not Monday socks’. The socks do not go back in the drawer so on Tuesday there are 6 pairs left. If she says ‘No, they are not Monday socks’ what are the chances of getting the correct Tuesday socks on Tuesday?