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

<p>First, we need to prove two theorems.</p>

<p>(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$.</p>

<p>(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$. </p>

<p>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 &gt; t_j$. </p>

<p>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$. </p>

<p>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 &lt; 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$. </p>

CC BY-SA 3.0
2011-04-21T22:20:16.810Z
2011-04-21T22:20:16.810Z
Peter Shor 
<p>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)?</p>

<p>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, <em>and</em> 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.</p>

CC BY-SA 3.0
2011-04-20T14:18:18.260Z
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
Suresh Venkat
CC BY-SA 3.0
2011-04-20T14:25:48.160Z
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 http://math.stackexchange.com/ IMHO.)
Radu GRIGore
CC BY-SA 3.0
2011-04-20T14:29:43.647Z
Oh, it's already on [Math Stackexchange](http://math.stackexchange.com/q/34073/512). Next time, please provide the link yourself.
Radu GRIGore
CC BY-SA 3.0
2011-04-20T15:48:07.933Z
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.
Adam Ernst
CC BY-SA 3.0
2011-04-20T23:49:51.170Z
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.
Peter Shor 
CC BY-SA 3.0
2011-04-22T04:35:40.280Z
@Peter, you're absolutely right. What I failed to state is that the practical application is a directions algorithm. Since the directions need to be simple, I need to choose only a fixed subset and say "Take X, Y, or Z." But your answer is so good I'm well on my way to figuring it out. Thanks!
Adam Ernst
CC BY-SA 3.0
2011-04-22T05:20:23.343Z
@Adam: I suspect the problem changes quite a bit when you assume a Poisson distribution on arrivals, rather than regular arrivals, and neither of these assumptions is going to be completely realistic. So there will probably be a number of reasonable solutions for the real application.
Peter Shor 
CC BY-SA 3.0
2011-04-22T11:19:23.643Z
If you assume a Poisson distribution on arrivals, then there are only $n$ strategies (take any train with travel time is $y_i$ or less), and it's quite straightforward to calculate the expected time taken by any of these strategies. So this does indeed give you a fixed subset.
Peter Shor 
<ds.algorithms>
Expected travel time for regularly departing trains
Adam Ernst
# Expected travel time for regularly departing trains

(Asked by: username_0 on 2011-04-20)

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.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: 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  
> **username_2**: 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 http://math.stackexchange.com/ IMHO.)  
> **username_2**: Oh, it's already on [Math Stackexchange](http://math.stackexchange.com/q/34073/512). Next time, please provide the link yourself.  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_0**: @Peter, you're absolutely right. What I failed to state is that the practical application is a directions algorithm. Since the directions need to be simple, I need to choose only a fixed subset and say "Take X, Y, or Z." But your answer is so good I'm well on my way to figuring it out. Thanks!  
> **username_3**: @Adam: I suspect the problem changes quite a bit when you assume a Poisson distribution on arrivals, rather than regular arrivals, and neither of these assumptions is going to be completely realistic. So there will probably be a number of reasonable solutions for the real application.  
> **username_3**: If you assume a Poisson distribution on arrivals, then there are only $n$ strategies (take any train with travel time is $y_i$ or less), and it's quite straightforward to calculate the expected time taken by any of these strategies. So this does indeed give you a fixed subset.  

---

## 1 answers

### Answer by username_3 on 2011-04-21. Score: 3 | Accepted answer

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$.


---

