Results 1 to 10 of 10

Math Help - Expected value

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Ms. NY View Post
    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:

    \bar{n}=\sum_{i=2}^n \frac{1}{n-1}i

    and the expected number of names not called is:

    \overline{nn}=\sum_{i=2}^n \frac{1}{n-1}(n-i)=n -\sum_{i=2}^n \frac{1}{n-1}i =\frac{n}{2}-1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by CaptainBlack View Post
    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:

    \bar{n}=\sum_{i=2}^n \frac{1}{n-1}i

    and the expected number of names not called is:

    \overline{nn}=\sum_{i=2}^n \frac{1}{n-1}(n-i)=n -\sum_{i=2}^n \frac{1}{n-1}i =\frac{n}{2}-1
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2008
    Posts
    4
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Ms. NY View Post
    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 .....
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by mr fantastic View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2008
    Posts
    4
    I see...hmmmm
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Ms. NY View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Aug 2008
    Posts
    4
    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 ...?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Ms. NY View Post
    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 \frac{1}{n-1} 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 .....)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Expected Value
    Posted in the Statistics Forum
    Replies: 1
    Last Post: April 25th 2011, 04:51 PM
  2. Expected value/ st dev/var
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: September 30th 2010, 03:55 AM
  3. Expected Value
    Posted in the Advanced Statistics Forum
    Replies: 9
    Last Post: September 20th 2010, 12:52 AM
  4. Expected Value
    Posted in the Statistics Forum
    Replies: 3
    Last Post: April 28th 2009, 05:05 PM
  5. expected value
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: January 16th 2009, 09:51 AM

Search Tags


/mathhelpforum @mathhelpforum