Results 1 to 6 of 6

Math Help - [SOLVED] Probability question

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    9

    Smile [SOLVED] Probability question

    Here's my problem.

    You are the last person to arrive to the event with k numbered seats
    (say, k >= 2), and all k-1 seats have been already randomly taken. You
    insist on sitting in the seat printed on your ticket, so you find your
    seat and (if it's not empty), you make the person sitting there stand up
    and find her own seat. That person in turn finds her own seat and makes
    the person sitting there stand up, etc... The process continues until
    someone finally seats in the empty seat. The question is, what's the
    probability that the first person to arrive to the event will not have
    to stand up?

    Appreciate all your help
    Last edited by temp; August 15th 2009 at 05:13 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    820
    Thanks
    31
    What level maths is this? I instantly thought: trick question - it's the probability that the first person sat in his own seat. Then I realised that there may well be closed chains that don't include the first person. This is quite deep, I think. It seems to be related to the size of a cycle in a permutation. Could this be an exercise in group theory, or am I overcomplicating it?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    9
    This problem came from a Math Stat II course, for which Discrete Math is one the prerequisites.

    Honestly, my discrete math is a bit rusty (5+ years since I took it), so I would appreciate any hint I can get

    Btw. my first guess was simply 1/k, but I agree with you. It must be more complicated...
    Last edited by temp; August 15th 2009 at 05:12 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by temp View Post
    Here's my problem.

    You are the last person to arrive to the event with k numbered seats
    (say, k >= 2), and all k-1 seats have been already randomly taken. You
    insist on sitting in the seat printed on your ticket, so you find your
    seat and (if it's not empty), you make the person sitting there stand up
    and find her own seat. That person in turn finds her own seat and makes
    the person sitting there stand up, etc... The process continues until
    someone finally seats in the empty seat. The question is, what's the
    probability that the first person to arrive to the event will not have
    to stand up?

    Appreciate all your help
    The probability is 1/2, independent of k.

    To see this, number the seats and the people from 1 to k and consider the permutation of {1, 2, ..., k} required to put each person in his proper seat. We will assume all the permutations are equally likely. As is well known, the permutation can be represented in an essentially unique way as the product of disjoint cycles. A little thought will show that the people who must move in order for the last arrival, k, to go in his proper seat are the members of the cycle containing k.

    Proposition 6.18 in "A Walk Through Combinatorics, 2nd Edition" by Miklos Bona, tells us that 1 and k are in the same cycle in exactly half of all permutations. So the probability of this occurrence is 1/2.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    820
    Thanks
    31
    That is a theorem I didn't know! I'm going to have to go away and think about why, now ... and I was going to do something else this weekend instead, bah.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Aug 2009
    Posts
    9
    Thank you.

    For an alternative explanation, see the answer I got on Topology Q+A board

    Re: Statistics/Probability

    Pk - probability, that the first person will have to stand up in problem with k seats
    now this is distribution dependent:
    what is the probability that my seat is free? Let's say it is 1/k. (kind of uniform distribution)

    Then: Pk = 1/k (probability that I will kick the FIRST-ONE)
    + (k-2)/k (probability that I will kick someone else)*P(k-1)
    (because he is in the same situation, just there are only k-1 seats)

    so Pk = (1+(k-2)*P(k-1))/k and P2 = 1/2
    from this prove that this means that Pk = 1/2 i.e. 1-Pk = 1/2.


    P.S. I hope I'm not violating any rules by posting a Topology Q+A link....
    Last edited by temp; August 15th 2009 at 06:03 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Probability question
    Posted in the Statistics Forum
    Replies: 0
    Last Post: December 17th 2009, 04:59 AM
  2. [SOLVED] Probability question - Expectation
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 23rd 2009, 02:51 PM
  3. [SOLVED] probability question
    Posted in the Statistics Forum
    Replies: 3
    Last Post: February 6th 2009, 10:32 AM
  4. [SOLVED] Probability Question. (please help)
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: March 3rd 2008, 11:28 AM
  5. [SOLVED] Probability Question
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: November 17th 2007, 12:23 AM

Search Tags


/mathhelpforum @mathhelpforum