Queue height
Some (n) people are standing in a queue. On average, how many of them can say that they are taller than everyone ahead of them?
NB The person at the front of the queue, can say that he is taller than everyone ahead of him.
NB The person at the front of the queue, can say that he is taller than everyone ahead of him.
Labels: Probability
posted by Chris at
12:18 PM
17 Comments:
Say a particular person is the j'th out of n people in line, and the k'th tallest. Assume also there are NO ties in height. If the person is taller than everyone ahead of them, then k < j. The person could have been in "n" spots, and only in (j-1) of them would this be true. So the probability for each person is (j-1)/n.
The average over the entire line is
sigma(j=1..n) (j-1)/n^2
which wxMaxima tells me is equal to (n-1)/2n or 1-(n/2).
This makes sense, because as n grows without bound, the average tends toward 1/2.
This post has been removed by the author.
frayed knot
Oh well, I tried.
I think the answer will converge to 1.
Let n be a random variable that represents the number of persons that are taller than everybody ahead in the queue.
Define p(n) as the probability of having n tallies (:D) in the queue!
If the queue length is 3, then p(1) = 0.5, p(2) = p(2>1,0)p(1>0)=0.5^3, and p(3) = p(3>2,1,0)p(2>1,0)p(1>0)=0.5^6
By induction, for a queue of length 4, p(n) = 0.5^10
Hence,
p(n) = (0.5)^(n(n+1)/2)
As E(n) = sum(n.p(n)) for n ranges between 1 and infinity, E(n) will eventually converge to 1.
lol, okay. Apparently, we need some help here :-) !
Hey guys, at least you're trying.
Check out Where do I sit? but just read the first answer, the try to work it out. It hhas a very nice solution. I really enjoyed cracking it.
I've started read Anon 3:15 PM. I think you need to define p(n) more clearly. I'm not sure what you have defined. But see below.
OR ignore all your stuff and experimentally try out various scenarios for a queue of 1 then 2 then 3. See where you go. For a queue of 1, 1 person can say he is the tallest (as there is no-one else).
OR define Tn as the expected/average number of tallies. i.e. the number of people who are taller than all the people in front of him/her.
I have either solved it or come up with another wonderful wrong answer.
After enumerating and examining all permutations, I found these results.
1 person: average 1
2 people: average 3/2
3 people: average 11/6
4 people: average 50/24
5 people: average 274/120
Obviously the denominator is n!. The numerator is harder to see the pattern, so I chickened out again and consulted the Online Encyclopedia of Integer Sequences (OEIS) and found it matches A000254
So, 1 person: 1/1
2 people: 1/1 + 1/2 = 3/2
3 people: 1/1 + 1/2 + 1/3 = 11/6
4 people: 1/1 + 1/2 + 1/3 + 1/4 = 50/24
5 people: 1/1 + 1/2 + 1/3 + 1/4 + 1/5 = 274/120
n people: sigma(1..n) 1/n
The sequence diverges, so there's no limit.
Your the man Ross. Well done indeed.
I've got a friend round, so I won't follow up for sn hour or two.
Okay, I worked it out again. I dunno from where I came up with that solution in my first post, lol.
Here goes. Say, the person in the head of the queue will always be taller than everybody ahead. So, at the very beginning we've 1 here.
If the queue length is 2, we'll have another 1 if the 2nd person is taller than the 1st, that's a probability of 0.5. So, on average we'll have 1 + 1 * 1/2.
For a queue of length 3, we'll have 1 + 1 * p(2nd > 1st) + 1 * p(3rd > 2nd > 1st) = 1 + 1 * 1/2 + 1/3
Hence, for a queue of length n, we've an average number of tallies equals to sum(1...n) 1/n = Harmonic(n).
I think I got it right this time.
Oh, Ross got it before me :-(. Well done Ross !
Hi Anon. You certainly seem to have got it. I think your explanation could have done with one more illustrative step in it. I can't be sure why you knew that adding 1/3 was right (of course I know why, but I set the problem).
There is a rather nice recursive way of doing it. Is anyone game?
My friend could see I was busting to respond.
How embarrassing. I meant "you're" the man Ross.
Well done both of you.
Let T[n] be the expected (average) #people who are taller than
all the people in front of them, when there are n people. Now
consider a queue with n-1 people in it. The number of people who
are taller in that queue will be T[n-1]. When the n th person
joins the queue, on average, 1 in n of them will be taller than
all the other n-1 people => T[n] = T[n-1] + 1/n. As T[1] = 1,
T[n] = 1 + 1/2 + 1/3 + ... + 1/n.
OR
Let T[n] be as above. If the tallest person is at the back of the queue, which occurrs 1/n of the time, then T[n] = 1 + T[n-1].
If he is second to last, again this happens 1/n of the time, then
T[n-1] = 1 + T[n-2]. So
T[n] = (1/n)((1+T[n-1]) + (1+T[n-2]) + ... + (1+T[1]) + 1)
=> nT[n] = n + T[n-1] + T[n-2] + ... + T[1]
=> (n-1)T[n-1] = (n-1) + T[n-2] + ... + T[1] {by definition}
Subtracting the second from the first => T[n] = T[n-1] + 1/n
I tried to solve the problem too but didn't get any harmonic or anything simmilar.let me tell u what I thought.
in all the ways of standing the queue there is just one way when only one man would say that he is taller than person ahead i.e. when all stand such that they are in decreasing order of height from front.
similarly two man would saying that when queue stand such that man from front are in increasing order till second man and after him all in decreasing order.
in this if we proceed then we will find that for any number of man (say k)there is only one way they can say that every one ahead of them in queue is shorter than him.
so we can deduce that average goes llike this
1(if one say so)+1(if two say so)+1(if three say so)............
this whole divided by foctorial n,
because there are n! wats of standing the queue.hence the answer is
n/n!=1/(n-1)!
Hi Ishan. You stopped developing your argument too soon. You got to
2 cases, but didn't spot that that gave you 2! = 2 ways of arranging
the queue. If you'd gone to 3 men, you'd have 3! = 6 equally likely
ways of arranging them. Let the heights be s,m,l (small, medium,
large): lms(1), lms(1), mls(2), msl(2), sml(3), slm(2). So for them,
the average is: (1*3 + 3*2 + 2*1)/6 = 11/6 = 1 + 1/2 + 1/3.
NB the probability that any two people have exactly the same height
i.e. to an infinitely accurate precision, is 0.
Post a Comment
Links to this post:
Create a Link
<< Home