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…