Optimal strategy for getting the larger envelope of two envelopes

Question

I encountered a problem similar to the two envelope paradox: Two envelopes with amounts $x$ and $2x$, where $x$ is uniformly distributed in $[0,100]$. Randomly shuffle the two envelopes, and you pick one and observe the amount. You can choose to switch or stay. What is the optimal strategy to get the envelope with the larger amount?

An intuitive strategy is to switch if the envelope has less than 100. But I am not sure how to show this strategy in fact maximizes the probability of getting the envelope with the larger amount. Here is what I tried:

\begin{align*} P(\text{getting large envelop}) &= P(\text{getting large envelop } | \text{ observed <100})P(\text{ observed <100})\\ &+ P(\text{getting large envelop } | \text{ observed >100})P(\text{ observed >100})\\ &= P(\text{getting large envelop} | \text{ observed <100}) \cdot \frac{3}{4} + 1 \cdot \frac{1}{4} \\ \end{align*}

but how can I show that the strategy maximizes $P(\text{getting large envelop} | \text{ observed <100})$?

Thanks.

Answer 1

I'll rephrase your problem to emphasize the different elements:

• we have a random variable $X$ with a real value $x$ in $[0, 1]$ uniformly distributed
• we independently flip a coin to decide which of $x$ and $2x$ will be the observed value (it's the same thing as shuffling the envelopes and choosing the first one). I will denote this by $O$ for observed, with values $0$ when the smaller value is seen first and $1$ when it's the larger value.
• the strategy that we are looking for is a function $f$ which will receive the observed value and provide a binary decision of $1$ for keeping the current envelope and $0$ for switching for the other one.

I will also use $R$ for the result of the game, with the value $1$ when the larger value was chosen and $0$ when the smaller one is selected. We are looking for a way to maximize the probability that the strategy $f$ helps us choose the larger amount, conditioned by the strategy $f$: $P(R = 1 | f)$. Consider a random value $x$ and the possible outcomes:

• with probability $1/2$ we are presented with the smaller value $x$. In this case, the conditional probability $P(R=1 | X=x, O=0, f)$ will be equal to $1$ if we switch and $0$ if we keep the first envelope, so we can write this as $1 - f(x)$
• with probability $1/2$ we are presented with the larger value $2x$. In this case the conditional probability $P(R=1 | X=x, O=1, f)$ is based on the decision $f(2x)$ (we apply $f$ to $2x$ here because that is the value we observe) and will be $1$ if we keep the envelope and $0$ if we switch, so in this case it is the same as the value $f(2x)$

Thus, the total probability $P(R = 1|f)$ for a strategy $f$ can be written as

$$ P(R=1|f) = \int_0^1 P(R=1|X=x,f)dx \\ = \int_0^1 \frac12 \left( P(R=1|X=x,O=0,f)+P(R=1|X=x,O=1,f) \right) dx \\ = \int_0^1 \frac12 (1 - f(x) + f(2x)) dx = \frac12 - \frac12 \int_0^1 f(x) dx + \frac14 \int_0^2 f(x) dx \\ = \frac12 - \frac14 \int_0^1 f(x) dx + \frac14 \int_1^2 f(x) dx $$

So from here we can see that the strategy $f$ which maximizes the outcome is indeed the one you suggested, switch when $x < 1$ and keep when $x > 1$. Seen as a probability value, the outcome of this case is $3/4$.