oscarbonilla.com

So I was browsing Concrete Mathematics by Don Knuth et al, and I found a proof that P=NP for small N[1]. However if you make P=0, the size of N doesn’t matter. So if P=0, then P = NP. Where is my money?

1. Specifically for N=1. It’s in the margin of the book [↩]

A recent thread in reddit about the two envelopes problem reminded me of how unintuitive probabilities can be. There is a fundamental flaw with how the original post worded the problem:

You and I both have envelopes filled with money. My envelope contains either double or half the amount of money that’s in yours. If you want, I’m going to let you switch envelopes. Should you stay, switch, or does it not matter?

Stop right there. Read that again. Does that make sense to you? See if you can set up the experiment in the real world. Grab two envelopes and some money. Take $100 and put them in an envelope, then, uh… what do you do with the other envelope? Put $50 in it? Put $200?

The original poster then went ahead and solved assuming probabilities of 1/2. But I’m not really choosing between two equally likely options. I don’t know the probability distributions!

A better wording for the problem (or a different problem if you’re pedantic) would be:

There are two envelopes. One contains double the amount of money than the other. You choose one of them, I take the other. Now I offer you a choice between keeping your original choice or switching envelopes with me. Is it to your advantage to switch?

The answer should be obvious, it doesn’t matter.