1
$\begingroup$

First a simple mathematical question: Suppose $n$ train lines service a train station. 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. If the rider takes the first train on any line, what is the expected journey time (waiting + travel)?

Secondly: 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 algorithmically. 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.

$\endgroup$
8
  • $\begingroup$ I'm assuming the "expectation" is over a uniformly distributed variable determining when the rider arrives at the station ? Because the train schedules appear to be deterministic $\endgroup$ Apr 20, 2011 at 14:18
  • $\begingroup$ Under some assumptions, the waiting time until the first train is $P(Z<z)=1-\sum_k(x_k-z)/x_k$. (This question seems more suitable for math.stackexchange.com IMHO.) $\endgroup$ Apr 20, 2011 at 14:25
  • 3
    $\begingroup$ Oh, it's already on Math Stackexchange. Next time, please provide the link yourself. $\endgroup$ Apr 20, 2011 at 14:29
  • 1
    $\begingroup$ Sorry about forgetting the link to the Math SE question. I'm posting here specifically for the second question: how to solve the minimization problem algorithmically. $\endgroup$
    – Adam Ernst
    Apr 20, 2011 at 15:48
  • 3
    $\begingroup$ Why is it equivalent to maximizing over all subsets? Suppose you have train A, which comes every 12 minutes, and takes 60 minutes to reach the destination, and train B, which comes every 12 minutes and takes 59 minutes to reach the destination. If you arrive at the station, and see train A about to depart, you should get on it, because if you don't, you expect to wait 6 minutes for train B. However, if you've already waited 11 minutes, and train A shows up, you should pass on it, because train B will show up in the next minute. So even in this simple situation, it's complicated. $\endgroup$ Apr 20, 2011 at 23:49

1 Answer 1

3
$\begingroup$

Here's a way you can find the optimal algorithm. Let's assume (for convenience) that all $x_i$ and $y_i$ are distinct.

First, we need to prove two theorems.

(1) If at time $t$, you would get on a train with travel time $y_i$, you would also get on any train with travel time less than $y_i$.

(2) If you would get on train $j$ at time $t_j$, you would also get on that train $j$ at any time $t \leq t_j$.

For (1), the proof is easy. For (2), the proof is based on the observation that the longer you wait, the higher the probability that any particular train shows up. So if there's some strategy of waiting for trains other than $j$ that has better performance than getting on a train $j$ with travel time $y_j$ at time $t_j$, that same strategy is going to give travel time $\leq y_j$ for all times $t > t_j$.

Now, if train $\alpha$ is the train with minimum $y_\alpha$, then you want to get on this train any time it arrives. Furthermore, if you've waited $x_\alpha - \epsilon$ time for sufficiently small $\epsilon$, your optimal strategy is to wait for train $\alpha$.

What we're going to do now is essentially continuous dynamic programming. If you've waited for time $t$, there are only $n$ possible optimal strategies. That is, get on any train with travel time $\leq y_i$. This optimal strategy changes at $n$ or fewer values of $t$. So, starting with time $x_\alpha$ and the strategy "wait for train $y_\alpha$", calculate the first time $t < x_\alpha$ where the strategy changes. You can do this by comparing $n$ possible strategies, each of which gives an expected travel time which is a function of $t$. Keep working to the left in this fashion, until you get to time $t= 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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