# Find a hole while travelling along an infinite wall

There is an infinite wall with a hole somewhere, you are placed on that wall at an unknown position. Let the distance between your initial position & the hole be $x$. Find the average distance traveled in terms of $x$ until you find the hole. What's the complexity of this problem in terms of $x$ and how does an algorithm look like that solves it?

• This looks like the standard lost cow problem. Commented Apr 26, 2013 at 15:52
• One is placed "at a random position" with what distribution? $\hspace{2.3 in}$ How does the hole's size compare to the wall's height? $\;\;\;$
– Ricky Demer
Commented Apr 26, 2013 at 18:08
• @RickyDemer: I suspect "random" actually means "arbitrary", that the "wall" is actually a line, and that "you" are actually a point. But I'm happy to be corrected. Commented Apr 26, 2013 at 19:41
• In that case, bludger should still say whether he's considering randomized $\hspace{1.45 in}$ or only deterministic search strategies. $\:$
– Ricky Demer
Commented Apr 26, 2013 at 19:45
• @JeffE: Could you summarize this in a short answer? Commented Jun 3, 2013 at 22:01

DIRECTION = Right