Monday, December 23, 2013

The Unmarked Bus Stop


This summer I lived in New York City for the first time since 2000. I've lived in New Jersey and New Hampshire since then. Both the City and I have changed enough for me not to remember my way around very well. That got me into trouble a few times -- I would think I knew where I was going, until I was sure I didn't. Once, after getting lost, I found myself waiting at an unfamiliar bus stop hoping to cut back across the city to where I was supposed to meet someone for dinner.

The N.Y.C. bus stop signs -- see an example above -- don't list the bus schedule. This is frustrating. Unless you're a local, you really have no sense of how long you will have to wait. What if that bus line isn't even running today? Yet, after you've been waiting some amount of time, the fact that you've waited has some value as information. You should conclude that, in general, buses are less frequent than you believed when you showed up. But you might also conclude that the coming bus will arrive sooner now than when you had arrived, given that you've been waiting some time without a bus.

Yes, all of this was running through my head as I waited at the bus stop. Let's call it the "unmarked bus stop problem": How long should you expect to wait after you've been waiting at a bus stop? The problem is a basic application of probability theory, but it's Christmastime and the solution is easy but practical.

The actual statement of the problem: Assume that buses show up at your stop according to a Poisson process with rate λ, which is itself unknown. Assume that, initially, all rates are equally likely so that you have a flat prior. As a function of the time you have already waited t, what is the expectation of the amount of time left before the arrival of your bus?

You can make this problem a bit more challenging, too. Almost always, when you get to a bus stop, you're not the only one waiting. What do you do with the information that others are waiting? Is it a sign that buses come infrequently? Or the bus is about to arrive?

Second problem: Assume that bus riders show up at the stop according to a Poisson process with rate μ, itself unknown with a flat prior. Assume that the arrival processes are independent. Assume that, when a bus arrives, all those waiting can always board. How long should you expect to wait given that there are n other people waiting there when you arrive and N waiting after wait-time t? Note: I haven't actually written this one out.

I will post the answer in the comments in a few days.

13 comments:

  1. Pretty sure no-one really believes that all values of lambda are equally likely a priori. Is once every 100,000 years really as likely a priori as once every hour?

    ReplyDelete
    Replies
    1. Don't you dare question the premise of the problem. Kidding, of course. If you adopt a uniform prior for lambda over some interval, so long as the interval is far greater than the wait time, the answer should be close to the flat-prior assumption, right? So my assumption seems harmless.

      Delete
    2. I gather you mean a flat prior for expected wait time, NOT (as stated) a flat prior for Poisson-process rate.

      Delete
  2. Check the bus schedule on your smartphone. Problem solved?

    ReplyDelete
    Replies
    1. See above about not questioning the premise of the problem.

      Delete
  3. Continuing the trend, http://bustime.mta.info/ gives real time bus info, even better than a schedule

    ReplyDelete
  4. Since no one seems interested in actually working the problem, I guess I'll take up the mantle.

    Define L as total wait time and T as time from now to arrival.

    Therefore, L=T+t

    E(L)=λ (Poisson process rate)

    E(T)=E(L-t)=λ-E(t)=λ-t

    This is intuitive because, regardless of the process rate, the expectation of T will fall as t rises. [ dE(T)/dt < 0 ]

    I'm not sure how to approach the second part, as it seems necessary to know precisely what information is gained by knowing how many people are at the stop.

    ReplyDelete
  5. Nope. That's NOT how a Poisson process works. For FIXED rate, λ, the probability that a bus arrives in the next 5 minutes is INDEPENDENT of how long you've been waiting.

    Of course, what we're SUPPOSED to do is apply Bayesian analysis to the (a-priori unknown) rate λ.

    The stated "flat" prior makes no sense (there is no "flat" probability distribution on [0,∞]). Instead, the most natural prior for λ is a Γ-distribution

    p(λ; κ, α) = κ^α λ^{α-1} e^{-κ λ} / Γ(α)

    With this prior, your expected wait time is

    〈T〉= κ / (α-1)

    If you have been waiting for a time t, your POSTERIOR probability distribution for λ takes the simple form

    p(λ; κ+t, α)

    and hence your EXPECTED wait time actually increases

    〈T〉= (κ+t) / (α-1)

    The reason is that, having waited for a time t, your estimation of the expected value for λ has gone DOWN (ie, you expect the bus runs LESS frequently).

    Problem 2 is a bit more intricate. Again, a "flat" prior for the Poisson rates λ, μ makes no sense. You need to choose something more sensible to even get started.

    ReplyDelete
    Replies
    1. "You need to choose something more sensible to even get started."

      As usual, I exaggerate. You can get STARTED on problem 2, without needing to choose a prior distribution for λ, μ. As a first step you need to compute the probability, for fixed λ, μ, that

      1) There are n people at the bus stop when you arrive.
      2) You wait for a time t, with no bus arriving.
      3) During that time, (N-n) more people arrive at the stop.

      The answer is

      P(N, n, t; λ, μ) = e^{-(μ+λ)t} (μ t)^{N-n} / (N-n)! ( μ/(μ+λ) )^n λ/(μ+λ)

      Choosing a prior p(λ, μ), you can then apply Bayes Theorem.

      OBVIOUSLY, there's no such thing as a "flat" prior. And, unlike the previous case (where a Γ-distribution was the "natural" choice), it's not obvious what choice our host has (or should have) in mind.

      Delete
  6. Sigh. Couldn't resist.

    Full solution here.

    ReplyDelete
  7. Wow, this is a pretty nice write-out. I feel kind of bad that I took up the time of a professor of physics to write all that out. All I meant by a "flat prior" was a the improper uniform prior over [0,infty], because I just wanted to think about the likelihood function for lambda. When you do that -- and you can see this in your general solution with kappa = 0 and alpha = 2 -- you get an amusing solution. You should always expect to wait another t after having waited t -- that is, you should always expect to have waited half the amount of time you need to wait.

    I need to write out #2.

    ReplyDelete
  8. I think you need κ > 0 for the integrals to converge. Of course it's true that some quantities have a finite limit as κ→0, but that's a bit deceptive.

    Moreover, it's useful to keep κ as a parameter; whatever value you pick for it in your prior, it changes in your posterior. As you can see from my Problem 3, it's also useful to keep "a" as a parameter, for much the same reason.

    ReplyDelete
  9. Some things have a finite limit as κ→0; others don't. So you have to be a little careful.

    So it's useful to keep κ as a parameter. Similarly, it's useful to keep "a" as a parameter. In Problem 3, you will observe a shift in both κ and a, in going from your prior to your posterior distribution.

    It is true, though, that κ→0, ρ→0 give a particularly simple answer for the posterior expected wait time in Problem 2 (much simpler than the full answer).

    ReplyDelete