Waiting for the bus
Inspired by Eric Lippert's blog entry: http://blogs.gotdotnet.com/ericli/PermaLink.aspx/ccad26e1cf0948dc81543afc087419ba
Eric has a strategy for waiting at bus stops. If he waits at the stop for too long and the bus does not arrive, he gets up and walks instead.
Suppose a bus comes by this bus stop every hour. Eric has no watch, so he doesn't know how long he has to wait for the next busit could be any value from 0 to 60 minutes with equal probability. He also knows the time it takes for the bus to get to his destination (Tbus), and the time it would take him to walk instead (Twalk).
If Eric wants to minimize the average amount of time the trip takes, how long should he wait at the bus stop before he walks instead?
Peter Meilstrup
Tuesday, October 07, 2003
I'm eagerly awaiting the general solution. If you could factor in a coefficient taking into account the odds that it will suddenly start raining (hint: it is October in Seattle) that would be ideal.
Eric Lippert
Wednesday, October 08, 2003
Oh, and incidentally, it's true  I don't have a watch and so I often don't know how long its going to take for the bus to arrive. And besides, the bus times are sufficiently random out here that I'm not convinced that having a timepiece would help.
Eric Lippert
Wednesday, October 08, 2003
I just stumbeled in by accident (seeing wich of these JoS forums are alive), so I don't know the customs here but looking at this question:
**********************************
Possible spoiler follows
**********************************
Why ever wait and then walk? Waiting provides no new data. Furthermore waiting will not change TWalk, and only reduce TBus in each instance, so you either start walking straight away or wait for the bus until it arrives.
If your bus frequency is F, then the average wait time is F/2.
If F/2+TBus > TWalk then you walk, otherwise you wait it out.
Just me (Sir to you)
Wednesday, October 08, 2003
> Waiting provides no new data.
Sure it does. Suppose you wait 59 minutes. You're telling me that you can't deduce a fact about the world from that? Of course you can. You can deduce that the bus is coming in the next minute.
The longer you wait, the more likely it is that the bus will come soon. You can use that data to improve the expected wait time.
Eric Lippert
Wednesday, October 08, 2003
Actually, what I said isn't quite true. Yes, you can gain information, but it doesn't help. Just Me's conclusion is correct  you're better off walking immediately than waiting and walking.
Suppose your strategy is "wait at least n minutes, then walk". If you work out the expected wait time of this strategy, it turns out to be governed by the quadratic equation:
n^2 + (2B  2W + 119) n + 120 W
Where 0 <= n <= 60
This equation gives you twice the number of seconds you're going to wait on average. Since that is a downwardopening parabola on a closed interval, the minima are going to be at the endpoints. The best strategy is either "wait at least 60 minutes" or "walk immediately", depending upon the values of W and B.
Note that when I posed the original question, it was a little different from this question. First off, I had no bounds  I could have waited forever for that shuttle. Second, I was seeking to minimize the _bound_ on the maximum wait time, not minimize the _average_ wait time  a subtly different problem.
Eric Lippert
Wednesday, October 08, 2003
Eric,
I'd say that if you have no info on shuttle deveations and "no shuttle ever arrives" is part of te possibilities, then you do not have much choice. You walk unless there is a shuttle in sight. The best maximal bound you can achieve is TWalk/TBus.
Best possible scenario: you arrive at the stop the moment the shuttle is there. To limit the worst case, you have no choice but to start walking immediately if you do not see a shuttle, since the shuttle might never come.
I also wonder about your DVD rental example: If you just buy every DVD straight away, seems to me you have limited your suckiness factor to 100% of the purchase price, which is better than the 200%.
Looking at best cost minimizing strategy with past information is more interesting. The trick becomes leaching a beneficial predictor out of a limited time series.
An example:
say you have the following viewing history (videos A to E)
A) watched 7 times
B) watched 1 time
C) watched 1 time
D) watched 11 times
E) watched 5 times
You can detect a strong correlation between (watched more than 1 time) and (watched more than 4 times)
In that case a strategy of buying on the 2nd urge to rent would be more great. Your maximal bound is still worse than in the "always buy" scenario (125% vs. 100%), but if the future is in line with the past, the new strategy will beat the always buy or always rent strategies.
For the shuttle this would mean having a series that shows e.g. every time I waited more than 60 minutes, it turned out I waited over 240 minutes, so if my walking time was just 120 minutes, and the shuttle would get me there in 30 minutes, my best strategy is to wait for 60 minutes and then start walking.
Just me (Sir to you)
Thursday, October 09, 2003
> I also wonder about your DVD rental example: If you just buy every DVD straight away, seems to me you have limited your suckiness factor to 100% of the purchase price, which is better than the 200%.
Right, but suppose you only watch it once? The suckiness factor is not the amount you paid over the purchase price, but the amount you paid over what you could have paid. If you only watch it once and yet you bought it, the fact that you paid only 100% of the purchase price is irrelevant  you paid 600% (or whatever) of the rental price.
Now, your point that the distribution of DVD watching is bimodal is a good one. If you can apply probability heuristics then you can improve the _average_ suckiness factor, though in doing so you may increase the _maximum_ suckiness factor.
Eric Lippert
Thursday, October 09, 2003
Thanks for clearing that up Eric, I misunderstood the "suckiness".
In the DVD example I would propose that a strategy of buying on the fourth instead of the fifth time is optimal since it limits the suckiness factor to 175% (vs. the 200% in your case).
Just me (Sir to you)
Friday, October 10, 2003
Yes, I noted that mistake in a comment to the original article.
Eric Lippert
Friday, October 10, 2003
Recent Topics
Fog Creek Home
