Drawing Blanks

Premature Optimization is a Prerequisite for Success

An unfair game

with one comment

You write down 2 distinct real numbers from [0,1] and seal them in envelopes. I pick one envelope, open it, and guess whether the number that I see is greater or less than the number in the other envelope.

I claim that I have a winning strategy, i.e. a strategy that allows me to guess correctly with probability greater than 50%.

Such strategy does exist.

It is important to note that you don’t pick numbers “at random”, you pick them “at will”. That is, I cannot assume that they obey some certain distribution. I intend to win no matter how you try to counter my strategy.

Solution.

I pick a random number from (0, 1).  If it’s greater than the number that I see, I say that the other number is greater, otherwise I say that the other number is less. My guess will be correct in more than 50% of cases.

Proof

Let the hidden numbers be a and b, a < b. And let my generated random number be x.

I pick a with probability 1/2. If x > a then I win. The probability of this is 1-a.

Or I pick b with probability 1/2. If x < b then I win. The probability of this is b.

The total probability of me winning is 1/2*(1-a) + 1/2*b = 1/2 + (b-a)/2 > 1/2

Obviously, the player who picks the numbers can make the loss arbitrarily small by picking very close numbers.

How does this work?

Imagine that you know some number between a and b. Then your win is guaranteed. Picking a random number ensures that sometimes (with some positive probability) it will fall in between a and b. That makes your chance greater than 1/2. Note that the distribution of x doesn’t have to be uniform. It just needs to be positive everywhere. So that for any interval the probability of x falling in it is positive.

Do we extract information from the random numbers?!

No. But randomness prevents our opponent from preventing our winning 😉 Imagine that the opponent can predict our random numbers. Then we won’t be able to win. And in the finite case with a deterministic random generator, the opponent will sooner or later learn to predict it. (See https://bbzippo.wordpress.com/2010/05/23/hunting-problem/ )

Advertisements

Written by bbzippo

06/02/2010 at 3:17 am

Posted in math

One Response

Subscribe to comments with RSS.


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

%d bloggers like this: