I recently ran across this problem and solution in the rec.puzzles
archive:

==> decision/high.or.low.p <==
I pick two numbers, randomly, and tell you one of them. You are
supposed to guess whether this is the lower or higher one of the two
numbers I picked. Can you come up with a method of guessing that does
better than picking the response "low" or "high" randomly (i.e.
probability to guess right > .5) ?

==> decision/high.or.low.s <==
Pick any cumulative probability function P(x) such that a > b ==> P(a)
> P(b).  Now if the number shown is y, guess "low" with probability
P(y) and "high" with probability 1-P(y).  This strategy yields a
probability of > 1/2 of winning since the probability of being correct
is 1/2 * ((1-P(a)) + P(b)) = 1/2 + (P(b)-P(a)), which is > 1/2 by
assumption.

I understand how to apply the answer, but I'm afraid I don't really
understand the answer itself.  Could someone please walk me through
the proof?  (And don't be afraid to walk slowly - I am comfortable
with decision theory in general but was not a math guy in college.)

Dear addisonbr:

Thank you for this very interesting question. After doing repeated
calculations, I have concluded that the solution given is false,
although the principle is correct. Here's my explanation. First, we
are assuming that the two numbers are not equal, and are integers.

Notation used: P(x) = probability of X. F(x) = CPF of x.

A cumulative probability function F(t) is defined to be the
probability that a random number x in the domain of F(t) is less than
or equal to t.
Further reading: http://library.thinkquest.org/10030/5rvpdcpf.htm

Now if you look at the given strategy, "guess "low" with probability
F(y) and "high" with probability 1 - F(y)", this is the same as saying
if F(y) > 1 - F(y) guess high, other wise guess low. Using the given
strategy, this will yield prob(winning) =

P(correct guess = P(chance the given number is higher) * P(x > L) +
P(chance the given number is lower) * P(x <= H) =>
P(correct guess) = 1/2 * (1 - F(L)) + 1/2 * F(H)
P(correct guess) = 1/2 (1 - (F(L) - F(H)))

Since F(H) > F(L) by assumption, then  (correct guess) must be > 0.5.


The way the answer in your questionid did it was wrong. Here's what it
should have looked like:

"There are two numbers, low L and high H. Because they are distinct
integers, H >= L + 1

The envelope we have opened contains y. The probability that it is the
smaller number (i.e. y = L) is 50%

The probability of making the right decision is therefore

P(y = L) * P(x > y) + P(y = H) * P(x &#8804; y)

P(correct) = 0.5 * (1 - F(y)) + 0.5 * F(y)

= 0.5"

Source: http://216.239.35.100/search?q=cache:K66Wgt82TMAC:www.ncaf.co.uk/htm/pubs/Soln11.ppt+high+low+decision+puzzle&hl=en&ie=UTF-8

Best Regards,
blader-ga

---

Clarification of Answer by blader-ga on 22 Jul 2002 20:21 PDT

Dear addisonbr:

I was informed by a colleague that my answer is not as clear as it
could be. After rereading my answer, I must say I agree with him. This
clarification is to perhaps make it a bit more clear. Also, there IS a
typo in one of the lines in my original answer.

First, some information on notations used in my answer.. 

Definitions:

1. P(x) means the probability of x happening. For example, if I write
P(x>y), then that refers to the probability that x > y.

2. F(x) refers to the cumulative probability function (which was
denoted as "P(x)" in your question. An understanding of what the CPF
is is essential to my answer.  A great explanation of it is here:
http://library.thinkquest.org/10030/5rvpdcpf.htm

Okay. Now let's look back at the original question. It said that the
optimal strategy is to guess low with probability F(y) and high with
probability 1 - F(y).

Now, to find the value for the probability of a correct guess using
our method, we use the following (there was a typo in the below
equation in my original answer. I switched an L and an H):

P(correct guess) = P(we were shown the higher number H) * P(we guessed
"high" given H) + P(we were shown the lower number L) * P(we guessed
"low" given L)

=> (plugging in from our selection method)

P(correct guess) = (1/2) * (1 - F(H)) + (1/2) * F(L) 

=>

P(correct guess) = (1/2) (1 - (F(L) - F(H))) 

=> Since F(L) - F(H) < 0 (by assumption)

P(correct guess) = (1/2) (1 - (a negative value))

=>

P(correct guess) > (1/2)(1 + (a positive value))

Therefore,

P(correct guess) > 1/2.

I hope this was more clear for everybody!

Best Regards,
blader-ga

---

Request for Answer Clarification by addisonbr-ga on 23 Jul 2002 05:50 PDT

blader, I'm afraid I don't agree with your proof.

You say:
-----
P(correct guess) = (1/2) * (1 - F(H)) + (1/2) * F(L)  
=> 
P(correct guess) = (1/2) (1 - (F(L) - F(H)))
-----

But I don't follow.  Let's let F(H) = A and F(L) = B.

(1/2) * (1 - A) + (1/2) * (B)
=
(1/2) * (1 - A + B)
=
(1/2) * (1 - (A - B))
<>
(1/2) * (1 - (B - A))

That feels like a pretty fundamental flaw.

I am rapidly coming to the conclusion that the appropriate strategy is
to guess IGH (not low) with P(y).  That I am having no problems
proving to myself.

---

Clarification of Answer by blader-ga on 23 Jul 2002 12:34 PDT

Dear addisonbr:

You are completely right. According to the alternate solution I linked
to:
http://216.239.35.100/search?q=cache:K66Wgt82TMAC:www.ncaf.co.uk/htm/pubs/Soln11.ppt+high+low+decision+puzzle&hl=en&ie=UTF-8

Their strategy was (in a two envelope LOW decision problem):
"draw an integer x at random. If x > y then choose the envelope you
have opened, otherwise choose the other one."

This is equivalent to the exact opposite of the method used to select.
If we switch our selection strategy, then it is easy to see that the
equation works. As you said:

"I am rapidly coming to the conclusion that the appropriate strategy
is
to guess IGH (not low) with P(y)."

I completely agree with this conclusion.

Where I went wrong was that I didn't notice that the alternate
solution I linked to was actually a problem involving a "LOW" decision
problem, which the exact opposite of our own.

Best Regards,
blader-ga

Took a couple of tries, but I ultimately got an answer I was satisfied
with.  Appreciated blader's efforts after the false start; was worth
the $.

OK, tell me if I'm wrong, but doesn't this proof rely on an assumption
that isn't necessarily true?  The assumption is that P(a) > P(b).  But
how do we know that P(a) isn't really less than P(b)?

I wasn't a math guy in college either, so I'll won't attempt an
answer.  I'll just concur with addisonbr that the answer seems easy to
apply but hard to understand.

Scott:

I think it's because we select the function P to make sure that P(a) >
P(b) holds true for all a > b. For example, P(x) = x + 1, then it
holds.

Isn't 1/2 * ((1-P(a)) + P(b)) = 1/2 + (P(b)-P(a))/2?  Isn't P(b)-P(a)
< 0?  Doesn't that make it < 1/2?

Am I missing something?

This question appeared locked after I typed in the comment.  I then
tried to refresh, multiple times, which somehow caused the multiple
posts of the same message.

Sorry for the stuck record...I mean CD skips...I mean MP3 file
corruption...

I will defer to blader, who sounds like more of a math person than I
am (I was on a math team in high school, but have probably regressed
since then :-| ).

I also agree with ulu -- it does seem like there's a "divided by 2"
missing in the solution, though I suppose that the solution, at least
as based on the initial assumption (or whatever it is), is still
correct.

It is the case that if I choose two choose distinct numbers, say A and
B, you have a strategy that permits you to select either A or B and,
on being shown the value of the number you selected, to determine,
with probability of correctness > .5, whether A or B is higher. The
answer points to an interesting URL, however, that URL addresses
another problem.

Oops, actually I may have made an error in my last comment; I just
reread the URL I'd pointed to and I think that that URL may be
addressing the same problem after all!

rbnn:

Yes, it's true that the value of probability is > .5 with the method
given, but given an infinite range for the random numbers, the exact
probability is .5 + lim x -> infinity. Which is too small to make a
difference at all. The odds improve greatly as limits are added. The
smaller the limit, the better the odds.

Best Regards,
blader-ga

Thank you for your explanation. I'm not entirely sure what is meant by
"lim x" in this context, and I'm afraid I'm still not totally clear on
whether your analysis supports or disagrees with the claim in the
comment: "It is the case that if I choose two distinct numbers, say A
and B, you have a strategy that permits you to select either A or B
and, on being shown the value of the number you selected, to
determine, with probability of correctness > .5, whether A or B is
higher."

Note that as stated the original question could be asking, "If I pick
two random numbers; and if I then select one of the numbers and show
it to you; can you determine with P>.5 whether I selected the higher
or lower number?" The answer to this question in general is (of
course) no.

You are right though this is certainly an interesting question. Really
(so to speak) there are two questions: the real and the integer case.
One problem with the real case is the numbers don't have finite
descriptions; it doesn't make sense necessarily to "show" someone a
real number. But suppose the numbers selected are rational, is there a
probabilistic recursive strategy?

I don't *think* there is a recursive solution when the numbers are
allowed to be recursively enumerable, that is, their digits are
recursively enumerable, but I'm not sure.

regards

Oh, I just read the clarification of the answer, and that does make
things clearer for me.

I was thinking, here is another to way to think of it. Choose any
continuous positive probability distribution over the real numbers.
Select some number t according to that probability distribution.

Now, suppose you see the number "A". If A>t, say "A is the higher"
else say "A is the lower".

Suppose the two numbers are A and B.

Now, if t> A and t>B, then you will be right with probability .5.
Similarly if
t<A and t<B you will be right with probability .5. (Assuming either A
or B is chosen to be shown to you randomly). But if either A<t<B or
B<t<A you will always be right; since the initial probability is
continuous positive, whether A<B or B<A you will occasionally choose t
in that interval, and so you'll have >.5 chance of getting the right
number!

Dear rbnn:

Yes, I realize now that my original answer was very much convoluted.
I'm happy that my clarification is a bit more understandable. =)

By lim x -> 0, I mean to say "the limit of x as x approaches to 0," as
it is used in calculus.

So, if the range of selection is infinite, i.e. -infinity to infinity,
then the advantage gained by using the strategy is infinitely close to
zero. Hence, more than .5, by not enough to matter. =)

However, realistically, there will be a range, since generating random
numbers in an infinite range is impossible. Therefore, practically
speaking, there is a significant enough advantage to use this strategy
to make it practical.

Best Regards,
blader-ga

Dear rbnn-ga:

By the way, I certainly don't mind discussing this problem further
here. But I don't see you posting on our researcher forums much. If
you want, we can always take it over there. =) The address is in your
latest newsletter.

Best Regards,
blader-ga

I've been thinking more about this interesting problem, and wanted to
explore a small generalization:

Here I think is how one can solve this under reasonable assumptions
even given finitary constraints and real input. In other words, we
don't want to have to say "select continuously a random real number"
as this cannot be done by a computer; i.e., its not a finitary
computation.

The assumption is that when you are shown a real number r, you can
always query the integer part and the k'th bit after the decimal
point, for any positive integer k.

We also assume that we have a source of coin flips.

Once more, assume we are presented with two distinct unknown real
numbers A and B; we choose one, say A, and want to determine with P>.5
whether or not A>B.

All we need to do is choose a real t from a continuous positive
probability distribution over the reals, and then ask whether t>A: if
it is, we say A is smaller, else we say A is the larger. (Since the
probability density is continuous we don't get t=A with nonzero
probability).

First, choose a random integer n. The simplest way to do that is to
keep flipping your coin until you get the first Tail. The number of
heads you have seen so far is n. If the next flip is a Head, then you
negate n.

Now we are going to choose t from the open interval (n,n+1) .

We keep computing bits of t until we know for sure whether t>A or not.

So, here is what we do:

If A>=n+1, we return A is HIGH and stop.
If A<=n we return A is LOW and stop.

Otherwise, set U=A-n.
set bitnumber=0;

while (true){
  flip
  bitnumber=bitnumber+1;
  if Head then bit = 1 else bit =0;
  If bitnumber'th bit of U is > bit, return HIGH else 
  if bitnumber'th bit of U is < bit return LOW 
}

This procedure terminates with probability 1 in a finite number of
steps, and
for any A and B, gives P>.5 of choosing correctly whether A is higher
or lower.

I'd be quite interested to know who first invented this paradox, by
the way. I was not able to find a reference in a long search.

I was trying to generalize to other domains, without too much success
though; that is, are there other interesting domains X and binary
relations R satisfying trichotomy such that when given distinct x1,x2
from X one can determine whether R(x1,x2) or R(x2,x1) with probability
> .5 ? What if R is a total order? What if it is not binary?