6
$\begingroup$

Assume you standing in some place and you have $n$ doors in front of you. When you open one of the doors, lets say the $i$-th door three things can happen.

  1. With probability $p_i$ you can escape
  2. With probability $q_i$ you will be killed
  3. With probability $r_i (=1-p_i-q_i)$ you know it is a door that leads to death and you return to your room

The events occuring behind the doors are independent from each other. Which doors should you choose to maximise the prob. of an escape.

In my opinions there is no optimal strategy how to choose the best door because by opening one of them there is no change in the probabilities at other doors, so you choose an arbitrary door and hope to survive or to come back. Is this correct or do I misunderstand something?

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ Do you know the probabilities? If not, you are right. If so, or at least something, you can $\endgroup$ – Ross Millikan Oct 20 '13 at 17:38
  • $\begingroup$ Oh, I see. The probabilities are different for each door. $\endgroup$ – TonyK Oct 20 '13 at 17:43
  • $\begingroup$ Yes you know the probabilities $\endgroup$ – Ulrich Otto Oct 20 '13 at 19:34
  • $\begingroup$ Someone who has an idea? $\endgroup$ – Ulrich Otto Oct 22 '13 at 13:35
  • $\begingroup$ What happens if you open but return from every door? Do you die? $\endgroup$ – Samuel Oct 23 '13 at 0:38
1
$\begingroup$

The optimal strategy is the greedy one: in each step, choose the door $i$ with the largest relative probability of escape $p_i/q_i$. (However, the greedy solution is only optimal if we choose to open all doors; see the footnote.)

Proof: Consider the strategy consisting of opening doors $1,2,3,\ldots,n$ in order (continuing to the next one if we haven't already escaped). Compare it to the strategy where we have switched the order of two neighboring doors, say door $i$ and $i+1$. I claim that the first strategy is better than the second strategy if and only if $p_i/q_i \geq p_{i+1}/q_{i+1}$. Thus, for any given strategy, we get a better strategy by switching the order of any pair of neighboring doors $i,i+1$ such that the new pair satisfies $p_i/q_i \geq p_{i+1}/q_{i+1}$; by iterating this procedure until it stops we will always end up with an ordering of the doors such that $p_1/q_1\geq p_2/q_2\geq\cdots p_n/q_n$, so the strategy opening doors $1,2,\ldots,n$ in order is optimal precisely if this condition is met.

I will now prove the claim. The probability that we will escape if we open doors $1,2,3,\ldots,n$ in order, is $$p_1+r_1(p_2+r_2(p_3+r_3(p_4+r_4(p_5+r_5(\cdots))))).$$ Say we switch doors $3$ and $4$. Then the probability of escaping is $$p_1+r_1(p_2+r_2(p_4+r_4(p_3+r_3(p_5+r_5(\cdots))))).$$ The first probability is $\geq$ the second probability if and only if $$p_3+r_3(p_4+r_4x) \geq p_4+r_4(p_3+r_3x)$$ where $x:=p_5+r_5(\cdots),$ which is equivalent to $$\begin{gather} p_3+r_3p_4 \geq p_4+r_4p_3 \iff \\ p_3(1-r_4) \geq p_4(1-r_3) \iff \\ p_3(p_4+q_4) \geq p_4(p_3+q_3) \iff \\ p_3q_4 \geq p_4q_3, \end{gather}$$ which is equivalent to $p_3/q_4 \geq p_4/q_4$, so we are done. I switched the places of doors 3 and 4 rather than doors $i$ and $i+1$, but that was only for simplicity of notation and it should be clear that this will work for any $i$. This completes the proof.


Footnote: I want to mention, however, that the greedy algorithm is only optimal if we go through with opening all doors. If we choose a strategy where we only open one door, and then stop, regardless of if we are allowed to return or not, will be optimized by choosing the door with the largest $p_i$ instead. Moreover, one can find a set of three doors such that $p_1/q_1>p_2/q_2>p_3/q_3$, but opening doors 1 and then 3 and stopping gives a lower probability of escape than opening doors 2 and then 3 and then stopping.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks for this answer. In my point of view it is intuitively clear to choose the door with largest relative probability $p_i/q_i$. Lets define the random variable $X_i=1$ with prob. $p_i$ and $X_i=0$ with prob $r_i$ and $X_i=-1$ with prob $q_i$. 1 stands fir escpape, 0 for going back and -1 for being killed. Then to get the maximal $\mathbb E[X_i]=p_i-q_i$ the term $p_i/q_i$ has to be maximal which is exacly what you mentioned. I am not sure my approach is fully correct. $\endgroup$ – Ulrich Otto Oct 26 '13 at 15:54
  • $\begingroup$ I found a proof for my conjecture, so I have completely rewritten my answer. $\endgroup$ – Samuel Oct 26 '13 at 19:07
  • $\begingroup$ @UlrichOtto: Regarding your approach: you are only considering a single door, not a sequence of doors, so I don't see how it could be used to solve the problem. Also, $p_i-q_i$ is not maximal iff $p_i/q_i$ is maximal. $\endgroup$ – Samuel Oct 26 '13 at 19:07
  • $\begingroup$ I see, thanks for that. $\endgroup$ – Ulrich Otto Oct 26 '13 at 19:07

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.