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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Gerhard Paseman
    Commented Apr 11, 2013 at 5:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .