[gwnn]

Fluffy, on 2014-May-17, 03:20, said:

You are not taking into account that you just missed a train.

Yea, but we are also not taking into account that there were actually two questions in the opening post all along.

It's kind of strange, I thought about it a bit today and it seems like the 'You just missed one.' condition somehow enters in our mind as a constant, and it somehow takes more than just another question to over-ride it. I am not trying to diss lamford (and I apologise for my irritated post above) but I think the best solution for stating a problem like this is to put all the common conditions in a paragraph and then have two clear questions. For example :

Quote

(3 trains an hour bla bla)
1. You get to the train station and there is no sign of a train. What is the average waiting time?
2. You get to the train station and you just miss a train. What is the average waiting time?

Again, not as a criticism of lamford, just something that I learned through this thread. This way it is clear that there are two parts of the problem and it is clear which conditions are common. Somehow reading comprehension decreases when we need to think of two maths problems at the same time.

[kenberg]

This is what I get out of the discussion so far. Perhaps we agree?

Suppose there are n trains rather than specifically 3. Suppose each arrives randomly (uniform distribution) between 2 nad 3, and suppose that between 3 and 4 there are also n trains, arriving randomly in the same way. Then:

A. If a guy arrives at the top of the hour his expected waiting time to catch a train is the fraction 1/(n+1) of an hour. eg if n=3 he waits 15 minutes on average. This sort of works even for n=0, he waits for 1/(0+1) =1 hour, although he doesn't get a train then either.

B. If he arrives during [2,3) just as a train leaves, and if there is no reason to think he is more likely to have just missed one train than another, his expected waiting time is 1/n. The exepeted waitng time might, I believe it does, depend on which train he just missed. But if the experiment includes a random, equally likely, choice of missed train then it's 1/n.

C. If he arrives randomly (uniform distribution) during the hour from 2 to 3, his expected waiting time can be computed. I haven't thought it through enough to commit myself to an answer.


In case A, we don't care about what happens after 3. In cases B and C we do. For example, suppose we are still on this random schedule from 5 to 6, but starting at 6 a train arrives at 6:03 and every ten minutes after that. Then if he misses the last train between 5 and 6, he waits until 6:03 rather than for some randomly arriving train after 6. .


It is not unusual for problems such as this, especially probabilistic ones, to lead to confusion. Problems about an imagined situation have to be stated with great precision or else the analysis is pretty hopeless. In a real world case, we would investigate the mechanism so we clearly understood just how these random arrivals are generated. If the guy arrives at a random time uniformly distributed between 2 and half past 2, the answer will be different than if he arrives between 2 and 3, uniformly distributed. Without a precise statement of the problem, everyone guesses what is meant, not everyone guesses the same.

gszes earlier said "Questions like this without sufficient details are a MENSA specialty so they
can claim their interpretation is the best:". I don't know about Mensa onw way or the other, a friend suggested I take the rest, I declined. But his general point about the need for clarity is right.

[kenberg]

With 3 randomly arriving trains during each hour (from the top of one hour to the top of the next) and a randomly arriving passenger during one of those hours (uniform distribution of arrival time during that hour) I think the expected waiting time is 5/32 (oops, scratch that, 6/32 which is 3/16) of an hour. I don't have time to check this carefully, but try this reasoning:

The train arrivals break the hour into four intervasL before the first train, between the first and second, and so on.

The expected value of the random lengths of each of these intervals is 1/4.

If the passenger arrives during the first interval his expected waiting time is half the length of the interval. So, on average, 1/8.

Same thing if he arrives during the second or their interval

If he arrives during the fourth interval, he has to first wait until the end of this interval, again with an expected waiting time of 1/8, and then wait for the first train of the next hour, expected waiting time of 1/8 (no, 2/8 since he is at the beginning of the interval).

So we have waiting times of 1/8, 1/8, 1/8, 3/8 depending on the interval of arrival. All intervals are equally likel.y for arrival so we average these four numbers and get 6/32=3/16.

Maybe I am missing something here, I will think about it while mowing the grass.I ahve already interrupted my mowing to correct 5/32 to 6/32=3/16. Back to the grass.

Added: I guess I am claiming that the general formula with n trains is an expected waiting time of (n+3)/(2(n+1)^2). In an odd sort of way this makes sense again for n=0. The guy arrives sometime during the first hour, waits on average a half hour, assumes he missed whatever trains there were that hour, waits out the entire next hour, and then realizes there are no trains and goes home. he waits, on average, 3/2 of an hour just as the formula says. With one train per hour the formula says 4/8=1/2. That seems nuts, no on second thought seems right. I have to think about it. Spouse is picking up knife and telling me to get off the computer.

I am about to go away for the weekend so I'll check in later.

[kenberg]

Focusing in this post only on the second question:

I will state one interpretation to the second question, and then the answer that I believe to be correct. There is nothing new here from the last post except perhaps I can phrase it more carefully.


I am assuming that the passenger arrives sometime between the top of one hour and the top of the next hour, and that we are then to compute the average length of time he will have to wait. We phrase it assuming the passenger arrives between 2 and 3:


Assumptions: There will be n (with n=3 if you like) trains arriving between 2 and 3, and n more trains arrive between 3 and 4. There will be one passenger arriving between 2 and 3. These 2n+1 arrival times are a independent set of random variables, each of them uniformly distributed over either [2,3] for the first n trains and the passenger or else over [3,4] for the second collection of n trains. We let W be the length of time from the passenger's arrival to the arrival of the first train after he arrives.

The problem is to find the expected value of W, the time the passenger waits for the train. With this interpretation the answer is (n+3)/(2(n+1)^2). In particular, for n=3 the answer is 3/16.

The argument runs: The arrival times of the n trains between 2 and 3 breaks [2,3] into n+1 intervals, and similarly with he trains arriving between 3 and 4. The expected value of the length of each of those intervals is (one can see fairly easily) 1/(n+1). If the passenger arrives randomly during any of the first n intervals his expected waiting time is half the length of that interval. If he arrives during the last interval he has missed all the trains for that hour. He has to wait until the end of that interval and then he has to wait for the first train of the next hour. His expected waiting time to reach the top of the hour is again half the expected length of this last interval, and his expected waiting time for the first train of the next hour is the full expected length of the first interval after 3.

So his expected waiting time conditioned on him arriving during any specific one of the first n interval is 1/(2{n+1)) and his expected waiting time conditioned on him arriving during the last interval is 3/(2(n+1)). Since all intervals have the same expected length, we get the expected waiting time by averaging these (n+1) numbers. We get (n+3)/(2(n+1)^2).

The problem is an artificial one and as in many such problems perhaps I have misunderstood the meaning. . Even if so, perhaps this will help in pinning down just what the intended interpretation was.

Of course the analysis could be in error, but it seems right.

[mike777]

Ken as I have stated before you are a wonderful teacher of math. I mean a wonderful teacher of math to us non math guys.

This post shows I think where math teachers lose us.

I understand your English, you lose us in the equation. You lose us in the very first equation, that to you seems easy to understand but it is not.

My guess is it only takes more time, much more time to explain the equations to equal how well you explain the problem in plain English.

[gwnn]

kenberg, I suspect the problem with your reasoning is that there will almost always be intervals with different lengths. The expected length of the four lengths in order of lengths is probably something like 20-16-14-10 or something like that (I guess there is an analytic formula for this but I'm too lazy to look it up). He will be more likely to get in the longest interval than the shortest one and I don't see how you accounted for that. In the case that I outline here, the average length of the interval he gets there is 15.87 minutes (sum(x_i^2)/sum(x_i) where sum(x_i) is 60 here).

[kenberg]

gwnn, on 2014-May-19, 02:12, said:

kenberg, I suspect the problem with your reasoning is that there will almost always be intervals with different lengths. The expected length of the four lengths in order of lengths is probably something like 20-16-14-10 or something like that (I guess there is an analytic formula for this but I'm too lazy to look it up). He will be more likely to get in the longest interval than the shortest one and I don't see how you accounted for that. In the case that I outline here, the average length of the interval he gets there is 15.87 minutes (sum(x_i^2)/sum(x_i) where sum(x_i) is 60 here).

First a note to mike:This will continue to be math heavy. The problem has a vagueness to it that math can eliminate, but this does come at a cost to non-mathematicians.. I will try another version later that might be clearer.


My first thought was to look up trhe expected value of the lengths by instead I computed them, at first for n=3 and then for general n. Let's do n=3. After this I will give the argument, simpler but more abstract, for general n. First we have to be clear about just which intervals we are speaking of. Let's go with n=3. I will measire time from the top of the hour sp at a quarter after 2 I will say the time is 0.25.

I let A1, A2, A3 be the arrival times, X1,X2,X3 be these same three numbers listed in increasing order. So if the arrival tiems are 0.86,0.23, 0.57 then X1= 0.23, X2= 0.57 and X3=0.86.

The intervals I am speaking of are [0,X1], {X1.X2], [X2,X3] , {X3,1]. I am claiming that the expecte values of X1-0, of X2-Xq, of X3-X2, and of [1-X2] are each 1/4.

First some symmetry: The expected value of X1-0 is the same as the expected value of 1-X2 since the minimum of A1, A2,A3 is as likely to be close to 0 as the maximum is to be clost to 1. Similarly, the expected value of X2-X1 is the same as the expected value of X2-X1 since in one case we are subtracting second largest from largest, in the other case we are subtracting smallest from second smallest.

Also, the lengths add to one, so the expected values add to 1. So I I show that the expected value of the length of the left most interval is 1/4 I am done since then so is the rightmmost, and ttwo middle ones split what's left.

Now I computed the expected value of X1 a few posts back and got 1/4. Here is how: For any random variable X, the expected value of X (if it exists, for some rvs it doesn't) is given by integrating x dF(x) where F is the cumulative distribution function F*x) -Prob (X<x) and the integral is Riemann Stieltjes. The function f will be continuous whenever, as here, Prob(X=x)=0 ofr all x (The probability of arriving exactly at x=.5 as contrasted with , say, between 0.4999999 and 0.5000001 is 0). Usually, and it happens here, the integral of x dF(x) can be replaced by the integral of xf(x) dx where f is the derivative of f.

Sorry for all that, the short version is that we have to compute F(x), differentiate it to get f, and then integrate xf(x) to get teh expected value of X.

Here calculating F directly is easy. P(X1<x) = 1- P(A1,A2, A3 are all >x) since X1 is not less than X if and only if all of A1, A2, A3 are greater than X. Well. greater or equal but in a continuous variable it doesn't matter since the probability of exact equality is 0.

Thus, F(x) =1-(1-x)^3, f(x)=3(1-x))^2 and E(X1), the expected value of X1, is the integral of 3x(1-x)^2 from 0 to 1. We can just do this, or more easily we can observe that thjis is the same as the integral from 0 to 1 of 3x^2(1-x). Since this expression is 3(x^2-x^3) the integral from 0 to 1 is 3(1/3 -1/4) which comes to 3/12=14.

So, for n=3, all the intervals of interest have an expected length of 1/4.


For general n, the same reasoning applied to the first integral leads us to integrating n(x^(n-1)-(x^n)) from 0 to 1 and we get n((1/(n+1))-(1.n))=1/(n+1).
But for n larger than 3 we need a different approach to see that the other intervals also have the same expected length. A probabilistic approach efficiently (more efficiently than the above) does this. I'll come back to that later. The above is the way I first calculated this, it has the advantege of being a direct calculation for the definitions and so is probably actually right. So is, I think, may general approach for n, but that's another post.

incidentally, it is also possible to get to the answer as follows. For each t in [01] calculate the expected waitng time assuming the passenger arrives at time t, and the integrate this quantity from 0 to 1. I am hopeful that I get the same answer when I do this, I think that I will.

First, some coffee.

[lamford]

kenberg, on 2014-May-19, 05:38, said:

For general n, the same reasoning applied to the first integral leads us to integrating n(x^(n-1)-(x^n)) from 0 to 1 and we get n((1/(n+1))-(1.n))=1/(n+1).

Which is indeed the same figure as the average of the minimums of sets of three random numbers between 0 and 1.

[kenberg]

lamford, on 2014-May-19, 05:47, said:

Which is indeed the same figure as the average of the minimums of sets of three random numbers between 0 and 1.

Yes. But my point here is that for 3. once I get the value of 1/4 for the first interval then I have the value of 1/4 for the last, and thus the remaining interfvals in the middle split up what is left, making 1/4 for all of them.

For general n, we can use the same reasoning to get 1/(n+1) for the first and last intervals but we need to think again to get 1/(n+1) for all the intervals.

[gwnn]

kenberg, I have had serious reading issues these last few days, so correct me if I'm wrong. You are essentially saying:

1. The three trains cut the hour in four intervals.
2. The four intervals each have an expected value of 15 minutes.
3. The probability that you get to any of the four intervals is equal, 25% (i.e., if you did the experiment 100 times, each time with random and different intervals and you noted which of the four intervals you got to, you would rate to get 25 ones, 25 twos, etc).
4. So you are 1/4 to be in the first quarter, which rates to be 15 minutes, and so on.

The first three of these is correct (and I might add, self-evident even without maths), but the fourth does not follow. Did you account for this? I posted a simple guess above about how average intervals would look like (ordered by length, not ordered chronologically!) It is true that on average your chance to be at the station in the first quarter is 25%, but you are much more likely to get to a "long" first quarter than a "short" first quarter. If the first quarter was 5 minutes, you are only 1/12 to get to the station in it. If the first quarter was 30 minutes, you are 1/2.

edit: to clarify, this has been discussed already by helene_t BTW upthread (that the interval you get to is more likely than not to be more than 15 minutes long): http://www.bridgebas...post__p__794130

This post has been edited by gwnn: 2014-May-19, 06:43

[StevenG]

kenberg, on 2014-May-19, 06:22, said:

For general n, we can use the same reasoning to get 1/(n+1) for the first and last intervals but we need to think again to get 1/(n+1) for all the intervals.

I bashed out the general case many years age, working out the probability functions. It's not difficult, just tedious (lots of factorials and summations), but the result is true.

[kenberg]

Explanation of why the expected length of the intervals is 1/(n+1).


We have independent uniformly distributed A1, ... , An rvs on [0,1 and we let me let X1, ... Xn be the same set of numbers listed in increasing order X1<X2< ...<Xn. We claim that the expected values of the various lengths, (X1-0), of (x2-X1), ... of (1-Xn) , are all 1/(n+1).

Suppose that A1, ..., An , and Y are all independent and uniformly distributed on [[0,1]. As we are about to draw these numbers, we can agree that the number Y is as likely to be the smallest as it is to be the second smallest or the third smallest etc. So, before we know any of the values, we can say P(X3<Y<X4) is 1/(n+1). Let's use 3 to represent any number, since bbo is not really set up for complex notation. We will just show that the expected value of x4-X3 is 1/(n+1).

So I am supposing that we we agree that before any numbers are drawn, P(X3<Y<X4)=1/(n+1).

Now we compute this another way: We first draw X1...Xn. Knowing these values, but not yet having drawn Y, then
P(X3<Y<X4 conditioned on the values of X1...Xn) = X4-X3.
We can now calculate P(X3<Y<X4) for all choices of X1...Xn as follows: If we take the expected value of P(X3<Y<X4 conditioned on the values of X1...Xn) for all choices of X1...Xn, we get P(X3<Y<X4), which we know to be 1/ (n+1). So the expected value of the left side of the equation
P(X3<Y<X4 conditioned on the values of X1...Xn) = X4-X3
we get 1/(n+1). Thus, E(X4=X3) is the same number, 1/(n+1).


So, for each interval, the expected value of the length is 1/(n+1).

[kenberg]

StevenG, on 2014-May-19, 06:30, said:

I bashed out the general case many years age, working out the probability functions. It's not difficult, just tedious (lots of factorials and summations), but the result is true.

Thanks If you go direct, you get a lot of binomial coefficients. But going as I did gives the result without these nasty factorials. The cost is that it uses some conditional expectations in a manner that might not be immediately certain, although it seems right.

[gwnn]

Was that a reply to me? I accepted a long time ago that each of the four intervals have an expected value of 15 minutes, in fact I said that I consider it to be self-evident.

My point is not that any given interval doesn't have an expected value 15 minutes, my point is that the interval you get to has an expected value larger than 15 minutes. It is most likely that you get to the interval that just happened to had been the longest interval. It is least likely that you get to the interval that was chosen to be the shortest interval. Do you dispute this? If not, did you take this into account?

This post has been edited by gwnn: 2014-May-19, 06:53

[kenberg]

gwnn, on 2014-May-19, 06:51, said:

Was that a reply to me? I accepted a long time ago that each of the four intervals have an expected value of 15 minutes, in fact I said that I consider it to be self-evident.

My point is not that any given interval doesn't have an expected value 15 minutes, my point is that the interval you get to has an expected value larger than 15 minutes. It is most likely that you get to the interval that just happened to had been the longest interval. It is least likely that you get to the interval that was chosen to be the shortest interval. Do you dispute this? If not, did you take this into account?

I concede. With one train per hour the expected waiting time appears to be 7/12, not 1/2. So right, I am wrong. (for n=1 I tried a couple of ways and got 7/12 both times but I am now wary...).

I thought the approach I was taking would cope ok with the varying lengths of the intervals that I arrived at, but apparently not. I was aware that we get to longer intervals more frequently, I thought that way I was doing it dodged that,. Not so.

So I need to rethink a little. It looked good but indeed it was not.

[kenberg]

Where are we? Is there an agreed upon answer yet? I did not follow some of the previous arguments, and I agree that what I said was wrong. Surely if there is an answer for 3 there is an answer for n. I apologize for being wrong but worse (or maybe better) i am short of time to think it through.

For that matter, is it even agreed that the a reasonable interpretation is that we are averaging for a guy arriving at some random time during one hour?

I am sorry, and embarrassed, for jumping the gun here. It seemed nice and easy.

[gwnn]

I thought we all agreed that the waiting time is 15 minutes until you said it was 3/16-th of an hour (11 minutes and 15 seconds). All you need to see this is that you are just interested in the length of the first interval, and it doesn't matter whether you arrive at the top of the hour or somewhere in between, as long as these three trains and the next three will arrive at the same minutes (i.e. the first train and the fourth will be exactly an hour apart, etc). At least I don't see why it would matter. So the waiting time is 1/(n+1) (if we don't know when the last train left, i.e. lamford's second problem).

[gwnn]

Out of curiosity I went back to my old friend Excel and ran a few tests. The expected values of the intervals are (if we sort them before averaging):
1st: 0.0624+/-0.00016
2st: 0.1461+/-0.00023
3rd: 0.2709+/-0.00013
4th: 0.5206+/-0.00023

I hope I didn't mess up the error bars, but anyway, I'm surprised that the expected value of the longest interval is more than 30 minutes long. I'm kind of reminded of the inequality thread here (distributing stuff randomly accounts for more inequality than we would normally expect - though obviously I'm not saying that stuff are distributed randomly in real life!).

[kenberg]

gwnn, on 2014-May-19, 09:09, said:

I thought we all agreed that the waiting time is 15 minutes until you said it was 3/16-th of an hour (11 minutes and 15 seconds). All you need to see this is that you are just interested in the length of the first interval, and it doesn't matter whether you arrive at the top of the hour or somewhere in between, as long as these three trains and the next three will arrive at the same minutes (i.e. the first train and the fourth will be exactly an hour apart, etc). At least I don't see why it would matter. So the waiting time is 1/(n+1) (if we don't know when the last train left, i.e. lamford's second problem).

Ah!!

"as long as these three trains and the next three will arrive at the same minutes

This is exactly what I was not assuming.

I was assuming the trains between 2 and 3 arrived at random times A1, A2, A3 and the trains arriving between 3 and 4 arrive at random times B1, B2, B3 with all six arrival times independent.

I agree that there is no problem if B1 is one hour later than A1. I thought that the point was that the arrival times between 3 and 4 had nothing to do with the arrival times between 2 and 3. it gets easier if there are, effectively, three trains going in a circle at a constant speed of one cycle an hour.

I guess I have not understood this problem from the beginning. Whatever was originally intended, I like my version.