Looking for hard and rare logic puzzles

[mward]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

I think that there is a subtle flaw in rhino's solution:

Spoiler:

Then find out what values f takes on points other than c - this pins it into one of your equivalence classes. Find your pre-chosen representative of f's equivalence class (call it F) and assume that f(c) = F(c).

This works with probability 1 because in order to get it wrong, we need c to belong to the measure-zero set where F differs from f - but because of how c was chosen this has probability zero.

The problem is that we are given all the values of f except at c. Let's call this partial function f'. In order to find F we need to extend f' to a total function, by giving it an arbitrary value on c. It doesn't matter which value we choose, since all the extensions are in the same equivalence class. So lets define f'' as the extension of f' such that f''(c) = 0. Now, f'' is in one equivalence class, so as in rhino's solution, let F be the representative of f''. Now f'' differs from F on a set of measure zero: call this set M. I will assume that rhino is correct in asserting that c is in M with probability zero. But M is the set on which f'' differs from F. Assuming that f(c) is not zero, then f differs from f'' on the set {c}, which is also of measure zero. So F differs from f on the set M \cup \{c\} with probability 1. So the value of F(c) tells us almost nothing about the value of f(c).

[Nitrodon]

I am thinking of a function f:ℝ→ℝ. You pick a real number c and I tell you the value of my function for all x except for c. You must guess f(c). What strategy can you use to maximize your probability of being right, and what is that maximal probability?

I think that there is a subtle flaw in rhino's solution:

Spoiler:

Then find out what values f takes on points other than c - this pins it into one of your equivalence classes. Find your pre-chosen representative of f's equivalence class (call it F) and assume that f(c) = F(c).

This works with probability 1 because in order to get it wrong, we need c to belong to the measure-zero set where F differs from f - but because of how c was chosen this has probability zero.

The problem is that we are given all the values of f except at c. Let's call this partial function f'. In order to find F we need to extend f' to a total function, by giving it an arbitrary value on c. It doesn't matter which value we choose, since all the extensions are in the same equivalence class. So lets define f'' as the extension of f' such that f''(c) = 0. Now, f'' is in one equivalence class, so as in rhino's solution, let F be the representative of f''. Now f'' differs from F on a set of measure zero: call this set M. I will assume that rhino is correct in asserting that c is in M with probability zero. But M is the set on which f'' differs from F. Assuming that f(c) is not zero, then f differs from f'' on the set {c}, which is also of measure zero. So F differs from f on the set M \cup \{c\} with probability 1. So the value of F(c) tells us almost nothing about the value of f(c).

Spoiler:

The idea behind this is that f'' is in the same equivalence class as f, so the representative F does not depend on your choice of c. F and f differ on some set M', which does not depend on c. The probability that you will choose a value that happens to be in M' is zero.

[skeptical scientist]

Spoiler:

So if the guesser can choose a representative of each equivalence class, he can guess f(c) with p=1 no matter what f is.
But as I said, if his adversary makes f by choosing each f(x) independently and uniformly at random from [0,1] for every x in ℝ, the guesser has insufficient information to determine f(c) with probability > 0. Obviously, these two facts are in contradiction.
Is building f this way just "not allowed"? Why would it be that choosing representatives from each equivalence class without specifying a distribution is OK, but choosing f(x) values with a specific distribution isn't?

Here's the resolution to your apparent contradiction:

Spoiler:

Let us closely examine what your construction actually proves. You want to argue that if you build f by choosing values at different points independently at random, then f(c) is independent of f|_R\{c}. Let's see what happens when we try to make that argument rigorous.

You can build f by choosing values at different points independently at random: you can view the space R^R of functions from R to R as a product space, and a probability measure on R will induce a probability measure γ on the product. You can pick a function f at random from this measure space, which does correspond to picking the various values independently at random. For example, it's possible to show that given finitely many points, the distributions of the values of f at those finitely many points are independent, and each matches the original distribution on R.

We want to show that this choice of f defeats Qaanol's strategy. Showing that we beat Qaanol's strategy with probability 1 is equivalent to showing that

\int_{\bf R^R \times R} \delta(S(f,c),f(c)) \, d(\gamma \times \mu)(f,c)=0,

where μ is the probability measure from which Qaanol picks c, γ is the probability measure on R^R, δ is Kronecker's delta function, and S(f,c) encodes Qaanol's guess for f(c) given f|R\c. The idea would be to show that i) by Fubini's theorem, this integral is equal to the integral

\int_{\bf R} \int_{\bf R^R} \delta(S(f,c),f(c)) \, d\gamma(f) \, d\mu(c),

and ii) since the values of f are chosen independently at random, for each c,

\int_{\bf R^R} \delta(S(f,c),f(c)) \, d\gamma(f)=0

since the product measure γ factors into the product of a probability measure on R^R\{c} determining f|_R\{c} and a probability measure on R^{c} determining f(c) (which again uses Fubini's theorem). Assuming i) and ii), this tells us that the Qaanol's guess is almost-surely wrong. But as the strategy determined by Qaanol produces a nonmeasurable function S, both steps fail, as Fubini's theorem applies only to measurable functions. (The proof does, however, show that no measurable strategy can succeed.)

Mike-l was completely correct when he pointed out the connection with nonmeasurable sets.

I am now undecided on whether Qaanol's proof actually works.

Spoiler:

Let's again encode Qaanol's strategy by a pair μ and S, where μ determines the choice of c, and S determines the guess for f(c), and imagine this strategy is played against some strategy γ for picking a function f (which may or may not be the same probability measure on R^R as above). It seems to be that Qaanol's proof is implicitly identifying

\int_{\bf R^R \times R} \delta(S(f,c),f(c)) \, d(\gamma \times \mu)(f,c),

the expected value of an indicator variable determining whether the guess is correct when both players play at random according to their strategies, with

\int_{\bf R^R} \int_{\bf R} \delta(S(f,c),f(c)) \, d\mu(c) \, d\gamma(f).

This is suspect for the same reasons as discussed above, and I think the probability of success is actually ill-defined. Or rather, it's pretty clear that Qaanol's strategy works if you are careful to state things in terms of a fixed (but unknown) function f, but it falls apart if Qaanol's strategy is played against an opponent who may also choose nondeterministically.

[mfb]

I am now undecided on whether Qaanol's proof actually works.

Spoiler:

>>but it falls apart if Qaanol's strategy is played against an opponent who may also choose nondeterministically.
If the opponent knows your representatives of the equivalence classes (with guessing, he has a chance of 0 to do that), maybe he can choose his own function to spoil the method. But as long as he cannot do that, I think we can work with
>> it's pretty clear that Qaanol's strategy works if you are careful to state things in terms of a fixed (but unknown) function f,

[mward]

Spoiler:

What is the difference between "a fixed (but unknown) function f" and "an opponent who may also choose nondeterministically"? In either case, by the time you start to try and guess the value of f(c), the function is fixed.

[skeptical scientist]

Spoiler:

What is the difference between "a fixed (but unknown) function f" and "an opponent who may also choose nondeterministically"? In either case, by the time you start to try and guess the value of f(c), the function is fixed.

Spoiler:

Well, the thing is, under the usual measure-theoretic interpretation of probability, asking the probability that the strategy works against a player who plays nondeterministically is asking for the measure of an unmeasurable set. If it were defined, it would have to be both 0 and 1 by the two different arguments. You can question whether this has any meaning as a "real" probability, but ultimately since a winning strategy isn't even definable, such questions aren't really meaningful.

Here's a much simpler question that displays the same paradoxical properties: assume the continuum hypothesis, and fix a well-ordering <_w of the interval [0,1] of type ω₁, the first uncountable ordinal. Two random numbers x and y are picked from the interval [0,1] according to the usual probability distribution (given by Lebesgue measure). What is the probability that x<_wy?

[jestingrabbit]

Spoiler:

Here's a much simpler question that displays the same paradoxical properties: assume the continuum hypothesis, and fix a well-ordering <_w of the interval [0,1] of type ω₁, the first uncountable ordinal. Two random numbers x and y are picked from the interval [0,1] according to the usual probability distribution (given by Lebesgue measure). What is the probability that x<_wy?

Spoiler:

Principle of indifference => 1/2 [that's a quasi serious answer, btw.]

[Macbi]

I'm not sure if I can cope with the frequentist interpretation of probability, the axiom of choice, and the continuum hypothesis all in one puzzle.

[skeptical scientist]

Where does the frequentist interpretation of probability come in to play?

Spoiler:

Principle of indifference => 1/2 [that's a quasi serious answer, btw.]

Spoiler:

You are completely right that the principle of indifference implies the answer is 1/2. On the other hand, after picking x, what is the probability that y>_wx? There are only countably many numbers <_wx, and since y is picked uniformly from [0,1] according to Lebesgue measure, y>_wx with probability 1. So there are perfectly good arguments suggesting the probability should be 0, 1/2, and 1.

The real answer, of course, is the events x<_wy and y<_wx are unmeasurable sets, so the probability is undefined. (This is example is inspired by a counterexample of Sierpinski's to Fubini's theorem.)

[Macbi]

Where does the frequentist interpretation of probability come in to play?

Spoiler:

Principle of indifference => 1/2 [that's a quasi serious answer, btw.]

Spoiler:

You are completely right that the principle of indifference implies the answer is 1/2. On the other hand, after picking x, what is the probability that y>_wx? There are only countably many numbers <_wx, and since y is picked uniformly from [0,1] according to Lebesgue measure, y>_wx with probability 1. So there are perfectly good arguments suggesting the probability should be 0, 1/2, and 1.

The real answer, of course, is the events x<_wy and y<_wx are unmeasurable sets, so the probability is undefined. (This is example is inspired by a counterexample of Sierpinski's to Fubini's theorem.)

For instance:

Spoiler:

If probability is bayesian and hence about degrees of knowledge, then the probability that y>x shouldn't change once x has been picked. So long as you don't know what x is, it is still a random variable.
A better example would be Qaanol's original puzzle. With my frequentist goggles on I can say things like:

"c has to be picked randomly after the other person has decided on f. If c was fixed before your opponent chose f then they could select f from a distribution such that the probability of you guessing wrong was 1. (Trivially, since they can just use the pure strategy of choosing an f where you turn out to get the wrong answer.) If you pick c after they pick their function then you can have probability 1 of being correct, no matter how they pick f"

But with my bayesian goggles on this is just babbling nonsense. "If they don't know c then it's as random as if I hadn't picked it yet. Also, the method they use to pick f is irrelevant, I've already marginalised it."

[jestingrabbit]

Spoiler:

Principle of indifference => 1/2 [that's a quasi serious answer, btw.]

Spoiler:

You are completely right that the principle of indifference implies the answer is 1/2. On the other hand, after picking x, what is the probability that y>_wx? There are only countably many numbers <_wx, and since y is picked uniformly from [0,1] according to Lebesgue measure, y>_wx with probability 1. So there are perfectly good arguments suggesting the probability should be 0, 1/2, and 1.

The real answer, of course, is the events x<_wy and y<_wx are unmeasurable sets, so the probability is undefined. (This is example is inspired by a counterexample of Sierpinski's to Fubini's theorem.)

Spoiler:

Yeah, sure, I'm aware of this (believe its in a Rudin somewhere). I would say that the arguments for 0 and 1 aren't that good though. You apply Fubini's in a circumstance where Fubini's doesnt apply to get either of those results.

Generally, I'd say that if you have A and B, measurable or not, and there is a measurable bijection st f(A)=B and f(B)=A, then it makes sense to say that a random variable that is in AuB has probability 1/2 of being in A. Ultimately though, you lose sigma additivity, and people really like that.

[skeptical scientist]

Generally, I'd say that if you have A and B, measurable or not, and there is a measurable bijection st f(A)=B and f(B)=A, then it makes sense to say that a random variable that is in AuB has probability 1/2 of being in A.

I'm not sure if I would agree with this for non-measurable A and B, even when A and B are disjoint and f is measure-preserving. Some probability questions are just ill-defined. Of course, for real-world types of questions, this never comes up.

[jestingrabbit]

Yeah, disjoint, I knew I had forgotten something...

[Superisis]

Spoiler:

Aren't there and equal amount of real numbers above zero as below zero? You have no idea how the numbers are chosen, hence you cannot assume certain numbers are favoured higher than others. Hence an equal (uniform) distribution of all numbers. So if your number is a number below zero then it should be more likely that the other number is greater. If you pick a number above zero then it should be more likely that the number is less. Am I missing something?

There is no uniform distribution over the real numbers. That does not mean that the puzzle is impossible, it only means that your solution does not work. 0 is not special in any way.
I think we already had a correct solution here in the thread - if not, the blag should link to one somewhere. There is a real solution to this.

Why is it not uniform? Why would I suppose that the person/machine who wrote down the numbers favours some more than others? How can I assume that any bias is more valid than any other? If not, then it must be uniform, no?

[jestingrabbit]

Why is it not uniform? Why would I suppose that the person/machine who wrote down the numbers favours some more than others? How can I assume that any bias is more valid than any other? If not, then it must be uniform, no?

This is one of those slightly weird facts. There isn't any way to choose real numbers in a uniform way. It would require that the probability of picking a number between 0 and 1 was the same as picking between x and x+1 for all real numbers x. In particular, if the probability that we choose a number between 0 and 1 is \epsilon then

1 = P(-\infty< x < \infty) = \lim_{R\to \infty} P(-R< x < R) = \lim_{R\to \infty} 2\epsilon R = \infty.

So, if we assume the existence of a uniform way to choose real numbers, we end up with a contradiction, so no such uniform method can exist. Its true that you should not assume that any bias is more valid than another, but certainly it is possible that there is such a bias, and your method must deliver some benefit, regardless of bias.

[Superisis]

This is one of those slightly weird facts. There isn't any way to choose real numbers in a uniform way. It would require that the probability of picking a number between 0 and 1 was the same as picking between x and x+1 for all real numbers x.

Isn't it? I thought the probability of picking a number in a continous distribution was 0. Then again, despite my interest, my knowledge of statistics is severely limited.

[jestingrabbit]

The way that continuous random variables work is that the probability of being between a and b is

\int_a^b f(t) dt

for some function, f, whose integral over all the reals is 1. So, the probability of having any particular value is 0, but the probability of lying between two values is non negative, and positive for some intervals.

We say that a distribution is uniform if the probability of being in an interval is simply some constant multiplied by the length of that interval. There is no such distribution on all the reals.

[Superisis]

Ok, I think I understand. So what distribution does it follow, or what distributions/biases can we restrict it to? I've read the posts above but to me they're a tad difficult to follow. What would be the layman's answer of the strategy that benefits from the potential bias (or most potentials biases)?

[mfb]

There is some bias in the distribution, but you do not know anything about it. So you cannot profit from something like an "expected bias" - there is none.

[jestingrabbit]

Yeah, you just have to choose your point for comparison using a distribution that has positive support over all real numbers ie one such that for all a and b, the probability of picking a number between a and b is positive, because otherwise your technique doesn't work for a distribution that only picks numbers between a and b.

[mfb]

I would like to add this one.
It looks like a regular "prisoners and light switch" problem, but the solutions require really new ideas.