Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

December 28, 2013

The Bus Stop Problems

Since we had so much fun with Bayes Theorem in a recent post, I can’t resist another.

Young Economics whippersnapper Evan Soltas posed two problems to do with Bayesian probability:

  1. You arrive at a bus stop in an unfamiliar part of town. Assume that buses arrive at the stop as a Poisson process, with an unknown (to you) rate, λ\lambda. You don’t know λ\lambda, but say you have a prior probability distribution for it, p 0(λ)p_0(\lambda).
    • What’s your expected wait time, T\langle T\rangle, for the next bus to arrive?
    • Say you’ve been waiting for a time tt. What’s your posterior probability distribution, p(λ)p(\lambda), and what’s your new expected wait time?
  2. Let’s add some more information. Say that riders arrive at the bus stop via an independent Poisson process with an (unknown to you) rate, μ\mu. Whenever a bus arrives, all those waiting at the stop get on it. Thus, the number of people waiting is the number who arrived since the last bus. Say you arrive at the stop to find nn people already waiting. You wait for a time, tt, at which point there are NN other people waiting at the stop (i.e., NnN-n arrived while you were waiting).
    • Given this data, what’s your posterior probability distribution, p(λ,μ)p(\lambda,\mu)?
    • What’s your new expected wait time, T\langle T\rangle?

These questions illustrate one of my favourite points of view on Bayes Theorem, namely that it induces a flow on the (infinite-dimensional!) space of probability distributions. Understanding the nature of that flow is, I think, the key task of the subject.

Infinite dimensions are hard to get an intuition for, so one of the first tasks is to cut the problem down to a finite-dimensional one.

Say we have a finite-dimensional family of probability distributions. We will call that family natural for the problem at hand, if the Bayes flow keeps us within that finite dimensional space.

A natural family of probability distributions for Problem 1 is the Γ\Gamma-distribution. Let us choose a prior in that family p 0(λ)=f(λ;κ,a)=κ aλ a1e κλΓ(a) p_0(\lambda) = f(\lambda; \kappa, a) = \frac{\kappa^a \lambda^{a-1} e^{-\kappa\lambda}}{\Gamma(a)} where, for reasons that will be apparent in a moment, we require κ>0,a>1\kappa\gt 0,\, a\gt 1. For fixed λ\lambda, the expected wait time is 0 dτe λτλτ=1λ \int_0^\infty d\tau e^{-\lambda \tau} \lambda\tau= \frac{1}{\lambda} So, given our prior, we expect to wait T= 0 dλp 0(λ)λ=κa1 \langle T\rangle = \int_0^\infty d\lambda \frac{p_0(\lambda)}{\lambda} = \frac{\kappa}{a-1}

Applying Bayes Theorem, our posterior distribution, after waiting a time tt, is p(λ;t) =e λtp 0(λ) 0 dλe λtp 0(λ) =f(λ;κ+t,a) \begin{split} p(\lambda; t) &= \frac{e^{-\lambda t} p_0(\lambda)}{\int_0^\infty d\lambda' e^{-\lambda' t} p_0(\lambda')}\\ &= f(\lambda; \kappa+t, a) \end{split} which, as announced, is just a shift of parameters of the Γ\Gamma-distribution. We immediately conclude that our expected wait time T=κ+ta1 \langle T\rangle = \frac{\kappa+t}{a-1} has gone up. The longer we wait, the longer we expect to continue having to wait!

You should pause to convince yourself that’s the generic behaviour, whatever prior you assumed.

What about Problem 2? The first task is to compute, for fixed rates, λ,μ\lambda,\mu, the probability that

  • There are nn people waiting at the stop, when you arrive.
  • You wait for a time, tt, during which
    • no bus arrives, but
    • NnN-n more riders arrive.

The answer is P(N,n;λ,μ)=e (λ+μ)t(μt) Nn(Nn)!μ nλ(λ+μ) n+1 P(N,n; \lambda,\mu) = e^{-(\lambda+\mu)t} \frac{{(\mu t)}^{N-n}}{(N-n)!}\, \frac{\mu^n \lambda}{{(\lambda+\mu)}^{n+1}}

The second task is to find a natural family of probability distributions for this problem. I don’t know its name, but there is an obvious 5-parameter family, which is the natural generalization of the Γ\Gamma-distribution, p 0(λ,μ) =g(λ,μ;κ,ρ,a,b,c) =κ a+cρ bΓ(a+c)Γ(b)F1 2 (b,c,1ac;κ/ρ)λ a1μ b1(λ+μ) ce (κλ+ρμ) \begin{split} p_0(\lambda, \mu) &= g(\lambda,\mu;\kappa,\rho, a,b,c)\\ &= \frac{\kappa^{a+c}\rho^b}{\Gamma(a+c)\Gamma(b)\multiscripts{_2}{F}{_1}(b,-c,1-a-c;\kappa/\rho)}\, \lambda^{a-1} \mu^{b-1} {(\lambda+\mu)}^c e^{-(\kappa\lambda+\rho\mu)} \end{split} Note that

  • For c=0c=0, this is just a product of independent Γ\Gamma-distributions. g(λ,μ;κ,ρ,a,b,0)=f(λ;κ,a)f(μ;ρ,b) g(\lambda,\mu;\kappa,\rho,a,b,0) = f(\lambda;\kappa,a)f(\mu;\rho,b)
  • For positive integer cc, the hypergeometric function is just a finite-order polynomial F1 2 (b,c,1ac;x)=1(a) c k=0 c(b1) k(a) ck(c k)x k \multiscripts{_2}{F}{_1}(b,-c,1-a-c;x) = \frac{1}{{(a)}_c} \sum_{k=0}^c {(b-1)}_k {(a)}_{c-k}\begin{pmatrix}c\\ k\end{pmatrix} x^k
  • There’s an obvious symmetry λμ κρ ab \begin{gathered} \lambda\leftrightarrow\mu \\ \kappa\leftrightarrow\rho \\ a\leftrightarrow b \end{gathered}

Applying Bayes Theorem, the posterior probability is p(λ,μ;N,n,t)=g(λ,μ;κ+t,ρ+t,a+1,b+N,cn1) p(\lambda,\mu; N,n,t) = g(\lambda,\mu;\kappa+t,\rho+t , a+1,b+N,c-n-1) which, again, is just a shift of parameters of the distribution. The expected wait time T=κa+c1F1 2 (b,c,2ac;κ/ρ)F1 2 (b,c,1ac;κ/ρ) \langle T\rangle = \frac{\kappa}{a+c-1} \frac{\multiscripts{_2}{F}{_1}(b,-c,2-a-c;\kappa/\rho)}{\multiscripts{_2}{F}{_1}(b,-c,1-a-c;\kappa/\rho)} transforms accordingly. The dependence on N,n,tN,n,t is, alas, somewhat complicated. You can spend some hours convincing yourself that it is what you should expect.

Whether you think a Poisson process is a good model for a real public transit systems, probably depends on your political persuasion.


Update: 12/29/2013

In return, I should pose the followup problem:

  1. Same setup as Problem 1 but, now, you’ve been to the bus stop nn times previously and had to wait for times {t 1,t 2,,t n}\{t_1,t_2,\dots,t_n\}. What is your posterior probability distribution for λ\lambda (hint: the Γ\Gamma-distribution is natural for this problem, too), and what is your expected wait time?
Posted by distler at December 28, 2013 4:42 PM

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2679

4 Comments & 0 Trackbacks

Re: The Bus Stop Problems

Regarding the first problem, and the fact that the expected waiting time increases, I find it very fascinating that it implies that a rational agent might decide to try waiting for the bus for a while and then give up and choose to walk when the expected wait time exceeds the time that it takes to walk.

I was forced to ponder the exact same problem during my school years and never figured this out…

Posted by: Andrea Censi on January 15, 2014 12:26 AM | Permalink | Reply to this

Re: The Bus Stop Problems

I find it very fascinating that it implies that a rational agent might decide to try waiting for the bus for a while and then give up and choose to walk when the expected wait time exceeds the time that it takes to walk.

I believe that people regularly behave in exactly that fashion, whether or not they actually perform the above calculation.

Similarly, I think the expected wait time, T\langle T\rangle, in Problem 3 does exactly what you’d expect it to do, even if you never thought of it in terms of a sequence of Γ\Gamma-distributions.

P.S.: Congratulations on the MIT job!

Posted by: Jacques Distler on January 15, 2014 8:52 AM | Permalink | PGP Sig | Reply to this

Re: The Bus Stop Problems

Very interesting article. You might have touched the most important issue of physics. John Ellis (at Royal Society conference earlier this week) told LiveScience ““I’m not giving up on supersymmetry. Individual physicists have to make their own choices, but I am not giving up. … And if the LHC’s next run does fail to reveal any sparticles, there is still no reason to give up on looking for them. In that case, new colliders with even higher energies should be built, for collisions at energies as high as 100 TeV.”

You calculation and conclusion that “The longer we wait, the longer we expect to continue having to wait! You should pause to convince yourself that’s the generic behaviour, whatever prior you assumed” could be the best description of Ellis’ belief and behavior.

Your bus stop problem is truly a very important issue. Is the bus arriving schedule independent of riders ‘expectation’ and ‘behavior’? If we change your statement very slightly to “The longer we wait, the longer we must wait” (which can be easily read as such by someone), then seemingly the bus schedule is a function (depending upon) of the riders’ wait-time. From here, someone can conclude that the bus schedule is not an ontological reality.

I am not exaggerating this problem. With the 50 years of long history of the mainstream physics which has failed to make any contact on ‘realities’ by the paradigm-theories (SUSY, M-string theory and all those BSM theories), the only way out for this long failure is to discredit ‘reality’ of nature as an ontological reality while claims that the major mission (task) of physics is ‘model building’, not truth searching. Thus, the central paradigm of physics today is that “But what is the full and absolute ‘reality’? It cannot be such thing in physics, it is just beyond the definition of physics. (See http://www.quantumdiaries.org/2014/01/10/realism-in-science/#comment-169030 ).”

The key issue here is that:
Is the bus arriving schedule an ontological reality, independent of the riders wait-time (regardless of his ‘expectation’?
Is the nature having a reality, independent of the models?

‘Expectation’ and ‘behavior’ are conscious activities which involve the ‘free will’ actions. Are these free will actions now play an important role in the laws of physics?

Posted by: Tienzen (Jeh-Tween) Gong on January 26, 2014 1:49 PM | Permalink | Reply to this

Re: The Bus Stop Problems

You might have touched the most important issue of physics. John Ellis (at Royal Society conference earlier this week) told LiveScience …

If anything I wrote here led you to that conclusion, then I apologize for having confused you.

In any case, you are truly and profoundly confused (both with respect to the topic at hand and with respect to physics).

Your bus stop problem is truly a very important issue. Is the bus arriving schedule independent of riders ‘expectation’ and ‘behavior’?

Yes.

I suggest you Google “Poisson Process”.

From here, someone can conclude that the bus schedule is not an ontological reality.

No.

I suggest you Google “Bayes Theorem”.

Posted by: Jacques Distler on January 26, 2014 3:15 PM | Permalink | PGP Sig | Reply to this

Post a New Comment