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")

Answer 2

Can all you do is check if the hole is at a given position? If so, it seems like the only thing to do is check positions in order of decreasing likelihood. You will be guaranteed to find a hole, but it may take an arbitrarily long time. (You can guarantee you will find a hole within a certain number of searches if and only if f has finite support -- that is, iff there are only finitely many k for which f(k) > 0). If there are an unknown number of holes, you will only be able to determine that you've located them all if f has finite support.

On the other hand, if you can check to see if the distance to the hole is less than some specified amount, then something like a binary search weighted by the CDF for f would probably be the best option.

It would be helpful if you could describe the context of the problem. As it stands, the graph doesn't really seem to enter the equation -- you just have a bunch of cups, and you're trying to figure out which one has a ball under it.