20

I came across an interview question:

There is a red train that is coming every 10 mins. There is a blue train coming every 15 mins. Both of them start from a random time so you don't have any schedule. If you arrive at the station at a random time and go on any train that comes the first, what is the expected waiting time?

amoeba
  • 93,463
  • 28
  • 275
  • 317
Shengjie Zhang
  • 243
  • 2
  • 8
  • 3
    Do the trains arrive on time but with unknown equally distributed phases, or do they follow a poisson process with means 10mins and 15mins. – Dale C Sep 27 '17 at 00:14
  • 1
    The former one, not poisson. – Shengjie Zhang Sep 27 '17 at 00:30
  • 7
    @Tilefish makes an important comment that everybody ought to pay attention to. **There is no definite answer.** You have to assume what "start from a random time" might mean. (Does it mean they start simultaneously or that they start at different unknown times? What would justify treating "unknown" as a random variable with a definite known distribution?) As a function of their phase difference (which matters only modulo 5 minutes), the answer can vary from $15/4$ to $25/6$. A uniform distribution of the phase difference would yield $35/9$. – whuber Sep 27 '17 at 19:23
  • @whuber everyone seemed to interpret OP's comment as if two buses started at two different random times. That they would start at the same random time seems like an unusual take – Aksakal Sep 27 '17 at 22:03
  • 1
    @Aksakal. Not everybody: I don't and at least one answer in this thread does not--that's why we're seeing different numerical answers. Moreover, almost nobody acknowledges the fact that they had to make some such an interpretation of the question in order to obtain an answer. – whuber Sep 28 '17 at 14:01

6 Answers6

15

One way to approach the problem is to start with the survival function. In order to have to wait at least $t$ minutes you have to wait for at least $t$ minutes for both the red and the blue train. Thus the overall survival function is just the product of the individual survival functions:

$$ S(t) = \left( 1 - \frac{t}{10} \right) \left(1-\frac{t}{15} \right) $$

which, for $0 \le t \le 10$, is the the probability that you'll have to wait at least $t$ minutes for the next train. This takes into account the clarification of the the OP in a comment that the correct assumptions to take are that each train is on a fixed timetable independent of the other and of the traveller's arrival time, and that the phases of the two trains are uniformly distributed,

Then the pdf is obtained as

$$ p(t) = (1-S(t))' = \frac{1}{10} \left( 1- \frac{t}{15} \right) + \frac{1}{15} \left(1-\frac{t}{10} \right) $$

And the expected value is obtained in the usual way:

$E[t] = \int_0^{10} t p(t) dt = \int_0^{10} \frac{t}{10} \left( 1- \frac{t}{15} \right) + \frac{t}{15} \left(1-\frac{t}{10} \right) dt = \int_0^{10} \left( \frac{t}{6} - \frac{t^2}{75} \right) dt$,

which works out to $\frac{35}{9}$ minutes.

Dave
  • 3,109
  • 15
  • 23
  • Dave, can you explain how p(t) = (1- s(t))' ? – Chef1075 Sep 27 '17 at 06:34
  • I can explain that for you S(t)=1-F(t), p(t) is just the f(t)=F(t)'. – Deep North Sep 27 '17 at 06:41
  • 4
    The survival function idea is great. But why derive the PDF when you can directly integrate the survival function to obtain the expectation? In effect, two-thirds of this answer merely demonstrates the fundamental theorem of calculus with a particular example. And what justifies using the product to obtain $S$? There's a hidden assumption behind that. – whuber Sep 27 '17 at 19:22
  • 2
    @whuber I prefer this approach, deriving the PDF from the survival function, because it correctly handles cases where the domain of the random variable does not start at 0. – Dave Sep 27 '17 at 19:47
  • 2
    (1) Your domain is positive. (2) The formula is [readily generalized.](https://stats.stackexchange.com/a/222497/919). – whuber Sep 27 '17 at 19:50
9

The answer is $$E[t]=\int_x\int_y \min(x,y)\frac 1 {10} \frac 1 {15}dx dy=\int_x\left(\int_{y<x}ydy+\int_{y>x}xdy\right)\frac 1 {10} \frac 1 {15}dx$$ Get the parts inside the parantheses: $$\int_{y<x}ydy=y^2/2|_0^x=x^2/2$$ $$\int_{y>x}xdy=xy|_x^{15}=15x-x^2$$ So, the part is: $$(.)=\left(\int_{y<x}ydy+\int_{y>x}xdy\right)=15x-x^2/2$$ Finally, $$E[t]=\int_x (15x-x^2/2)\frac 1 {10} \frac 1 {15}dx= (15x^2/2-x^3/6)|_0^{10}\frac 1 {10} \frac 1 {15}\\= (1500/2-1000/6)\frac 1 {10} \frac 1 {15}=5-10/9\approx 3.89$$

Here's the MATLAB code to simulate:

nsim = 10000000;
red= rand(nsim,1)*10;
blue= rand(nsim,1)*15;
nextbus = min([red,blue],[],2);
mean(nextbus)
Aksakal
  • 55,939
  • 5
  • 90
  • 176
  • 1
    You're making incorrect assumptions about the initial starting point of trains. i.e. Using your logic, how many red and blue trains come every 2 hours? How many trains in total over the 2 hours? etc. – Dale C Sep 27 '17 at 03:22
  • 1
    Can trains not arrive at minute 0 and at minute 60? – Dale C Sep 27 '17 at 03:28
  • 1
    what about if they start at the same time is what I'm trying to say. What if they both start at minute 0. How many instances of trains arriving do you have? – Dale C Sep 27 '17 at 03:33
  • +1 change your simulation to R nsim = 10000000 red= runif(nsim,0,10) blue= runif(nsim,0,15) nextbus = pmin(red, blue) mean(nextbus) – Deep North Sep 27 '17 at 04:54
  • 1
    The simulation does not exactly emulate the problem statement. In particular, it doesn't model the "random time" at which *you* appear at the bus station. As such it embodies several unstated assumptions about the problem. – whuber Sep 27 '17 at 21:18
  • 2
    @whuber it emulates the phase of buses relative to my arrival at the station – Aksakal Sep 27 '17 at 21:40
  • 1
    Right--and in so doing, it makes a critical assumption about their relative starting times. The answer depends on that. It very well could have been different. This is one reason why simulations ought to try their best to model the problem *exactly* rather than relying on such intuitive leaps of understanding, A good simulation not only can be convincing because of the faithful way it models a process, but it can also surprise you by revealing, through its deviation from what you expect, assumptions you might not have realized you were making. – whuber Sep 27 '17 at 21:50
4

Assuming each train is on a fixed timetable independent of the other and of the traveller's arrival time, the probability neither train arrives in the first $x$ minutes is $\frac{10-x}{10} \times \frac{15-x}{15}$ for $0 \le x \le 10$, which when integrated gives $\frac{35}9\approx 3.889$ minutes

Alternatively, assuming each train is part of a Poisson process, the joint rate is $\frac{1}{15}+\frac{1}{10}=\frac{1}{6}$ trains a minute, making the expected waiting time $6$ minutes

Henry
  • 30,848
  • 1
  • 63
  • 107
  • Just integrating the survival function doesn't provide the correct answer for general probability distributions. – Dave Sep 27 '17 at 10:56
  • 3
    @Dave it's fine if the support is nonnegative real numbers. – Neil G Sep 27 '17 at 12:03
  • @NeilG would this approach work if there were only one train? Or if inter-train time were Poisson distributed? I don't see how it could. – Dave Sep 27 '17 at 12:21
  • 3
    @dave He's missing some justifications, but it's the right solution as long as you assume that the trains arrive is uniformly distributed (i.e., a fixed schedule with known constant inter-train times, but unknown offset). It works with any number of trains. This is the because the expected value of a nonnegative random variable is the integral of its survival function. – Neil G Sep 27 '17 at 12:36
  • 1
    @Dave with one train on a fixed $10$ minute timetable independent of the traveller's arrival, you integrate $\frac{10-x}{10}$ over $0 \le x \le 10$ to get an expected wait of $5$ minutes, while with a Poisson process with rate $\lambda=\frac1{10}$ you integrate $e^{-\lambda x}$ over $0 \le x \lt \infty$ to get an expected wait of $\frac1\lambda=10$ minutes – Henry Sep 27 '17 at 13:19
  • 1
    @NeilG TIL that "the expected value of a non-negative random variable is the integral of the survival function", sort of -- there is some trickiness in that the domain of the random variable needs to start at $0$, and if it doesn't intrinsically start at zero(e.g. for a different problem where the inter-arrival times were, say, uniformly distributed between 5 and 10 minutes) you actually have to use a lower bound of 0 when integrating the survival function. (starting at 0 is required in order to get the boundary term to cancel after doing integration by parts) – Dave Sep 27 '17 at 13:43
  • 3
    +1 At this moment, this is the unique answer that is explicit about its assumptions. *All* the others make some critical assumptions without acknowledging them. – whuber Sep 27 '17 at 19:24
2

I am probably wrong but assuming that each train's starting-time follows a uniform distribution, I would say that when arriving at the station at a random time the expected waiting time for:

  1. the $R$ed train is $\mathbb{E}[R] = 5$ mins
  2. the $B$lue train is $\mathbb{E}[B] = 7.5$ mins
  3. the train that comes the first is $\mathbb{E}[\min(R,B)] =\frac{15}{10}(\mathbb{E}[B]-\mathbb{E}[R]) = \frac{15}{4} = 3.75$ mins

As pointed out in comments, I understood "Both of them start from a random time" as "the two trains start at the same random time". Which is a very limiting assumption.
keepAlive
  • 849
  • 1
  • 7
  • 17
2

Suppose that red and blue trains arrive on time according to schedule, with the red schedule beginning $\Delta$ minutes after the blue schedule, for some $0\le\Delta<10$. For definiteness suppose the first blue train arrives at time $t=0$.

Assume for now that $\Delta$ lies between $0$ and $5$ minutes. Between $t=0$ and $t=30$ minutes we'll see the following trains and interarrival times: blue train, $\Delta$, red train, $10$, red train, $5-\Delta$, blue train, $\Delta + 5$, red train, $10-\Delta$, blue train. Then the schedule repeats, starting with that last blue train.

If $W_\Delta(t)$ denotes the waiting time for a passenger arriving at the station at time $t$, then the plot of $W_\Delta(t)$ versus $t$ is piecewise linear, with each line segment decaying to zero with slope $-1$. So the average wait time is the area from $0$ to $30$ of an array of triangles, divided by $30$. This gives $$ \begin{align}\bar W_\Delta &:= \frac1{30}\left(\frac12[\Delta^2+10^2+(5-\Delta)^2+(\Delta+5)^2+(10-\Delta)^2]\right)\\&=\frac1{30}(2\Delta^2-10\Delta+125). \end{align}$$ Notice that in the above development there is a red train arriving $\Delta+5$ minutes after a blue train. Since the schedule repeats every 30 minutes, conclude $\bar W_\Delta=\bar W_{\Delta+5}$, and it suffices to consider $0\le\Delta<5$.

If $\Delta$ is not constant, but instead a uniformly distributed random variable, we obtain an average average waiting time of $$ \frac15\int_{\Delta=0}^5\frac1{30}(2\Delta^2-10\Delta+125)\,d\Delta=\frac{35}9.$$

grand_chat
  • 2,632
  • 1
  • 8
  • 11
2

This is a Poisson process. The red train arrives according to a Poisson distribution wIth rate parameter 6/hour.
The blue train also arrives according to a Poisson distribution with rate 4/hour. Red train arrivals and blue train arrivals are independent. Total number of train arrivals Is also Poisson with rate 10/hour. Since the sum of The time between train arrivals is exponential with mean 6 minutes. Since the exponential mean is the reciprocal of the Poisson rate parameter. Since the exponential distribution is memoryless, your expected wait time is 6 minutes.

Alison
  • 21
  • 1