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