Cover’s Game

Let’s play a game. I will pick two numbers at random, write them on separate pieces of paper and stuff them inside envelopes A and B, respectively. You open one of the envelopes (let’s say Envelope A), and see the number inside. Now, you must guess whether the number from Envelope A is larger than the number in Envelope B.

Cover's Game, simple at first.

Cover’s Game, simple at first glance.

You’re probably thinking to yourself, ‘ok, that’s boring, I have a 50/50 chance of winning’.  But are you sure?  Here’s the goal of the game: determine a strategy that will allow you to win more than 50% of the time.

This game was invented by Stanford EE professor Tom Cover almost a decade ago to illustrate the usefulness, and outright non-intuitiveness, of formal probability.  Most players immediately conclude that, despite the fact that they’re allowed to open one of the two envelopes and see the number inside, it doesn’t change their luck: knowing only one number is as useless as knowing neither.  But that’s not the case.  Cover demonstrates, with absurd simplicity, that the player is actually at a (sometimes significant) advantage.

Here’s the optimal strategy, as discussed by Cover: before you open either of the envelopes, pick a random number (let’s say 20).  Now open one of the two envelopes (again, let’s say Envelope A).  If the number in said envelope is less than 20, guess that the number in the other envelope is greater.  If the number in said envelope is greater than 20, do the opposite.

Cover's Game: the Optimal Strategy

Thought you had just a 50-50 chance? With a strategy like this, it gets way better.

In the case shown, the I pick the numbers 16 and 23.  You pick 20 as your own random number.  Opening Envelope A, you see that 16 is less than 20, so you pick the number in Envelope B.  And it turns out you were right. Now imagine that, instead of opening Envelope A, you’d opened Envelope B to reveal 23.  Since 23 is greater than 20, you guess that 23 is greater than the number in Envelope A.  And you’re still right. That’s a 100% chance of winning this particular instance of the game…assuming you pick 20 for your own number.

Of course, you don’t know beforehand that you should pick 20.  Maybe you pick 0.  Maybe you pick 100. Maybe you pick a prime number between 600 and 630 each time (there’s only 5).  But luck’s still on your side.  As long as you use the strategy above, your random number will put you into one of three situations:

  1. Your number is less than both of my numbers. Then your number doesn’t help you out, and your success depends on whether the envelope you choose to open contains the larger number.  Chance of winning: 50%.
  2. Your number is more than both of my numbers. Again, your number doesn’t help you out, and your success depends on whether the envelope you choose to open contains the smaller number.  Chance of winning: 50%.
  3. Your number is between my two numbers. No matter which envelope you choose, you’ll pick the correct number.  Chance of winning: 100%.

So your chance of winning is 100% anytime your number is between my two numbers, and 50% otherwise.  As long as you have a nonzero chance of picking a number between my two numbers (we’ll talk about this in just a second), your average chance of winning is guaranteed to be >50%.  You’ve just hustled the house.  Or your friends, if you’re mean like that.

The real art behind this strategy is to pick the right number.  It may seem nearly impossible to do that, but here’s a helpful fact: most people, when asked to choose a number, pick one between -100 and 1000.  So if you pick your number from that same distribution, you’ve immediately improved your ‘luck’, especially when compared with the infinite set of all numbers.  Theoretically, you can succeed as much as 75% of the time if you’ve picked the right limits for your numbers.  Experimentally, success rates are closer to 60%.

One last protip: if you’re the host, and the contestant is using this strategy, you can easily foil them by choosing numbers that are extremely close together (like 13 and 14).  This reduces the chances that the contestant will choose a number that ‘separates’ yours, and limits their success to, well, 50/50.

So there you go.  Like my probability professor said when he introduced Cover’s Game, ‘you can entertain people at cocktail parties with this!’

If You’re Interested

Find more problems like this one in Cover’s The Elements of Information Theory by Wiley Press.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s