= 27d567bc2d48d9f40e9ccc20ea370b15)
IlyaShpitser comments on The correct response to uncertainty is *not* half-speed - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (40)
Imagine an undirected graph where each node has a left and right neighbor (so it's an infinitely long chain). You are on a node in this graph, and somewhere to the left or right of you is a hotel (50/50 chance to be in either direction). You don't know how far -- k steps for an arbitrarily large k that an adversary picks after learning how you will look for a hotel.
The solution that takes 1 step left, 2 steps right, 3 steps left, etc. will find the hotel in O(k^2) steps. Is it possible to do better?
Since the problem posed is scale free, so should the solution be, and if there is a solution it must succeed in O(k) steps. Increase step size geometrically instead of linearly, picking an arbitrary distance for the first leg, and the worst-case is O(k), with a ratio of 2 giving the best worst-case value approaching 9k. The adversary chooses k to be much larger than the first leg and just after one of your turning points.
In the non-adversarial case, if log(k) is uniformly distributed between the two turning points in the right direction that enclose k, the optimum ratio is still somewhere close to 2 and the constant is around 4 or 5 (I didn't do an exact calculation).
ETA: That worst-case ratio of 9k is not right, given that definition of the adversary's choices. If the adversary is trying to maximise the ratio of distance travelled to k, they can get an unbounded ratio by placing k very close to the starting point and in the opposite direction to the first leg. If we idealise the search path to consist of infinitely many steps in increasing geometric progression, or assume that the adversary is constrained to choose a k at least one quarter of the first step, then the value of 9k holds.
They can't, because this is all happening in a discrete setting ("Imagine an undirected graph...") where the minimum possible distance is 1 and your initial distance isn't going to vary over a very large range.
I can get O(k).
Grow your steps in powers of 2 instead of linearly.
Does the solution have to be deterministic? If an adversary places the hotel after looking at my algorithm, my first inclination is introduce uncertainty into my search.
No. But you can't do better than O(k) anyways, and you can do O(k) deterministically.
Randomising the length of the first step will improve on the constant factor by about 2. Similar analysis to the non-adversarial case, and with the same ETA I just added to my earlier comment.
If you make the run lengths increase exponentially instead of linearly then you get O(k) unconditionally.
I know. I was improving the constant factor.
Ah yes, OK, essentially the same randomization helps against an adversary when you're growing exponentially as when you're growing only linearly. Fair enough.