Thread: [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

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?

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

Originally Posted by temp

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.

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.

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