Sunday, February 05, 2012

Two Dilemmas

The Train Dilemma:
If you run to catch a train which from a distance you saw pull into the station, it will depart just as you arrive. Next time, you will believe you can't catch it, and you will walk. If you walk to the station believing you can't catch the train, it will still depart just as you arrive. You will believe that if you had run you would have caught it, so next time, you will run. Ad infinitum.

Assume that all other things being equal, walking is preferable to running.

run_speed >> walk_speed
distance / run_speed = "t_to_departure" + epsilon (very small interval), therefore just walk
distance / walk_speed = "t_to_departure" + epsilon, therefore run

The illusion here, or the problem in reasoning, is that the departure time of the train is somehow correlated with your decision to run or walk. If this is so, then the correct solution is to retain your dignity and walk coolly to the station every time. But it is unlikely that this is so.

Clearly the solution to this problem is to run every time, but it might take you a few failures to convince yourself of that. I've been in this situation many times on the way home from TKD, walking down the alley off Brookline that leads to Fenway Station; that's exactly where the D-Train comes out of the underground, and if when I get to the end of the alley I hear a distant screeching of metal wheels on metal rails, I know the train is coming, and I know I should start running.

The Bus Dilemma:
Let's say you have multiple paths to a destination, one of which includes a bus ride, but you don't know the schedule, only that the bus comes at a certain interval.

The dilemma here is whether or not to take your other option. Often, you might feel that you have committed enough time to waiting for the bus that you should abandon other options and just wait until the next one comes - otherwise, you've wasted all that time.

If the following propositions are true, then the dilemma occurs:
1. time_by_bus < time_by_other
2. time_by_bus + bus_period > time_by_other
3. bus_phase is unknown or undependable

If these are true, then it can be hard to decide just what to do. Keep waiting, or take the other route?

Again, the answer is probabilistic. If the bus phase is unknown, we can represent 'wait time' as a uniformly distributed random variable in the interval [0 bus_period]. We can then combine the after-weight travel times for the bus and the other route in the following way:

t_wasted = rand[0 bus_period] + t_bus - t_other

If t_wasted is positive, then the wait was too long and time would have been saved by taking the other route. If it's negative, then the wait was worth it, and time was saved by taking the bus. How do you use this to decide what to do? First off, look at what happens if t_bus and t_other are equal - in that case, t_wasted will always be positive, i.e. it makes no sense to wait at all, and you should take the other route every time.

At the very least, you want to break even on average. To do this, (t_bus - t_other) has to be equal to negative half the bus period, i.e. taking the other route should take as long as taking the bus plus half of the maximum wait time. Otherwise it's just not worth it, unless you get lucky. That's why those three propositions are necessary; otherwise you'll always know what to do.

After writing this out, I googled "bus dilemma", and what do you know: there's an arxiv paper on a similar problem. Here, he's considering whether to wait or walk along the same route (in which case you can also try to account for the chances you might have to catch the bus as you're walking), which wasn't how I was thinking of it, even though it's similar to the main example I had in mind. I was thinking about two situations: the bus stop in front of my old building in Louisville, where the bus came every 20 minutes or so, took 5 minutes to take you to campus, and was set against a 20 minute walk to campus. On average in this case, you would come out ahead, but I eventually decided waiting was boring, and the few minutes gained on average were better spent walking down 3rd Street.

The other example is of coming home from Davis Square in Cambridge, and deciding whether or not to catch the 86 bus home from Harvard Square or to take the D train home from Park Street. That one is more complicated since there are multiple waits involved, but since several times I've gotten lost looking for the 86 bus stop, the problem has run through my mind several times there...

No comments:

Post a Comment