Naked before God: HELP ME SKLANSKY!

[jason1990]

[ QUOTE ]
[ QUOTE ]
If we can assume that X and Y are never equal

[/ QUOTE ]

Is it sufficient to assume that the probability that x=y is zero?

[/ QUOTE ]
I believe it is necessary and sufficient to have the CDF of X be continuous, which happens if and only if f(y):=P(X=y)=0 for all y. Do a little logical song and dance to show that f(y)=0 for all y if and only if f(Y)=0 almost surely. Then note that since f(Y) is nonnegative, f(Y)=0 almost surely if and only if E[f(Y)]=0. Finally, observe that

P(X=Y) = E[P(X=Y|Y)] = E[f(Y)].

So the CDF of X is continuous if and only if P(X=Y)=0.

[pzhon]

[ QUOTE ]
The only correct answer to the riddle/paradox is that it is in fact impossible to devise a good strategy, since you have no information at all.

[/ QUOTE ]
False. You can't give a uniform bound greater than 50%, but strategies have been presented that win more than 50% of the time against any continuous distribution.

[ QUOTE ]
The reason why otherwise smart people THINK they have a solution is that they don't take into account whether certain probabilities are well defined...

[/ QUOTE ]
You are disagreeing with multiple professional mathematicians who are telling you that the probabilities are well-defined, and that this problem is solved. Perhaps you should think about it a bit more.

[Kristian]

[ QUOTE ]
...strategies have been presented that win more than 50% of the time against any continuous distribution.


[/ QUOTE ]

It is very difficult for me to believe this. The space of continous distributions is so unbelievably large that it is impossible to make such a statement. I am also quite sure that the professional mathematicians you mention can confirm that they make some additional assumptions before presenting their solution.

[PairTheBoard]

gasgod:"The problem is that an integer cannot be drawn at random from an infinite array."

If you mean by "at random" that all integers would be equally likely to be chosen then of course you are right. You don't need such a complicated argument though. Just notice that the sum of the equal probabilities for all the integers exceeds 1. This is the kind of hidden bogus assumption people make in the Two Envelope Problem.

Rubble is talking about a probability distribution though. Certainly, a probability distribution exists for the integers. Take 1/2^n for example. For Rubble's problem he restricts it to continuous probabilty distribtions though.

PairTheBoard

[PairTheBoard]

Jason, My intuition tells me there might need to be some kind of tightness restrictions on God's distribution. Suppose X has no finite Expectation. Are you sure in that case that the Expectation you take in your calculation is actually finite?

PairTheBoard

[jason1990]

Both f and F are continuous (hence measurable), nonnegative functions bounded by 1, so the expectation certainly exists, regardless of the distribution of X. If you want to think of X as having a density p(x), then having no finite expectation means int{xp(x)} does not exist. But int{p(x)}=1, so E[G(X)]=int{G(x)p(x)} exists whenever G is a bounded function.

[pzhon]

[ QUOTE ]
[ QUOTE ]
...strategies have been presented that win more than 50% of the time against any continuous distribution.


[/ QUOTE ]
It is very difficult for me to believe this.

[/ QUOTE ]
It is not something you were asked to take on faith. Logical arguments were given.

[ QUOTE ]
The space of continous distributions is so unbelievably large that it is impossible to make such a statement.

[/ QUOTE ]
No, it isn't impossible to make or prove such a statement. The space is not unbelievably large, either.

[ QUOTE ]
I am also quite sure that the professional mathematicians you mention can confirm that they make some additional assumptions before presenting their solution.

[/ QUOTE ]
I suggest you be less sure of things that are not true. The only assumption necessary is that the distribution is continuous (the CDF is continuous), which I mentioned above.

There many real numbers. It is still easy to prove that for any real number x, x^2+x+1>0. No additional assumptions are necessary there, either.

[PairTheBoard]

OK!

[PairTheBoard]

I accept the result. Now can you explain in intuitive terms what's going on in the solution? The proof convinces me. But I'm never really satisfied until I have a feel for some principle at play in making it work. Thanks.

PairTheBoard

[pzhon]

[ QUOTE ]
I accept the result. Now can you explain in intuitive terms what's going on in the solution?

[/ QUOTE ]
There are two approaches given/referenced in this thread. They are equivalent, but I think the way described by M127 is more intuitive. I'll quote the start:

<ul type="square">
Naively, we'd just like to guess X &gt; Y when X is positive, X &lt; Y when X is negative. In fact, it turns out that this strategy almost works by itself - to see why, notice there are four possibilities:

1. X,Y&gt;0 : when this happens, our strategy works 50% of the time, since X and Y are identically distributed.

2. X&gt;0, Y&lt;0: here, we we always get in, since in this case we guess X&gt;Y correctly

3. X&lt;0, Y&gt;0: again, our strategy always works here, since it causes us to guess X&lt;Y

4. X, Y&lt;0: in this case, our strategy works 50% of the time, for the same reason as case 1.



Its not hard to see intuitively (and pretty easy to prove numerically) that unless cases 2 and 3 never happen, our probability of getting the right answer will be strictly &gt; .5. Also, when cases 2 and 3 are impossible (ie when all God's numbers are positive or all are negative), our strategy still works 50% of the time. So our answer is "almost" right.[/list]More explicitly, let p=P(X&gt;0). This strategy works with probability 1/2 + p(1-p). That is only 1/2 when p=0 or 1. When 0&lt;p&lt;1, this strategy works with probability greater than 1/2.

It is worth thinking about this until it is clear that this strategy works between 50% and 75% of the time (inclusive).

<ul type="square">
Now lets call the above strategy S(0). Its pretty easy to see that the number 0 is irrelevant to the above discussion, and if we let r be any real number, and let S(r) be the strategy "say X&gt;Y when X&gt;r and say X&lt;Y if X&lt;r", then S(r) will work strictly &gt; 50% of the time, unless all of God's numbers are greater than r or all of them are less than r. In that case, S(r) would work exactly 50% of the time.[/list]S(r) will always work at least 50% of the time. We want to ensure that our strategy works strictly more than 50% of the time, so we would like to vary r so that there is a chance it is in the middle of God's distribution (neither above 100% of God's numbers nor below 100%).

Let R be a random variable from a distribution that has positive probability on any interval, e.g., choose r from a normal distribution, or a Cauchy distribution (density dx/pi 1/(x^2+1)). Then R has a positive probability of being in the middle of God's distribution, so S(R) works strictly greater than 50% of the time.

Instead of generating a random number from that distribution, we can just skip to the consequence: If you are shown x, you will say X is greater than Y any time R is less than x. That means you switch with probability P(R&lt;x). If you are using the Cauchy distribution, P(R&lt;x) = 1/2 + arctan(x)/pi. So, instead of generating R, you can declare X is greater than Y 1/2 + arctan(x)/pi of the time, and declare X is less than Y 1/2 - artcan(x)/pi of the time. This strategy guesses correctly more than 50% of the time against any continuous distribution.