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?

  • 4
    $\begingroup$ Wait a few days and you should receive a ticket for parking illegally. They usually tell you where you can find your towed car. $\endgroup$ – IAmNoOne Dec 1 '14 at 4:48
  • 2
    $\begingroup$ I don’t think the exact turn sequence is known, but the question is addressed in the references here, specifically the papers by Beck. en.wikipedia.org/wiki/Linear_search_problem $\endgroup$ – Steve Kass Dec 1 '14 at 5:08

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-:

  1. 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.

  2. 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........

  • $\begingroup$ does this still hold if you try to optimize P(finding car) in a fixed amount of time? (arguably a more realistic model then heading off to infinity) $\endgroup$ – djechlin Jan 2 '15 at 17:13
  • $\begingroup$ @AAA Yes it does, the asymptotic case just makes the explanation complete, but you are correct. $\endgroup$ – user76844 Jan 2 '15 at 17:20
  • $\begingroup$ I think the "real life" problem is your model changes as you don't find your car. $\endgroup$ – djechlin Jan 2 '15 at 17:42
  • $\begingroup$ @AAA yep, that is why I included an acceptable "error" rate...which basically says I am willing to accept an $x$% risk of not finding my car. In my example, there is a 1% chance you don't find your car. $\endgroup$ – user76844 Jan 2 '15 at 17:44
  • 2
    $\begingroup$ @Eupraxis1981: As an extreme case, consider that you are going to make so sure you find your car, you are willing to search up to $100$ standard deviations from the mean in either direction. Surely you wouldn't go all the way out to $100$ standard deviations in one direction...after a while you'd decide that you were all but certain to find your car on the other side. $\endgroup$ – paw88789 Jan 2 '15 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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