Hole search algorithm in an infinite one-dimensional graph

Question

A cow is standing in front of an endless fence. On the other hand, grass. The cow wants to get to this grass. Somewhere along this fence there is a hole through which the cow can reach the other side. The distance d from the cow to the hole has a probability distribution f (d) associated with it, that is, the probability that the hole at a distance of k steps from the cow is given by f (k). Note that we consider all distances to be discrete, that is, they are always measured in terms of the steps taken by the cow. A cow can take negative whole steps, as well as whole positive steps, that is, k steps to the left and steps to the right, respectively. In addition, we know that Σ (k = -∞) ^ ∞ | k | ⋅f (k) ≤ ∞. We want to describe an algorithm that can find a hole with probability 1.

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

Answer 1

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

• check hole in current position
• go forward 1 step, check hole
• go back 2 steps, check the hole
• go forward 3 steps, check for a hole
• go back 4 steps, check the hole ...

1. , , , , , . ""; 1-2-3-4-5 , 2 . :

• 1 , .
• 2 , .
• 4 , .
• 8 , ...

Google " ", N- ( , "" "" )

Answer 2

, ? , , , , . , . ( , , f , .. k, f (k) > 0). , , , f .

, , , - , , , , CDF f.

, . , : , , .

Answer 3

, , . . , , (, , ).

Answer 4

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);
}