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

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.

Answer 2

create a bullet shot, put variable sized intervalled walls in between and see wich wall is not shot at. go on from there. you have to know how to graph the hole function though ( maybe an approximation will do, just not to an endless hole ).

Answer 3

findHole(S)
{
  k = 0;
  previous_k = 0;

  current_f = f(k, S);
  if (current_f == 1) return (S);

  previous_f = 0;
  //While the probability of finding a hole increases,
  //we increase k and verify if the vertex at k steps is a hole
  while (current_f >= previous_f)
  {
    previous_f = current_f;
    previous_k = k;

    //As closer to probability 1 we are, as smaller steps we make
    k = (1 - current_f) * MAX_STEP_SIZE;
    current_f = f(k, S);
    if (current_f == 1) return (S);
  }

  //If we overshot our hole and the probability of finding
  //a hole at k steps distance has started to decrease, we
  //perform a binary search within the boundaries of the interval
  //[previous_k, k], with probabilities in [previous_f, current_f],
  //having a guarantee that our hole is within this interval
  return binSearch(previous_k, k, S);
}

Answer 4

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