4by12

Two Envelopes: Part 2

As promised, here’s another solution to the two envelopes riddle: First, choose a descending list of probabilities p(n). When you receive a number n, say ‘higher’ with probability p(n) and ‘lower’ otherwise. That’s the solution. Now let’s prove that it works.

Say the other person chooses numbers n

P(win) = 0.5*p(n) + 0.5*(1-p(m)) = 0.5*(1 + p(n) – p(m)) > 0.5

That last step is where I use the fact that the series of probabilities descends: n < m and so p(n) > p(m). Finally, because P(win) is larger than 0.5 for every n,m pair that can be chosen, we expect to win with probability greater than 0.5.

I’ll now explain how I found this solution, and that will shed some light on why it works in the first place. The explanation is a bit long and verbose, because I tried to make it as clear as possible. The first thing I noticed when thinking about the riddle is that, if the first number I get is 1, then the second number must be higher. So if I get 1, I can say ‘higher’ and be correct every time. I then devised my first strategy: If the number is 1, say ‘higher’. Otherwise say ‘higher’ with probability 0.5.

If the other person has a chance of giving me 1, then I will obviously win in the long run. The other person knows my strategy, so he cannot ever give me 1. Okay, so the minimum number I get is 2… Maybe if I get 2 I can say ‘higher’, and be correct. And maybe I can follow this line of reasoning and do the same with 3, 4, 5, … ad infinitum. Well, this of course doesn’t work, because eventually the other person must choose some number and I won’t always be right.

So this strategy isn’t scalable, so to speak. But there is some knowledge here: The other person is less likely to choose 1 as one of the numbers, because then she has a 0.5 chance of giving it to me as the first number and letting me win. So if I get 2, I know that it is likely that the other number is higher than 2. But how do we quantify this increased likelihood, given that the other person can choose any strategy she likes?

Turns out we can let the math do the work for us. Let’s define the following strategy: If we get 1, we say ‘higher’. If we get 2, we say ‘higher’ with probability p. Otherwise we say ‘higher’ with probability 0.5. Our goal is to find the optimal ‘p’. Let’s say the other person first chooses 2, and then chooses a number greater than 2 with probability q, and a number lower than 2 (i.e. 1) with probablity 1-q. Our chances of winning in this case are:

P(win) = q*(0.5*0.5 + 0.5*p) + (1-q)*(0.5*(1-p) + 0.5*1)

Let’s explain this. There are actually three options: The other person can choose either greater than 2 or 1, we can get either 2 or the other number, and we can say ‘higher’ or ‘lower’. So the first term, q*0.5*0.5, is the case where the other person chooses a number higher than 2 (prob. q), we get that number (prob. 0.5), and we say ‘lower’ (prob. 0.5). Note that the last term is the one where the person chooses 1 and we get it, so we say ‘higher’ and are correct with prob. 1. Now let’s simplify this:

P(win) = 0.5*[q*0.5 + q*p + (1-q)(2-p)] = 0.5*[2 - p + q*(0.5 - 2 + 2*p)] = 1 – 0.5*p + 0.5*q*(2*p – 3/2)

This last expression is quite cool. By choosing p=3/4, we can make the last term vanish and get P(win)=5/8 > 0.5 ! This is the crux of this method: We can choose a p that eliminates our dependence on q, which is the only control the other person has. So in effect this method allows us to take control of the problem, and to ensure our victory.

We can go on and solve the same problem in case we get 3, 4, and so on, finding the optimal probability for each. I won’t go into the calculation, but the resulting probabilities are: p(n) = 0.5*(0.5 + p(n-1)), i.e. the next probability is the average between 0.5 and the current probability, and p(1)=1 as before.
As you can see, this forms a descending series of probabilities, and we already showed that such a series allows us to win the game. In a sense, this is the optimal series of probabilities. And now you can see why this method works: It’s because the natural numbers have a minimal item, and we can use this leverage inductively to form a winning strategy.

Another related and interesting characteristic of this solution is that it is applicable to other number spaces, but only to those the have a minimum. For example, you can choose two real numbers in the interval [0,1]. In this case, we can use a descending function of probabilities p(x) to obtain the same result. But if the other person chooses two integer numbers (i.e. allowing both positive and negative), this method breaks down. Compare this with the first solution, which works for any number space.