Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Sometimes, regardless of the mathematics, the next bus seems to never come. –  Asaf Karagila Mar 23 '13 at 19:13

2 Answers 2

up vote 1 down vote accepted

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: \begin{equation} f_X(t|N=k)=\frac{P(N=k|X=t)}{P(N=k)}f_X(t) \end{equation} $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: \begin{equation} 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) \end{equation} We can now write $f_X(t|N=k)$ as: \begin{equation} f_X(t|N=k)=\frac{\lambda}{P(N(n)>k)}e^{-\lambda n}\frac{(\lambda t)^k}{k!}1_{[0,n]} \end{equation}

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:

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

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

enter image description here

share|improve this answer
    
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). $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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