And further into the envelope madness …

Although I started out on the side of John and Bill Carone in believing that there was something funny about the two-envelope problem, I’ve always been suspicious of claims that the class of inifinty paradoxes (even Zeno’s Paradox) can really be tamed by asserting that they disappear if you know how to take limits properly. With that in mind, I mercilessly torture some of Greg Chaitin‘s work to create a version of the two-envelope paradox in which I don’t think there are any limit arguments to make use of. Once more into Socratic dialogue ….

ANGEL: So here we bloody well are again, eh?

DANIEL: Yes, yes, I know the drill. Two envelopes, purgatory, hell, etc, blah blah blah. Have you *quite* finished flipping your coin?

ANGEL: No coin flipping this time. Instead, a little maths test.

DANIEL : Maths test?

ANGEL: Yes. In this first envelope, you will see written down an exponential Diophantine equation. Set to work solving it.

DANIEL: How. may I ask?

ANGEL: Any way you want to. Here’s a textbook on the LISP computer programming language, which ought to help.

DANIEL: And what’s my incentive?

ANGEL: Basically, the faster you solve it, the less time you spend in Hell. For every day you spend working on this problem, you spend a day in Hell.

DANIEL: Strikes me that I could be quite some time …

ANGEL: Clever boy. But if you’re worrying about the fact that the equation might have no solution, then don’t. After you’ve been working a week, then I’ll offer you another deal. At any point after that, I’ll offer you the option of stopping work on *that* equation and starting work on *this* equation in this other envelope. And I’ll even offer you an incentive to switch; you’ll spend the time in Hell that you spend solving the second equation, minus a day.

DANIEL: Seems good, but …

ANGEL: And to make it yet sweeter, I hereby guarantee you that at least *one* of the two equations has a finite solution.

DANIEL: I can’t help noticing that a fair number of my mates have taken similar bets with you, and none of them have ended up in Heaven so far …

ANGEL Well think it over … there’s a week to go before you need to make any decisions …

{ 26 comments }

ogged 06.01.04 at 5:50 pm

A tricky trick from D-squared, since we all know that having to solve a math problem under time pressure

isHell. Real questions: are there two hells? And how can we choose between them?Matt 06.01.04 at 6:17 pm

So… does this prove that moral questions (i.e., questions posed by an angel) may be undecidable?

dsquared 06.01.04 at 6:37 pm

Maybe … my aim (I’m most definitely not sure I’ve achieved it) is to suggest that the real guts of these paradoxes is not something to do with limits but more likely that they all come down to something similar to the assumption that names which look like they refer to something actually do so.

Bill Carone 06.01.04 at 8:26 pm

Dsquared,

Would you explain a little more about the situation you describe? What about the exponential diophantines, one that certainly has a finite solution and one that might not, drives the problem? I’m just not getting it :-(

dsquared 06.01.04 at 9:51 pm

Basically, there is a particular class of exponential diophantine equations which have the property that you can’t tell whether they have a solution or not unless you can also solve the halting problem for a Turing machine. So, if you are working on problem 1 and being offered the option to switch to problem 2, then you are being offered something fairly analogous to the deal in Brian’s second, coin-tossing version of the envelope problem; a choice between a process that might take a finite time or might take forever, and a process which also might take a finite time or take forever, but which appears to be stochastically dominated. Except that in this case, there’s no issue of taking limits; your uncertainty is right there as soon as the problem is posed.

John Quiggin 06.01.04 at 9:59 pm

I’m also having trouble seeing the difficulty. In the usual paradox, the point is that you can be persuaded to switch back again at the end of the second week. But in this case, there is no real problem unless you drag in an infinite expectation.

It seems reasonable to suppose that Hell has PCs (though not Macs). So you set your PC to checking possible solutions (brute force method). Every time you get an opportunity to switch you take it. Eventually you must find a solution. (A long time, maybe, but you get to watch that bird brushing the mountain with its wingtip every million years, which would help to pass the time)

How long, on average, is “eventually”? This depends on the set from which the soluble equation is drawn. If this is one that leads to a violation of countable additivity, you’re in trouble.

phil 06.01.04 at 10:02 pm

F*ck the equations. Make yourself comfortable. Order room service. Tell the angel you need to hire some staff – intermediate terms administrator (x2), infrastructure support (x4), office manager. Take them on team-building exercises. Hell only starts when you finish. The angel has made a MAJOR mistake.

Ross Smith 06.01.04 at 10:34 pm

You haven’t changed the nature of the problem at all; you’ve just replaced a pair of “random” choices from one infinite set (positive integers) with another (diophantine equations with certain special properties). The fundamental problem (that there isn’t a clear definition of “random” in the context of an infinite set) is unchanged.

Nevin 06.01.04 at 10:55 pm

If I understand correctly, your only chance to switch is after 1 week. At that point, you will be stuck with one problem, and if it is unsolvable then you will spend eternity in Purgatory (I assume that the problem takes place there, since the other ones did. You don’t specify, though.) I will henceforth refer to “eternity in Purgatory” as “Hell”. (If my understanding is wrong, and you intend to let people switch back and forth weekly, like some commenters imply, then the rest of my posting is moot.)

The “paradox” only comes up if the subject cannot determine whether the problem is solvable within a week. If so, then they basically have a 50% chance of staying in Hell and a 50% chance of a finite time in Purgatory. There’s no way to tell which is which… basically, this boils down to the angel saying “I’ll flip a coin. If you lose, you go to Hell, but if you win, you eventually go to Heaven.” There’s no paradox there, just a very tense gambling situation.

The “1 day less” aspect is equivalent to the angel saying “If you choose Heads and win, you’re Purgatory time will be less than if you choose Tails and win.” Again, no paradox (though it may raise questions about whether the angel is trying to trick you)…just a gamble with different results for different choices.

Bill Carone 06.02.04 at 3:06 am

Dsquared,

I seem to be unable to really digest your example, but here are a few thoughts.

“Except that in this case, there’s no issue of taking limits; your uncertainty is right there as soon as the problem is posed.”

I don’t know what you mean by this statement. The uncertainty is “right there” in all of Brian’s situations, in that we don’t know what payout will occur. How do we model our uncertainty? Using probability. How do we model our uncertainty over an infinite set of possibilities? I say that we try with limits, and fail otherwise.

The question isn’t the presence or absence of uncertainty at different points in the problem; in all these examples we don’t know what the payout will be, and we are trying to model the idea that there are an infinite number of possibilities. No matter how you set up the idea that there are an infinite number of possible outcomes, my (contested) claim is that the only way to model them is using limits.

“a choice between a process that might take a finite time or might take forever, and a process which also might take a finite time or take forever, but which appears to be stochastically dominated.”

In (most of) Brian’s examples, he specifically says that the “infinite payout” doesn’t happen (i.e. if the coin never lands heads, you get e.g. 1 day in Hell instead an infinite stay in Hell). So we are opening up another issue here that we haven’t had to deal with before.

Once we add in the idea not only of an infinite number or possibilities, but some possibilities having infinite utilities, that adds a new level of limits we need to take, and a new way that our mathematics can refuse to give an answer (if limits aren’t well-behaved).

However, let’s say that you simply stay in Hell until you solve the problem; let’s also say that God, at maximum, will only keep you N days. Then, we might be able to model the situation by letting N go to infinity; that would be a “limit” way of modelling your situation. Is there anything I am missing so far?

Then we would follow this process.

1) We would specify our probability for problem 1 having a solution or not; repeat with problem 2.

2) We would specify our probability distribution for the time it would take until we find a solution to problem 1, given it has a solution; repeat with 2.

3) We would calculate the expected utilities (over these finite ranges) for each alternative.

4) We would then see what happens when N goes to infinity.

Before I make further assumptions, do an example calculation, and see if the limit is well-behaved, do you object to any of the steps 1-4 above. I suspect you do, as a result of the “special” situation of the exponential Diophantines, but I can’t see it.

Dave 06.02.04 at 3:07 am

A nearly optimal solution to this problem is to spend equal amounts of time on each envelope (perhaps a week at a time on each?) constantly switching back and forth.

If you are forced to re-start your calculations after each switch, then the optimal solution probably involves spending ever-increasing amounts of time on each (such as one week, then two, then four, etc.)

If you only can switch once, you should (though when is up to you). Using the halting problem (which I understand better) as an argument, I would say that while it’s impossible to come up with an algorithm that determines whether an arbitrary TM will halt on an arbitrary input, a machine that will halt tends to do so sooner rather than later. So the longer I work on a TM without it halting (or showing obvious signs that it won’t), the more likely I am to want to switch.

Look at it this way. Say that the average (TM + input) of length N that is going to halt does so in D days with a probability roughly proportional to 2^(-D). Of course, the actual numbers will vary considerably from this, but it serves as a reasonable model. Anyway, we know that (according to the article linked in this post) the probability of a random (TM + input) of length N halting is in itself a random variable with a more or less uniform distribution in [0, 1].

Now, unless the Angel is trying to trick us by making our first TM a particularly long-running (but halting) one, we can come up with a good strategy. Note that we assign both TM’s a prior probability of halting of 50% (the average probability of halting, because we don’t know any better). Now, if we’ve spent any time on the first TM and it doesn’t halt, the probability that it is going to halt is reduced. We can then safely switch to the second TM. However, the longer we spend on the first TM, the more certain we can be that we’re not abandoning the one that will send us to heaven. BUT, if we work on the wrong one, we will stay in purgatory forever instead of going to hell and then heaven. So, we balance the possibility of an eternity running TM simulations in purgatory against the (ever-increasing) amount of hell-time we’ll have to suffer, and make a decision of when to switch.

What makes this problem distinctly different from the others is that by working on the first problem, we get at least some information about it that lets us make a more educated choice later on. We still have nice probabilities, and in this case, we probably don’t even have to take limits.

dsquared 06.02.04 at 7:17 am

Bill: But the halting probability (the probability that any algorithmic process for solving the equation will halt in time T) is strictly unknowable (this is the guts of Chaitin’s Goedelian argument). There is no way of making an estimate of the halting probability in step 1 (by which I mean, no algorithmic procedure which will ever deliver an informative estimate).

John: Same response. The “British Museum Algorithm” that you suggest does not in fact generate a solution to all exponential Diophantine equations which have a solution. It’s a violation of coutnable additivity in the same way in which all Goedelian arguments implicitly rely on one, but taking limits doesn’t help you (or at least, if it did, it wold also help you solve the Halting Problem, which it doesn’t).

Dave: Given the Angel’s track record in Brian’s problems, you should certainly assume it is “quite likely” (where “quite likely” is a probability not estimable by any alogrithmic procedure) that he is trying to put one over on you in exactly this manner.

[NB, since this is God we’re talking about and perfection is demanded, I’m assuming that “solve” in this context means “write down all whole-number solutions”. The exact point that Chaitin makes is that there is no procedure with a well-defined halting probability which can tell whether particular Diophantines have a finite or infinite number of solutions]

Dave 06.02.04 at 8:16 am

Given the Angelâ€™s track record in Brianâ€™s problems, you should certainly assume it is â€œquite likelyâ€ (where â€œquite likelyâ€ is a probability not estimable by any alogrithmic procedure) that he is trying to put one over on you in exactly this manner.Ah. Well, then he’s probably picked a problem with a ridiculously long solution time, so even if you do manage to solve it you’re spending a tremendous amount of time in hell. In that case, I might pick one of the problems and just not work on it very hard, so that I never leave purgatory.

The exact point that Chaitin makes is that there is no procedure with a well-defined halting probability which can tell whether particular Diophantines have a finite or infinite number of solutions.I’m not sure that’s what it’s saying. What it seems like to me is (a) there is no algorithm that can tell you whether there is a solution for an arbitrary Diophantine equation, and (b) the probability that a member of the set of Diophantine equations with representation length N has a solution is entirely random (distributed uniformly in [0, 1]) for any N.

Now, that’s not to say that we don’t get any additional information by working on the problem a little. Like I said, I don’t know much about Diophanes, but the article seemed to suggest that finding solutions was equivalent to solving the halting problem. This would make the set of equations with solutions recursively enumerable, not undecidable. Since there are at most 2^N equations with representation length N, the set of such equations is finite, and therefore the subset of equations with solutions must be null or finite.

There is, therefore, a maximally difficult solution to find (in terms of computation time) among the solvable Diophantines of length N. The problem is that for arbitrary N, we have no idea what that computation time is, or even how many of the equations of length N are solvable (if any). If we knew what that maximally difficult solution was, we could just do that much computation and see if we solved the equation or not. However, it can be shown that not only do we not know the computation length for the hardest problem in the set of length N, but that T(N) in general is not bound above by any computable function!

However, there is also a minimally difficult solution for the set of problems of encoding length N. Through the magic of padding, at least in the halting problem, it is possible to come up with a number of problems of length N that halt in an very short time. I suspect the Diophantines problem is the same way. So, by doing even a little bit of computation, you can eliminate some of the possible equations with solutions.

Now, since we don’t know the probability that a problem of length N is solvable, eliminating a few possibilities by doing a little computation not only suggests that the particular problem you have is not in the set of problems with solutions, but also suggests that the probability of solution for length N is less than 50%. The two might balance each other out, but by doing some hand-waving, and invoking the same magic that inspires the tau distribution, I think you can make the argument that the overall chance you have a bad problem increases with the time you spend on it. Determining exactly how much it increases, though, is beyond my mathematical ability.

dsquared 06.02.04 at 8:37 am

One can tidy up the example for the suggested strategy of not working and staying in purgatory by assuming you’re already in Hell and trying to get out …

Jack 06.02.04 at 11:29 am

Doesn’t this just show that the real interest of the supposed paradox lies much less deep? The original issue appears to be simply soluble but that apparently simple solution produces impossible answers.

By this I mean the supposedly obvious calculation that switching boosts your expectation by 25%.

In this new case, anybody capable of jumping to a swift conclusion would probably be quite happy to remain in purgatory doing maths in any case but will also be used to the strange behaviour of distributions with infinite expectation. In short, they may work hard to work out what the right solution is but they won’t find it paradoxical.

Michael Mouse 06.02.04 at 3:34 pm

Surely the correct response to the Angel is like Lucifer’s:

non solviam: I will not solve. You’ll almost certainly be cast into the inferno, where there are no Macs or PCs to help you calculate, and perhaps even worse, no web connection. But as the Son Of The Morning said, better to (slide) rule in Hell than to surf in Heaven.Bill Carone 06.02.04 at 5:40 pm

Dsquared,

“But the halting probability (the probability that any algorithmic process for solving the equation will halt in time T) is strictly unknowable … There is no way of making an estimate of the halting probability in step 1 (by which I mean, no algorithmic procedure which will ever deliver an informative estimate).”

I disagree fundamentally with much of this statement. However, it doesn’t change the basic point: once you put my limiting procedure in, there is no longer a dominance argument; it is no longer the case that, for all possible outcomes, you prefer envelope 1 to envelope 2. Therefore, no paradox.

…

Okay, just a few more points about the quote above.

1) Probability describes a state of information. Probability isn’t “unknowable,” you don’t “estimate” probabilities, as if they were facts about the world you are trying to discover. You assign them to be consistent with your information.

2) You may be arguing that no probability is consistent with the state of information given in the problem. You would have to show that, if we assign probability p, it leads to a contradiction for any p. I do not see this in the paper (although I may not recognize it if I see it).

Even if it were true that there is no consistent probability, it doesn’t produce a paradox, it merely doesn’t give an answer. (What is the probability that “This sentence is false” is true? No answer, but no paradox either, any more than “What is the probability that Bill is six feet tall given that he is less than five feet tall and more than seven feet tall?”)

3) The paper’s use of the word “random” blurs the distinction between uncertainty (not knowing what will happen) and complexity (irreducibility). Probability theory models uncertainty, dynamic systems theory models complexity. I claim that you shouldn’t “mush” the two together; you should analyze the unknown and the complex separately, then put them together using standard mathematical tools.

Matt Weiner 06.02.04 at 5:54 pm

D-squared–

It seems to me that this example relies essentially on the idea that the angel knows which equation has finite solution time and which doesn’t. So it turns into something like the Holmes and Moriarty problem* in which there’s no way that each of the opposing players can devise a strategy that works. In Weatherson’s cases, though, the gaming can take place without the angel knowing what is in which envelope.

Still, I think this is a great tool; I’m wondering whether it’s possible to determine the distribution of solution times over a certain class of exponential diophantine equation. If there were a certain finite range of coefficients such that it could be proved that at least one of the coefficients in that range had infinite solution time, we could get a paradox that I think would be relatively well-behaved. (Er, that’s a plea for someone else to do some of my thinking for me.)

Trival point: If you’re trying to get out of hell, then the offer isn’t tempting at all, since switching would waste the week you’ve spent working on the first problem… My proposed fix is to make you spend double the solving time in Hell, and have the second offer be that you spend 2x-8 in Hell. Or something like that.

*I’m not going to supply a link here because it’d take me a while to find and I got it from you in the first place.

Shai 06.02.04 at 8:50 pm

ping

Shai 06.02.04 at 10:00 pm

throw out the bit about diophantine equations (mostly because I’m too lazy and stupid to learn about them) and replace it with black box turing machines. one halts, one doesn’t, but you’re basically a blind halting oracle contemplating the rest of the truth table until you receive the information that one does indeed halt, one doesn’t. here you may as well flip a coin unless you receive some other information about one or more of the state machines to achieve a more favourable probability distribution.

throw in the bits in the original discussion about eternal damnation in the pits of hell and isn’t Brian’s original discussion identical, sans the computers? (sloth prevents me from bothering to read either of them)

Neel Krishnaswami 06.03.04 at 1:16 am

I think this problem still has a badly-behaving limit in it.

Here’s a rough sketch of how the argument goes (rough, because my knowledge of complexity theory is). With a Turing machine, the amount of addressable memory is proportional to the length of time it runs, and the size of the state space is proportional to the exponent of the memory used. So the maximum number of possible solvable equations rises exponentially with the amount of time your Turing machine can run. As a result, you get an ill-defined expectation when you try to compute the mean expected runtime of the terminating Diophantine exponentials — you don’t have a proper limit.

I think the best you can do is to take Dave’s suggestion: alternate between the two problems, and rely on the fact that -one- of them is (allegedly) guaranteed to terminate. At worst you’ll take twice as long as if you had picked the right one and worked on it exclusively.

dsquared 06.03.04 at 7:07 am

Shai: yes, that one came to me as I was shaving this morning. It’s much clearer if you think of it as being Alan Turing in Hell, being told that he’ll be let out when the machine in front of him halts.

Neel: Also yes. But note that the “badly-behaved” limit is the

correctone in this instance; if you formulate the problem this way, then it’s not open to you to decide that you’re going to take limits in a way which gives a useful answer.Bill: Similar answer – I seem to remember that I owe you an answer from the Holmes-Moriarty case which is similar to this one. There isn’t a well-behaved limit as N goes to infinity in this case (nor could there be one, otherwise we would be well on the way to a solution of the hlating problem).

Bill Carone 06.03.04 at 3:27 pm

Dsquared,

“There isn’t a well-behaved limit as N goes to infinity in this case”

If this is true, that means there is no answer, not that there is a paradox. Once you formulate it as a limit (even if the limit doesn’t exist), there is no sure-thing argument like there is in standard two-envelope problems (i.e. no matter what you see in envelope one, you prefer it to envelope two with its “infinite expectation”). Once that argument disappears, the paradox disappears as well.

Also, your argument seems to imply that we can’t solve even a finite problem: say N is the maximum time you are allowed to spend in Hell solving the problem (You’ve not been that bad, God can’t justify keeping you in there longer :-). Can you solve the problem now? It seems not if you claim that the probabilities “are unknowable.”

If you can’t solve the finite problem, then this is a different sort of difficulty than in Brian’s two-envelope problem.

OmerosPeanut 06.04.04 at 5:12 am

Wait, wait, wait.

Why is it “Hell” to have to do mathematics for an eternity? The statement of the problem appears to be missing something in my opinion.

Omeros P.

Anarch 06.04.04 at 3:21 pm

Also, your argument seems to imply that we canâ€™t solve even a finite problem: say N is the maximum time you are allowed to spend in Hell solving the problem.What does the problem even mean if you limit the time you’re permitted to stay?

Bill Carone 06.04.04 at 4:30 pm

“What does the problem even mean if you limit the time you’re permitted to stay?”

I might be completely confused, as I thought it was simple.

Doesn’t it make sense that, instead of staying in Hell for the amount of time it takes for the machine to halt, you stay in Hell for min(the amount of time it takes to halt, N)? In other words, after e.g. 3 millenia, God lets you out of Hell no matter what has happened with the equations?

Or am I completely off my rocker?

Comments on this entry are closed.