6
$\begingroup$

Knowing a solution to the following well-defined problem could help many students and other low-wage workers feel more confident when selecting a home in a new town. Its conditions are inspired by my current experience hunting for a room in Santa Cruz, CA. I'd certainly apply the solution to my current search.


The Problem:

Andy is trying to find a room to rent in cool house. Let's suppose there are (countably) infinitely many houses to pick from and Andy...

  1. visits one house each day.
  2. must, each day, decide to move in to that day's house, or abandon the option and keep looking.
  3. immediately knows how a house ranks relative to the other houses he's seen. I.e. after any number of days, $k$, he can write down an ordered list $(h_1, h_2, ..., h_k)$ of the houses he's seen (ordered by his personal preference).
  4. has a constant probability, $p$, of being accepted a house once he asks to move in. If accepted he keeps his word, if not, he keeps looking.
  5. has $N$ days to pick a house -- after $N$ days Andy must ask to move into every house he visits.

Find a strategy that maximizes the expected percentile (among the infinitely many houses available) of the house Andy ends up in.


Note, I've come across related problems phrased in terms of:
* receiving an envelope containing an amount of money and deciding to keep the money, or go on to the next envelope.
* walking down a street picking a (maybe Chinese) restaurant. If you know the common name for these types of problems, please comment.

$\endgroup$
6
  • 1
    $\begingroup$ youtube.com/watch?v=ZWib5olGbQ0 is a similar ( though not countably infinite) problem. $\endgroup$
    – user451844
    Aug 1, 2017 at 0:04
  • 1
    $\begingroup$ These sort of problems are often referred to as the secretary problem. The probability bit is different...not sure how that changes anything. $\endgroup$
    – lulu
    Aug 1, 2017 at 0:08
  • $\begingroup$ Thanks @Roddy. This problem is the special case when $p=1$ (see condition 4). That may give me a place to start :) $\endgroup$
    – mathandy
    Aug 1, 2017 at 0:47
  • $\begingroup$ And, same @lulu :) $\endgroup$
    – mathandy
    Aug 1, 2017 at 0:49
  • $\begingroup$ I'd argue it's a special case where the number of days determines the amount you have to choose from etc. $\endgroup$
    – user451844
    Aug 1, 2017 at 1:29

1 Answer 1

4
$\begingroup$

This is what's known as the secretary problem, which has (for large N, although it converges very rapidly) as optimal answer to unconditionally reject the first $\dfrac{N}e$ houses, then accept the first house that's better than the first $\dfrac{N}e$ you saw.

The only complicating factor is $p$. But I conjecture that you can view $p$ as simply reducing $N$ to $pN$.

$\endgroup$

You must log in to answer this question.

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