Thread: Expected value

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.

Originally Posted by Ms. NY

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.

Without the stopping rule all the names will be read out in some order, and my name is equally likely to be in any position other than the first. So the expected number of names read out is:



and the expected number of names not called is:

Originally Posted by CaptainBlack

Without the stopping rule all the names will be read out in some order, and my name is equally likely to be in any position other than the first. So the expected number of names read out is:



and the expected number of names not called is:

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.

Originally Posted by Ms. NY

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

Originally Posted by mr fantastic

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.

That looks OK to me, now I think about it the position of my name does not signify how many names are read out, which is what I had assumed.

RonL

I see...hmmmm

Originally Posted by Ms. NY

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.

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.

Let kn denote the number of possible derangements when number of people is n.

n=2, k2=1;
n=3, k3 = 2 = 1 * 2C1;
n=4, k4 = 9 = (1+2) * 3C1;
n=5, k5 = 44 = (2+9) * 4C1;
n=6, k6 = 265 = (9+44) * 5C1;
...
n=n, kn = (k(n-2) + k(n-1)) * (n-1)C1 ...?

Originally Posted by Ms. NY

Let kn denote the number of possible derangements when number of people is n.

n=2, k2=1;
n=3, k3 = 2 = 1 * 2C1;
n=4, k4 = 9 = (1+2) * 3C1;
n=5, k5 = 44 = (2+9) * 4C1;
n=6, k6 = 265 = (9+44) * 5C1;
...
n=n, kn = (k(n-2) + k(n-1)) * (n-1)C1 ...?

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