Algorithm to find hole in an infinite one dimensional graph

Question

A cow is standing in front of an infinite fence . On the other side is grass. The cow wants to get to this grass. Somewhere along this fence is a hole through which the cow can get to the other side. The distance d from the cow to the hole has a probability distribution f(d) associated with it i.e. the probability that the hole is k steps away from the cow is given by f(k). Note that we think of all distances as discrete i.e. they are always measured in terms of steps taken by the cow.The cow can take negative integer steps as well as positive integer steps, i.e. k steps to the left and steps to the right respectively. Also, we know that ∑(k=-∞)^∞|k|⋅f(k)<∞. We want to describe an algorithm that can find the hole with probability 1.

Problem 1 What is a sufficient condition for an algorithm to be able to find the hole with probability 1? Problem 2 Describe such an algorithm.

Answer 1

It seems to me that your problem, as stated, has a trivial solution:

• check for hole in current position
• walk forward 1 step, check for hole
• walk backward 2 steps, check for hole
• walk forward 3 steps, check for hole
• walk backward 4 steps, check for hole...

This walk will visit all relative integers, with probability 1. Of course, what you really want is to optimize for the average amount of steps that the cow will have to take, which is known as the search game problem. The solution is an 1-dimensional exponential "spiral"; you just replace the 1-2-3-4-5 arithmetical sequence above with a geometrical one, multiplying by 2 each time. That is:

• check for hole in current position
• walk forward 1 step, checking for hole at each step
• walk backward 2 steps, checking for hole at each step
• walk forward 4 steps, checking for hole at each step
• walk backward 8 steps, checking for hole at each step...

Google for "The Cow-Path Problem", which is a generalization of yours to an N-way crossroad (you have only two, "left" and "right")