= 27d567bc2d48d9f40e9ccc20ea370b15)
gjm 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?
Grow your steps in powers of 2 instead of linearly.