I will be on instragram:
We, Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).
We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.
#PvsNP #blogging #youngminds #instagram
-------------------------------------
(David Marcus emailed me this for a guest post, inspired by my posts on a similar problem where I gave the question here and the answer here.)
This is a well known problem, but I have learned over time that not everyone knows things that are well known.
PICK THE LARGEST NUMBER:
There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number.
You want to pick the larger one. You can pick one of the numbers at random and look at it
before deciding which one you want.
Is there a strategy that will win with probability > 1/2.
CLARIFICATIONS:
1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.
2) It must have prob of winning > 1/2 for EVERY pair of reals.
3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.
(Warning: I will NOT block comments that give away the answer, so if you want to work on it without knowing the answer, do not look at comments.)
Tom Cover presented this problem and solution (and I think a generalization) at an Info Theory Symposium in the late 90s. The trick is to randomly sample from a normal and keep the one that you picked if it is greater than the random draw.
ReplyDeleteTake any strictly increasing function p(x) between 0 and 1, e.g. the continuous neural network threshold function. If you pick x, stay with it with probability p(x). Then you will choose the larger number with probabilty greater than 1/2. An example of how elementary calculations may lead to a counterintuitive result.
ReplyDelete