Page 1 of 2 12 LastLast
Results 1 to 15 of 18
Like Tree5Thanks

Math Help - Probability / odds of last person drawing their own name from a hat

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    Hong Kong
    Posts
    9

    Probability / odds of last person drawing their own name from a hat

    Hi... I'm an English teacher, and just did an exercise with my 6th graders - Secret Santa. But in my version, kids don't all draw names at the same time, everyone does it one at a time. The question I have is, what is the probability of the *last* student drawing their own name from a hat?

    If there are 12 students, 12 names in the hat, each student draws one name, in turn, and checks to be sure it's not their own, and if it is, they throw it back and pick again. Then the next student draws. However, in my exercise, no student draws their own name, until the very last student. Therefore the whole game has to be restarted. What were the odds of that happening? If possible, can you give it to me in a "1 in 1,000,000,000" type of answer? or explain how I can convert a decimal number to odds format?

    And I would like to add... I'm not a math student - and I'm now 20+ years outside of university, so my ability to solve equations that you give me may be limited. Please don't bash me as I've seen in other threads. I've come here to the experts in a field to answer a curious question I have. That's all it is. If this isn't the right place, kindly point me in the right direction.
    Thank you kindly
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,163
    Thanks
    761

    Re: Probability / odds of last person drawing their own name from a hat

    Hey HKJason.

    So just to clarify, are you finding the probability that everyone picks out the correct name and thus everyone gets their name and puts it back in the hat?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2012
    From
    Hong Kong
    Posts
    9

    Re: Probability / odds of last person drawing their own name from a hat

    Hmm. not really.

    12 Students in a class - Each has to get a present for one of their classmates, in secret. So we put 12 names into a hat, and each student, in any order, picks one name, looks at it, and if it's not their own name (can't give a present to yourself), they keep the name and go and buy a present for them. If it is their own name, they just toss it back in the hat, and select again.

    So in theory, with an even number of students, everyone gets a present. Given the way they select their names, everyone should get a name that is not theirs - except the last student *could* possibly be left getting their own name - and since they can't throw it back in, we have to do the whole thing over again! That's what happened. I want to know the odds of that happening... The first 11 students didn't select the 12th student's name, leaving the 12th student with his own name in the hat.

    example, for 3 students:

    1st possibility:
    A picks B (there are three to choose from)
    B picks C (only two names left)
    C picks A (it's the only one left) -> this 'game' was successful.

    2nd possibility:
    A picks C
    B picks A
    C picks B -> another successful outcome.

    3rd possibility:
    A picks B
    B picks A
    C picks C -> unsuccessful -- so the game has to start over. <- odds of this... but for 12 students
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,163
    Thanks
    761

    Re: Probability / odds of last person drawing their own name from a hat

    So basically you want the odds of the last person getting their own name given that everybody else got a different name?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2012
    From
    Hong Kong
    Posts
    9

    Re: Probability / odds of last person drawing their own name from a hat

    That sounds like a nice succinct way to say it! thanks :-)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,163
    Thanks
    761

    Re: Probability / odds of last person drawing their own name from a hat

    What I can do is simulate the process happening about 50,000 times and get a probability for that particular event happening.

    This is a common technique for complex problems that don't have a nice or easy analytic solution.

    Do you want to give it a try later on (not right at this moment)?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2012
    From
    Hong Kong
    Posts
    9

    Re: Probability / odds of last person drawing their own name from a hat

    Sure! Thank you very much for your time on this! I'm not in a rush...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Probability / odds of last person drawing their own name from a hat

    Hi HKJason,

    I wrote a program (using the Python programming language) which worked through all the possibilities and computed the probability that the last person draws his own name, with the result that the probability is 0.0650929. My program is not a simulation, like that proposed by chiro, but rather a computation; it doesn't draw any random numbers. It takes about 1.5 minutes to run on my PC, however, so I'm glad you don't have more students, because the run time is more or less exponential in the number of students.

    I've tried to come up with a pencil and paper solution but have not been successful so far. The bit about not drawing your own name (unless you are the last to draw) makes computation tricky.
    Thanks from HKJason
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,413
    Thanks
    1852

    Re: Probability / odds of last person drawing their own name from a hat

    No "the bit about not drawing your own name" does NOT make it tricky. No matter how the first n-1 names are given out, the whole problem here is to determine the last name left in the hat being the name of the last student to pick.

    If there are n names in the hat then the probability of any one name being the last left in the hat is 1/n. And the probability of any one out of n students being the last to pick is also 1/n. The probablility that the last name left in the hat is the name of the last student to pick is [itex](1/n)(1/n)= 1/n^2[/itex].

    If there are 20 students the probability the last student will get his own name is 1/400.
    Thanks from HKJason
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    708
    Thanks
    293

    Re: Probability / odds of last person drawing their own name from a hat

    Hi HKJason,
    As you computed, for 3 students the probability that you must start over is 1/3. Of course, this does not agree with the last answer of HallsOfIvy, I believe his solution neglected to take into account that the pairings of the students do not have a student paired with himself. Here's my solution:
    Probability / odds of last person drawing their own name from a hat-fixedpointfree.png
    Thanks from HKJason
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Dec 2012
    From
    Hong Kong
    Posts
    9

    Re: Probability / odds of last person drawing their own name from a hat

    Wow, thank you everyone, for the effort you put into this. I appreciate it.

    It is interesting, however, that I end up with 3 different answers so far....
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Probability / odds of last person drawing their own name from a hat

    Since we have three different answers so far, I propose to consider the case where there are only 4 students in detail in order to illustrate what I think is a correct method of solution. For simplicity let's suppose the students are numbered 1 through 4, and the names in the hat are actually their numbers.

    As already noted by johng, there are only two possible sequences in which student 4 gets stuck with his own number: 2-3-1-4 and 3-1-2-4; anything else violates the rule that a student (other than student 4) can't draw his own number. We will compute the probabilities of each of these two sequences.

    In order to draw 2-3-1-4, student 1 must first draw a 2, with probability 1/3. (Remember that he can't draw a 1, so there are only 3 possibilities.) Student 2 must then draw a 3, with probability 1/3 since the hat contains {1,3,4}, all of which are "legal". Student 3 must then draw a 1 with probability 1/2 since the hat now contains {1,4}, all of which are allowed. Student 4 is then stuck with a 4. So the probability of 2-3-1-4 is (1/3)(1/3)(1/2).

    In order to draw 3-1-2-4, student 1 must draw a 3, with probability 1/3. Student 2 must then draw a 1, with probability 1/2, since the hat now contains {1,2,4} but he can't draw a 2. Student 3 must then draw a 2, with probability 1/2 since the hat now contains {2,4}. Student 4 is stuck with a 4. So the probability of 3-1-2-4 is (1/3)(1/2)(1/2).

    Putting these two results together, the probability that student 4 is stuck with his own number out of the hat is
    \frac{1}{3} \cdot \frac{1}{3} \cdot \frac{1}{2} + \frac{1}{3} \cdot \frac{1}{2} \cdot \frac{1}{2} \approx 0.1389

    The difficulty of expanding this method to larger numbers of students is that the number of cases that must be considered (here only two) expands exponentially with the number of students. It's not hard to see that the number of possible sequences for n students is D(n-1), the number of derangements of n-1 objects. For 12 students, we have D(11) sequences, which is over 14 million but is feasible on a modern PC. Working the problem for 24 students by this method is clearly not feasible. So for larger numbers of students, I think the best idea so far is chiro's recommendation of using a simulation to get an approximate result. I've used simulation to check my answers for 4 and 12 students, and the simulation agrees well with the numbers computed by the "exact" method. Maybe someone will find a shorter computation, but I haven't seen one posted yet which I think is correct.

    [edit] More information on derangements can be found here: Derangement - Wikipedia, the free encyclopedia [/edit]
    Last edited by awkward; December 20th 2012 at 05:44 PM.
    Thanks from HKJason
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Dec 2012
    From
    Hong Kong
    Posts
    9

    Re: Probability / odds of last person drawing their own name from a hat

    Quote Originally Posted by awkward View Post
    probability is approx 0.1389

    I think the best idea so far is chiro's recommendation of using a simulation to get an approximate result. I've used simulation to check my answers for 4 and 12 students, and the simulation agrees well with the numbers computed by the "exact" method.

    Excellent! Just so I'm clear, the simulation method for 12 students shows a .1389 (or approx) probability as well?

    Thanks for the tip on the derangements. It seems that is what I'm after. I either forgot about them, or didn't cover them in Uni...
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Probability / odds of last person drawing their own name from a hat

    Quote Originally Posted by HKJason View Post
    Excellent! Just so I'm clear, the simulation method for 12 students shows a .1389 (or approx) probability as well?

    Thanks for the tip on the derangements. It seems that is what I'm after. I either forgot about them, or didn't cover them in Uni...
    No, my simulation for 12 students shows a probability of about 0.065, which is in agreement with the calculation of 0.06509.

    0.1389 is the probability for 4 students.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Probability / odds of last person drawing their own name from a hat

    If anyone is interested, here is my Python program for computing the probability for the case of 12 students. To change the number of students, all that's necessary is to change the first line, currently reading "N = 12".

    The students are numbered from 0 to 11, since that seems a little more natural in Python. The hat is represented by a Python "set". The program prints out the probability that the last student gets stuck with his own number from the hat.

    Warning: this program can take a long time to run, as described in a previous post.

    Code:
    N = 12  # number of students
    pN = 0  
    
    # student i draws from the hat
    # the probability of getting to this point is p
    def draw(i, hat, p):
        global pN
        if not ((N-1) in hat):
            return
        if i == N-1:
            pN += p
            return
        if i in hat:
            nchoices = len(hat) - 1
        else:
            nchoices = len(hat)
        for j in hat:
            if i != j:
                draw(i+1, hat - set([j]), p / float(nchoices))
    
    hat = set([i for i in range(N)])
    draw(0, hat, 1.0)
    print pN
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Probability and odds?
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 14th 2011, 11:39 AM
  2. probability or odds, not sure which it is
    Posted in the Statistics Forum
    Replies: 1
    Last Post: June 27th 2010, 12:09 PM
  3. Odds and probability question!
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 17th 2010, 06:42 PM
  4. Odds vs Probability
    Posted in the Statistics Forum
    Replies: 2
    Last Post: February 8th 2010, 06:15 AM
  5. Finding the probability of a random person
    Posted in the Advanced Statistics Forum
    Replies: 7
    Last Post: May 31st 2009, 11:08 PM

Search Tags


/mathhelpforum @mathhelpforum