7
$\begingroup$

I'm going to ask a very simple practical question, but I believe it has some interesting mathematical properties.

The simple variant is: trains depart every $x$ minutes and take $y$ minutes to arrive at the destination. How long should a rider expect his journey to take (waiting plus travel)?

The more complex variant is: $n$ train lines service the stop. Each of the $i \in \{1, 2, ... n\}$ lines has trains departing every $x_{i}$ minutes and takes $y_{i}$ minutes to arrive at the destination. Assume arrival times are uncorrelated and random across lines. If the rider takes the first train on any line, what is the expected journey time?

The final, most complex variant: it may be the case that taking the first train on any line is not optimal. (For example, if one of the train lines takes $y_{j} = 30$ minutes to arrive at the next stop while others take 20 minutes, and the waiting times are such that it doesn't make sense to take the slower train anyway.) Unfortunately I'm at a total loss for how to compute this, practically speaking. Mathematically it's minimizing the expectation over all subsets of $\{1, 2, ... n\}$, but I need to actually compute it so any tips would be helpful. This is more of a CS question so perhaps I'll cross-post to another site.

  • 0
    There's a good answer from Ross below, but still some disagreement about how to calculate the expected waiting time; see the comments. Please help!2011-04-20

2 Answers 2

1

For the simple variant, you have a waiting time uniformly distributed in $[0,x]$, so expectation $\frac{x}{2}$, so total time $\frac{x}{2}+y$

Corrected: For a simple version of the more complex variant, suppose there are two lines with uniformly distributed arrival times, but we do not know anything about how they are correlated. On line 1, trains come every 5 minutes and take 40 minutes. On line 2, trains come every 10 minutes and take 37 minutes. On average $\frac{1}{5}+\frac{1}{10}$ trains arrive every minute, so your average waiting time is $\frac{5}{3}$ minutes. Then the chance you take a train on line 2 is $\frac{1}{4}$, $\frac{1}{2}$ that it comes in $5$ minutes times $\frac{1}{2}$ that (given it comes in $5$ minutes) it gets there first. So the total time is $\frac{5}{3}+\frac{3\cdot40}{4}+\frac{37}{4}=40.91$ min.

For your third question (again assuming the arrival times are evenly distributed but uncorrelated), you can look to the first for the expected time for each train. Once you have been waiting $m$ minutes, the expected time for a given train is $\frac{x-m}{2}+y$. When a train arrives, you know how long it will take. If that is less than the expected time of any other train, take it. Otherwise, wait for that one.

  • 0
    Why do you take line 1 two-thirds of the time? Doesn't it depend on how in phase the times are?2011-04-20
  • 0
    @Henry: I was assuming the arrivals are uncorrelated (which I will add). Then in 5 min you will see a train on line 1 and have 1/2 chance of seeing one on line 2.2011-04-20
  • 0
    If you are assuming the arrivals are random (say a Poisson process), I could understand that, but elsewhere you are assuming they are regular (e.g. earlier using $\frac{x}{2}$ rather than $x$). To get two-thirds, you need train 2 to arrive 3 minutes and 20 seconds after a train 1 rather than 2 minutes and 30 seconds, which is not obvious to me.2011-04-20
  • 0
    @Henry: no, I am assuming each train comes regularly, but you don't know how they are correlated. So when you get to the station, you know there will be a train on track 1 within $x$ minutes, evenly distributed. If track 2 has a spacing $x_2$, that is also evenly distributed in $[0,\frac{x_2}{2}]$ but we have no information on the relative phasing. I agree that one could make different assumptions.2011-04-20
  • 0
    @ross: I think you will find that if you take that approach and do the integrations, you may find the expected time is 41 minutes and 20 seconds rather than the 41 minutes and 30 seconds you gave originally. Not really important.2011-04-20
  • 0
    @Henry: in transit, I realized that the first arrival times are not uniformly distributed in 5 min. But that also perturbs the ratio of times you take each train. See the correction. I am still not sure about the third piece.2011-04-20
  • 0
    Thanks Ross, this is a very helpful answer. In my case, for the "which trains to take" question I need to come up with a set of trains before waiting occurs (since it's for a directions algorithm)... any advice is appreciated, but you've already set me on the right path.2011-04-20
  • 0
    Also, one thing. You say $\frac{1}{5}+\frac{1}{10} = \frac{3}{10}$ trains per minute implies $\frac{10}{3}$ min expected waiting time. But doesn't this imply for the simple one-line case, $\frac{1}{5}$ trains per minute implies $5$ min expected waiting time (clearly wrong)? Shouldn't it be $\frac{5}{3}$ minutes expected waiting time for the two-trains case?2011-04-20
  • 0
    @Adam: good catch. I have corrected.2011-04-20
  • 1
    @Adam, @Ross: I think you will find that the expected waiting time is $\frac{25}{12}$ minutes, i.e. 2 minutes and 5 seconds if the two trains are randomly out of phase.2011-04-20
  • 0
    @Henry OK. Do you have a link to any relevant info online that I can read up on to understand it?2011-04-20
1

Your first question is easy: $\frac{x}{2}+y$

Your second question does not have enough information. For example, suppose there are two lines $A$ and $B$, trains on line $A$ leave on the hour and take 53 minutes while trains on line $B$ leave at 10 minutes past the hour and take 37 minutes. Then the expected journey time after turning up at random is (I think) 72 minutes (but can be reduced to 67 minutes by never taking the slow train). But if the line $B$ trains change timetables to start leaving at 10 minutes before the hour then the expected journey time is (I think) 61 minutes and 20 seconds (faster than not taking the slow train).

Your third question turns into your second simply by ignoring any train which arrives after but leaves before another train.

  • 0
    Thanks Henry! As you two discussed above, I in fact mean to assume the two lines are uncorrelated so you can't know their relative arrival times...2011-04-20