I have been discussing this problem with a coworker for a few days now and neither of us have made any headway on it. I would appreciate any help with a possible solution or maybe a suggestion of a book on related subject matter. The problem is as follows:
I usually park my car near the doors of a convenience store but I constantly forget where my car is parked. Let's say that my car is parked somewhere on the real axis. Let's also assume that the probability distribution of my cars location is given by a normal distribution centered at zero. Starting at zero, I will walk along the real axis until I reach my car's position or turn around and walk back in the other direction.
Given that I am extremely lazy, what is the optimal search strategy that minimizes the expected distance I have to walk?
First, I'll ignore the fact that a complete search takes an infinite amount of time, so that your question really depends on the maximum length you theoretically could cover on the real line. Lets codify this by saying that you're going to accept an error rate of 1% (so in 1% of the cases, you stop before you find your car).
Lets look at a few special cases-:
You flip a fair coin. If it is heads, you go towards $\infty$, otherwise you go towards $-\infty$. This will have an average success rate of 50%, so it is not acceptable at the 1% level.
Walk in one direction until the tail probability equals 0.5%, then turn around and head in the other direction until that tail probability is 0.5%. Now, your expected success rate is 99%.
No 2 is optimal because it maximizes the "density per unit length" of the overall search path, which means you spend more time searching in higher probability regions, without "deadheading" as much as you would if you did multiple "turnarounds" while searching. We want to minimize turnarounds, but still get the highest probability regions in our search........