How can the dilemma be solved with out statistics?
Robert Dochow and Michael Schwarz
You wish to go to a buddy and arrive there as quickly as potential. There’s a direct bus connection, however the bus is often late and generally doesn’t come in any respect. You’re on the station on time, however the bus shouldn’t be there. What are you going to do?
Both you anticipate the bus, otherwise you begin strolling to get to your buddy. Should you go away the station, you gained’t have the ability to take the bus anymore. On the one hand, you’re prepared to attend for a experience, since it’s quicker. Then again, there’s a likelihood that the bus is not going to come. What a dilemma!
Sort of downside
Initially, it looks as if that is an optimization downside the place the aim is to reduce the journey time to your buddy. A better look reveals that solely restricted data is accessible, and helpful statistical assumptions can’t be made. There is no such thing as a sure management over the journey time. The true downside is about minimizing private remorse for making the improper determination. Instantly after you understand the bus is behind schedule, you waver between two choices: wait or stroll? The whole downside is a sequential determination downside because the waver time is divisible into discrete sub-problems. Each second you understand “the bus continues to be not there”, you need to make a brand new wait-or-walk determination. Such a sequential downside, the place data arrives piece-by-piece in a serial vogue, is known as an on-line downside. In distinction, a corresponding downside the place all data is understood prematurely, just like the true future, is known as an offline downside. Notice that statistical assumptions should not wanted if the long run is understood.
The optimum answer for a web based downside
A web-based downside can often be solved with completely different methods. A web-based algorithm is a formulation of a method as an relevant sequence of steps to resolve a concrete situation. The standard of such an algorithm will be evaluated with a aggressive evaluation and permits a comparability with different algorithms. For this on-line algorithm, the aggressive ratio c must be derived. It’s outlined as the biggest ratio of the net answer (ALG) and the corresponding offline answer (OPT) for any situation. In different phrases, this ratio is derived by figuring out one worst-case situation, the place the algorithmic answer with restricted data differs probably the most from the answer of somebody who is aware of the long run.
A web-based algorithm is denoted as aggressive whether it is mathematically potential to show that this c is a continuing (with c ≥ 1), which suggests it’s impartial of any situation. This idea has an enormous benefit. It offers a efficiency assure for that algorithm, although the result of a sensible occasion of the issue shouldn’t be identified. No matter any situation, the answer of the net downside will all the time be smaller than or equal to c occasions the answer of a rational determination maker who is aware of the long run.
The web algorithm with mathematical provable lowest c has the tightest efficiency assure and is, subsequently, optimum. (Notice, that the above assure system differs for maximization issues. For extra data, study on-line optimization.)
One of the best answer for the offline downside
Assume the gap d to your buddy is 3 km, your strolling pace v_w is 4 km/h, and the driving pace of the bus v_b is 20 km/h. Therefore, by strolling, you would wish 45 min (3/4 * 60 = 45), however driving the bus would solely take 9 min (3/20 * 60 = 9).
Nevertheless, your private determination depends upon figuring out what number of minutes you need to wait till the bus arrives on the station t_b. All potential eventualities differ solely in that arrival time. If ready plus the driving time is longer than the pure strolling time, then you’ll all the time begin strolling instantly. If not, you’ll wait.
If you realize the long run, you’ll by no means want longer than 45 minutes to reach at your buddy’s place. In all eventualities of the offline downside, it’s only useful to attend when the bus arrives inside 36 minutes. This may additionally can help you arrive in 45 minutes (36 + 9 = 45). Sadly, you have no idea the long run…
Evaluation of assorted on-line algorithms
Now, check out the actual sensible downside in which you’ll be able to’t see the long run. In an summary sense, there are only some methods the issue will be solved:
Algorithm 1 — the athlete (ALG1): One technique is that you simply all the time begin strolling instantly if the bus shouldn’t be there. The worst-case situation for that algorithm appears as follows: You’ll all the time stroll, and the bus will arrive instantly (assume after ε time, the place ε may be very small) when you begin strolling.
You all the time want 45 minutes however there are numerous eventualities the place you will remorse your determination, extra exactly, in all eventualities the place the bus arrives throughout the subsequent 36 minutes. Within the worst-case situation, the bus arrives ε time after you begin strolling, the place ε time is negligibly small. Then you definitely want 5 occasions longer than it really would have been potential (9 vs. 45 minutes as a result of ε is near 0). The technique appears to be excessive, however no less than you arrive at your buddy’s place in every situation. The algorithm is aggressive… however is it additionally optimum?
Algorithm 2 — the lazy particular person (ALG2): One other excessive technique is the place you all the time anticipate the bus and by no means determine to stroll. It’s straightforward to foresee that within the worst-case situation, the bus by no means comes. You by no means arrive at your buddy’s place. This technique has no fixed c and is, subsequently, not aggressive.
Algorithm 3 — the optimizer (ALG3): One could all the time determine to attend for a set time x earlier than getting impatient and deciding to stroll. It’s hanging that aggressive methods with completely different x can considerably differ within the aggressive ratio.
For instance, suppose you all the time wait precisely 10 minutes (i.e., x = 1/6 hours) earlier than you begin strolling. The bus instantly comes after you permit the station within the worst-case situation. You find yourself being at your buddy’s place after 10+45 = 55 minutes, whereas the offline answer would wish 10 + ε +9 = 19 minutes. Therefore, you’re 2.89 occasions (55 vs. 19 minutes) worse than the answer for which you’d have identified the precise arrival time of the bus. In comparison with the c = 5 of the athlete (i.e., x = 0 hours), the c = 2.89 is already a major enchancment. However are you able to do even higher?
How you can derive the optimum ready time x*? Relating to the optimum on-line answer x*, there are two errors you will remorse. Both you begin strolling too early or too late. Within the too-early case, you remorse not having waited longer because the respective offline answer is all the time going to attend for the bus. Within the too-late case, you remorse that you simply didn’t begin strolling earlier, as a result of the offline answer will instantly begin strolling once you arrive on the station. The optimum on-line technique would stability out each circumstances to reduce your remorse.
Rearranging to x offers the optimum ready algorithm. By inserting x* in one of many error aggressive ratios above, the corresponding optimum aggressive ratio c* is derived. It’s the lowest potential aggressive ratio. If the bus pace is all the time better than the strolling pace, c* is rarely bigger than 2.
Within the concrete instance, the optimum ready time is x* = 0.6 hours (3/4 –3/20 = 0.6) which interprets into 36 minutes (0.6 * 60 = 36). The corresponding aggressive ratio is c* = 1.8 (2–4/20 = 1.8), the place the offline answer arrives after 45 minutes, and the net answer wants 81 minutes (36 + 45 = 81). Based mostly on the given bus and strolling pace, there is no such thing as a higher technique. Which means every other ready time leads all the time to a better c.
For a greater understanding, think about beneath the visualization of the aggressive ratio for all on-line methods within the vary between 0 and 120 ready minutes. The bottom level represents c* with corresponding x*.
Conclusions
So what are you going to do subsequent time when you find yourself on the bus station and the bus shouldn’t be coming? Earlier than you begin strolling, consider this text. There exists a method that’s by no means 2 occasions worse than a method that is aware of the precise future. The optimum ready time is the bus journey time minus strolling journey time. This can be a worst-case technique the place you might have completely no details about the long run. Notice this: If in apply you make a distinct determination, you both assume different data, or you aren’t performing rationally.
Zoom out! What else did you study? First, you solved a future-related optimization downside with out making any statistical or distributional assumptions. The used methodology is known as aggressive evaluation. Second, your answer has a efficiency assure primarily based on an answer that is aware of the precise future.
Take into consideration different purposes in enterprise and personal life: Make or purchase? Hire or purchase? … Do or not do?
References
- A. Borodin and R. El-Yaniv, On-line Computation and Aggressive Evaluation (1998), Cambridge College Press
- J. Chen, S. Kominers and R. Sinnott, Stroll versus Wait: The Lazy Mathematician Wins (2008), arXiv Working paper
- C. Thompson, The Bus-wait Method (2008), New York Occasions Journal: Yr in Concepts
- A. Morton, A Notice on Strolling Versus Ready (2008), arXiv Working paper
- R. Dochow, On-line Algorithms for the Portfolio Choice Drawback (2016), Springer
