A few weeks ago, I watched this video: James Randi and a Graphologist.
There were 5 ladies in the video and the graphologist was supposed to assign a profession to each lady from a given list of 5 professions. Now, there are 5! = 120 possible ways of assigning them. I tried verifying that the expected number of ladies for which the graphologist assigns the correct profession is exactly 1. I did this in a very convoluted manner using the concept of derangements. I'll describe this first and in the end, I'll provide a really simple way of verifying this using the concept of linearity of expectation.
Let us count the number of ways to assign them in which he gets exactly 1 correct and the remaining 4 incorrect. There are 5C1 ways of choosing the lady for which the assignment is correct and if we call the number of ways wrong profession is assigned to each of the remaining 4 ladies as d4, then the number of ways to assign the professions such that exactly 1 lady has been assigned the correct profession is: 5C1 ⋅ d4.
Similarly, the number of ways he can get exactly 2 correct is 5C2 ⋅ d3 where d3 is the number of ways wrong profession is assigned to each of the remaining 3 ladies. Let us denote the number of ways wrong profession can be assigned to k ladies from a list of k unique professions as dk, where 1 ≤ k ≤ 5. Now, we can say that in general, the number of ways he can get exactly k correct is 5Ck ⋅ d5-k. So, the probability p(k) that he can get exactly k correct is (5Ck ⋅ d5-k)⁄5!.
The number dk is the possible number of derangements of k elements. A derangement of a given sequence is a permutation of the elements in the sequence in which none of the elements appear in its original position. It is obvious that d1 = 0 since there is only one permutation of a sequence containing a single element and this only permutation is not a derangement. d2 = 1 since the only possible derangement of (1, 2) is (2, 1). d3 = 2 since the only possible derangements of (1, 2, 3) is (2, 3, 1) and (3, 1, 2). To calculate d4 and d5, I'll use the recurrence relation, dn = (n - 1)(dn-1 + dn-2). The recurrence relation is easy to understand. I'm including an explanation from the Wikipedia article on derangement:
Suppose that there are n persons numbered 1, 2, …, n. Let there be n hats also numbered 1, 2, …, n. We have to find the number of ways in which no one gets the hat having same number as his/her number. Let us assume that first person takes the hat i. There are n − 1 ways for first person to choose the number i. Now there are 2 options -So, d4 = 3(d3 + d2) = 3(2 + 1) = 9 and d5 = 4(d4 + d3) = 4(9 + 2) = 44.
- Person i takes the hat of 1. So Now the problem reduces to n − 2 persons and n − 2 hats.
- Person i does not take the hat 1. This situation can be simulated as renumbering hat 1 as i. So now case is equivalent to solving problem with n − 1 persons n − 1 hats.
The expected value of the number of ladies for which the professions are assigned correctly by the graphologist turns out to be:
0 ⋅ p(0) + 1 ⋅ p(1) + 2 ⋅ p(2) + 3 ⋅ p(3) + 4 ⋅ p(4) + 5 ⋅ p(5)
= 0 + (5C1 ⋅ d4)⁄5! + 2 ⋅ (5C2 ⋅ d3)⁄5! + 3 ⋅ (5C3 ⋅ d2)⁄5! + 4 ⋅ (5C4 ⋅ d1)⁄5! + 5 ⋅ (5C5 ⋅ d0)⁄5!
= (0 + 45 + 40 + 30 + 0 + 5)⁄120
On trying to generalize this result for n ladies and n professions, we get the same result. The expected number of correct assignments by the graphologist is always 1, no matter how many persons are involved.
This happens because
0 ⋅ nC0 ⋅ dn + 1 ⋅ nC1 ⋅ dn-1 + … + n ⋅ nCn ⋅ d0 = n!
where n is a positive integer, d0 = 1, dk is the number of derangements of k elements.
As a result, for n number of persons, where n is any integer, the number of correct assignments of professions turns out to be:
0 ⋅ p(0) + 1 ⋅ p(1) + … + n ⋅ p(n) = 0 ⋅ (nC0 ⋅ dn)⁄n! + (nC1 ⋅ dn - 1)⁄n! + … + 5 ⋅ (nCn ⋅ d0)⁄n! = (0 ⋅ nC0 ⋅ dn + 1 ⋅ nC1 ⋅ dn-1 + … + n ⋅ nCn ⋅ d0)⁄n! = n!⁄n! = 1
That was too much work to verify a simple fact. Here is a simpler way to verify it. Let us denote the graphologist's set of assignments of professions using a sequence of n numbers. The kth number in the sequence is 1 if the kth person is assigned the correct profession; it is 0 otherwise. For each person, the probability that he is assigned the correct profession is 1⁄n. This is because out of the n! possible ways of assigning n professions to n people, for a given k, the number of ways the kth person is assigned the correct profession is (n - 1)! and (n - 1)!⁄n! = 1⁄n.
So, the expected value of each number in the sequence is: 1/n. It can be proven that expectation is linear. One result of this is, E(x + y) = E(x) + E(y), where E(r) is used to denote the expected value of a random variable r defined on a given probability space. In other words, expectation of sum of random variables is equal to the sum of expectations of each random variable. So, the sum of all the numbers in the sequence is n⋅1⁄n = 1.
If you enjoyed this, here is a little fun problem for you that I made up while thinking on the concepts of derangement and expected value. Prove that
nC0d0 + nC1d1 + … + nCndn = n!