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.

  • $\begingroup$ 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! $\endgroup$ – Adam Ernst Apr 20 '11 at 19:27

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.

  • $\begingroup$ Why do you take line 1 two-thirds of the time? Doesn't it depend on how in phase the times are? $\endgroup$ – Henry Apr 20 '11 at 14:15
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Apr 20 '11 at 14:18
  • $\begingroup$ 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. $\endgroup$ – Henry Apr 20 '11 at 14:27
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Apr 20 '11 at 14:31
  • 1
    $\begingroup$ @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. $\endgroup$ – Henry Apr 20 '11 at 16:29

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.

  • $\begingroup$ 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... $\endgroup$ – Adam Ernst Apr 20 '11 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.