Game involving envelopes

Question

Suppose we have $E$ envelopes with envelope $i$ having some amount $S_i$ of dollars in it. We suppose the $S_i$ are independent copies of $S$ for which $P(S \leq s) = \frac{s}{\sqrt{s^2 + 1}}$. Let us open the envelopes one at a time. After opening an envelope $i < E$, we have to decide whether we want to continue and open the next envelope $i + 1$ or keep the money in the current envelope and end the game. How do we prove that the optimal strategy is to stop the first time $S_i \geq \sqrt{E - i}$?

I know that if we want to stop at envelope $i$ we need to compare the $S_i$ with the maximum amount in the remaining envelopes, but I'm not sure how to do that?

Answer 1

Here is a sketch of an approach, assuming you are trying to maximise the expected amount taken:

• If you have only one envelope, you have to take the amount you see. Find the expected amount to be taken and call this $A_1$.

• If you have two envelopes, you will take the amount you first see if it exceeds $A_1$ and reject it if it is less than $A_1$, instead moving on to the other envelope. Find the expected amount to be taken (either with this envelope or the other envelope) and call this $A_2$.

• If you have three envelopes, you will take the amount you first see if it exceeds $A_2$ and reject it if it is less than $A_2$, instead moving on to the other two envelopes. Find the expected amount to be taken (either with this envelope or the other envelopes) and call this $A_3$.

• And so on ...

You should be able to show $A_k =\sqrt{k}$ by induction using $\sqrt{k}\sqrt{\frac{k}{k+1}}+\sqrt{\frac{1}{k+1}}=\sqrt{k+1}$.

This optimal approach then translates into your "$S_i \geq \sqrt{E - i}$" approach using $k=E-i$.

Answer 2

Let's say that $S_{i}=n$. We prefer to stop the game if it's more likely that all the remaining $E-i$ envelopes have less than or equal to $n$ inside of them. In other words, we wish to find $n$ such that

$$ \left[P(S\leq n)\right]^{E-i}= \left(\sqrt{\frac{n^{2}}{n^{2}+1}}\right)^{E-i} > \frac{1}{2} $$

Some algebraic manipulation yields

$$ n > \sqrt{ \left[ 1-\left(\frac{1}{4}\right)^{1/\left(E-i\right)} \right]^{-1}-1 } $$