# When does the next bus come?

People arrive at a bus stop according to a Poisson process at rate $\lambda$ per minute. The bus leaves every $n$ minutes, but you have no idea when the last bus left. You observe that there are $k$ people waiting at the stop. Given this information, when do you expect the next bus to arrive?

Part of me says this is elementary. But I can't think of where to even begin solving it.

-
Sometimes, regardless of the mathematics, the next bus seems to never come. –  Asaf Karagila Mar 23 '13 at 19:13

This is a nice question, probably not as simple as it sounds, I'll give it a try. It is a Bayesian problem, when you arrive at the bus stop, you have no idea about when the last bus passed, so your prior on the distribution of the elapsed time $X$ since the bus last passed is uniform over $[0,n]$. As you observe the number of people in the queue, you update your distribution of $X$ to form a posterior distribution.

Let $f_X$ be the pdf of $X$ and $N$ the random variable describing the number of people in the queue. Bayes theorem states that: $$f_X(t|N=k)=\frac{P(N=k|X=t)}{P(N=k)}f_X(t)$$ $f_X(t)$ corresponds to your prior and thus reads $f_X(t)=\frac{1}{n}1_{[0,n]}$; and $P(N|X=t)$ is exponentially distributed with rate $\lambda$ so $P(N=k|X=t)=e^{-\lambda t}\frac{(\lambda t)^k}{k!}$.

$P(N=k)$ can be obtained equivalently by using the law of total probability or by observing that it must be so that $\int_{0}^1 f_X(t|N=k)dt=1$. Either way, we obtain: \begin{align} I_k:=P(N=k)&=\frac{1}{n}\int_0^n e^{-\lambda t}\frac{(\lambda t)^k}{k!}dt\\ &=\frac{1}{n}\left(\left[-\frac{e^{-\lambda t}}{\lambda}\frac{(\lambda t)^k}{k!}\right]_0^n+\int_0^n e^{-\lambda t}\frac{(\lambda t)^{k-1}}{(k-1)!}\right)\\ &=-\frac{e^{-\lambda n}(\lambda n)^{k-1}}{k!}+I_{k-1}\\ &=I_0-e^{-\lambda n}\sum_{i=1}^{k-1}\frac{(\lambda n)^{i}}{i!}\\ &=I_0+e^{-\lambda n}-e^{-\lambda n}\sum_{i=0}^{k-1}\frac{(\lambda n)^{i}}{i!} \end{align} Since $I_0=\frac{1}{\lambda n}(1-e^{-\lambda n})$, we get: $$I_k=\frac{1}{\lambda n}\left(1-e^{-\lambda n}\sum_{i=0}^{k-1}\frac{(\lambda n)^{i}}{i!}\right)=\frac{1}{\lambda n}P(N(n)>k)$$ We can now write $f_X(t|N=k)$ as: $$f_X(t|N=k)=\frac{\lambda}{P(N(n)>k)}e^{-\lambda n}\frac{(\lambda t)^k}{k!}1_{[0,n]}$$

We may now compute the expected elapsed time since the bus last passed: \begin{align} E[X|N=k]&=\int_0^n t f_X(t|N=k)dt\\ &=\frac{1}{P(N(n)>k)} \int_0^n e^{-\lambda n}\frac{(\lambda t)^{k+1}}{k!}dt\\ &=\frac{(k+1)}{P(N(n)>k)} \int_0^n e^{-\lambda n}\frac{(\lambda t)^{k+1}}{(k+1)!}dt \end{align} We observe that the integral in the last equality is equal to $nI_{k+1}=\frac{1}{\lambda}P(N(n)>k+1)$, whence:

$$E[X|N=k]=\frac{k+1}{\lambda}\frac{P(N(n)>k+1)}{P(N(n)>k)}$$

The expected waiting time is then given by $n-E[X|N=k]$.

As an illustration, I have let $n=20$ minutes and $\lambda=3$ people/min and obtained the following graph, which seems to make a lot of sense

-
This is awesome and exactly what I was looking for. Just working through it now. Thanks! –  crf Mar 27 '13 at 5:03

Let $X$ be the time (in minutes) since the last bus left. I think you need to assume that $X$ is uniformly distributed over $\{1,...,n \}$. We know that $N$, the number of people waiting when you arrive at the bus stop, has Poisson distribution $\mathcal P(\lambda X)$. So what you want to calculate is $$\mathbb E(n - X \vert N = k) = n - \sum_{j=1}^n \ j \ \mathbb P(X = j \vert N = k).$$

-