Find a hole while travelling along an infinite wall
If you can go only left or right, than you can do the following strategy:

DIRECTION = Right
For i = 0 to infinity do:
    Go 2^i steps to DIRECTION.
    Go back to the initial place.
    CHANGE_DIRECTION
    STOP if you found the hole


If the distance between the start place and the hole is n, you will find the hole within O(n) steps. You can easily calculate the exact average number of steps given this algorithm.