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
^{5}C_{1} 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 d_{4}, then the
number of ways to assign the professions such that exactly 1 lady has
been assigned the correct profession is: ^{5}C_{1}
⋅ d_{4}.

Similarly, the number of ways he can get exactly 2 correct is
^{5}C_{2} ⋅ d_{3} where d_{3} 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
d_{k}, where 1 ≤ k ≤ 5. Now, we can say that in general,
the number of ways he can get exactly k correct is
^{5}C_{k} ⋅ d_{5-k}. So, the probability
p(k) that he can get exactly k correct is
^{(5Ck ⋅
d5-k)}⁄_{5!}.

The number d_{k} 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 d_{1} = 0 since there is
only one permutation of a sequence containing a single element and this
only permutation is not a derangement. d_{2} = 1 since the only
possible derangement of (1, 2) is (2, 1). d_{3} = 2 since the
only possible derangements of (1, 2, 3) is (2, 3, 1) and (3, 1, 2). To
calculate d_{4} and d_{5}, I'll use the recurrence
relation, d_{n} = (n - 1)(d_{n-1} + d_{n-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, d

- 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.

_{4}= 3(d

_{3}+ d

_{2}) = 3(2 + 1) = 9 and d

_{5}= 4(d

_{4}+ d

_{3}) = 4(9 + 2) = 44.

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}

= 1

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 ⋅ ^{n}C_{0} ⋅ d_{n} + 1 ⋅
^{n}C_{1} ⋅ d_{n-1} + … + n ⋅
^{n}C_{n} ⋅ d_{0} = n!

where n is a positive integer, d_{0} = 1, d_{k} 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

^{n}C_{0}d_{0} +
^{n}C_{1}d_{1} + … +
^{n}C_{n}d_{n} = n!

## No comments