I have a probability problem:
n people play a game. First, each person receives a blank piece of paper and they write their names on it. The papers are then collected and shuffled and redistributed to each person randomly. If any one received the paper with their own name on it then the papers are collected again, shuffled again and redistributed again. This process continues until all people have paper with name other than their own on it.
You, as the host, stand out and read the name on your paper. The person whose name was read out then stand up and read the name on his paper and so on. The game stops when your name (the first person) is called.
Find the expected value of the number of people whose names would not be called.
==============================
My answer is n/2-1.
My tutor in class suggested the answer could be complex so I am not confident in my answer at all... Can anyone please help? Thanks.
I'm not sure this answer is correct since it doesn't work for n = 3 .....
Let the names of the people be A, B and C and A is the host.
There are only two possible distributions:
A, B, C
C, A, B with probability 1/2. Number of names not called out = 0.
B, C, A with probability 1/2. Number of names not called out = 0.
Therefore expected value of names not called out = (0)(1/2) + (0)(1/2) = 0. Yet the proposed answer gives (3/2) - 1 = 1/2 ......
I don't have time right now to look more closely (not one word from anyone .........) but will try to later.
If n = 3 and the names are A, B and C respectively, then the possible distribution should be:
1: B A (stops as A is called)
2: C A (ditto)
3: C B A
4: B C A
One name wouldn't be called for the first 2 situations and all are called for the last 2.
The probability for each situation is 1/4. Hence the probability of one name not called is half and all names called is half. Therefore the expected value in this case would be 0 * 1/2 + 1 * 1/2 = 0.5 = 3/2 - 1.
Therefore I think n/2 -1 works when n=3.
Correct me if I am wrong. Thanks.
Isn't eveyone meant have a bit of paper with someone elses name on it? The only way that can happen in the two ways I posted.
A, B, C
1. B, A, C not a valid distribution since A gets B, B gets A, but C gets C.
2. C, A, B valid distribution.
3. C, B, A not a valid distribution since A gets C, but B gets B, C gets A.
4. B, C, A valid distribution.
So unless I'm missing something very obvious .....
Some insight might be gained by considering n = 3 (done), n = 4 (see below) etc.
When n = 4 there are 9 possible derangements. The probability of each derangement is 1/9. Of the 9 derangements, 3 leave two names not called out and the remaining 6 leave 0 names not called out. So when n = 4 the expected value for the number of names not called out is 2/3.
I haven't had the inclination to consider n = 5 (44 possible derangements) but it may be that a pattern for the number of names not called out might emerge and provide insight for the general case. I can't help thinking that the permutation group might be useful here ......
If I have the time I might have more to say.
Derangement - Wikipedia, the free encyclopedia
Note also that for any value of n, by symmetry you only need to consider of the derangements in order to calculate the distribution of number of names not called out (of course, this fraction of cases considered cannot be chosen randomly .....)