1
$\begingroup$

Suppose you are facing an infinitely-long wall. Somewhere in the wall is a door, but you can only see the door if you are right next to it. You want to go through the door.

You don't know whether the door is to your right or to your left.

How far in each direction should you walk to minimize the total (expected) distance you have to walk to find the door?

$\endgroup$

1 Answer 1

9
$\begingroup$

To be well posed you need to specify the probability distribution which specifies where the door is placed (this is the old problem of not being able to put a uniform distribution on a line).

Once you specify this, this is known as the linear search problem. There is a fair amount of literature on this problem. As a starting point see A. Beck and M. Beck's paper ``Son of the linear search problem," Israel J. Math. 48 (1984), no. 2-3, 109–122. The paper address the case of various distributions, such as the Gaussian.

$\endgroup$
1
  • $\begingroup$ Also, sometimes called the cowpath problem, as it generalizes to trees. Gerhard "And Also As Robot Apple" Paseman, 2013.04.10 $\endgroup$ Apr 11, 2013 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.