Suppose you're certain 1000:1 that the coin is fair. The only coin flip outcomes worth considering are runs of heads (obviously once you see a single outcome of tails, you're done).
If you ask for k=5 or more coin flips, then you can only be wrong if the coin is fair but ended up doing HHH...HH anyway, which is long enough to convince you. This has probability less than 1/2^k (since Pr[fair coin] < 1). At that point, every additional coin flip is worth a ridiculously tiny amount you can solve for.
If you ask for fewer than 5 coin flips, then no sequence of coin flips you see will convince you that the coin isn't fair with probability over 50%, and you'll just end up betting on that no matter what you see. So these coin flips are worthless unless you will have the chance to buy more.
The "either 2/3 or 1/3" coin is actually worse in the scary-zeroes department. The nice feature of both the 2d6 and the double-heads coins is that they completely lack an outcome, so no matter what your prior is, if you are currently considering betting on these, there is a small chance you'll be convinced not to.
On the other hand, if both coins can come up both heads and tails, then a single extra flip is worthless unless your prior odds are between 2:1 and 1:2 -- no matter what outcome you see, your belief will shift in one direction or the other by exactly one bit. It's like a biased random walk on the number line, and you don't know what the bias is. But no matter where you are, there's always some number of coin flips that will be worth buying (all at once), although potentially the price you'd pay for them would be really tiny.
I posted this problem to my own blog the other day. When I posted it, I thought it looked very easy, more fiddly than difficult:
I reasoned thus:
There's no reason that you should have any opinion on which piece of paper he's brought. So you start off thinking 50:50, and that leads you to believe that he's effectively just given you £500.
If he tells you a number, then your belief will change. Say he tells you 1, then you know that he's brought the 1D12 results, and so you're now able to tell him that, and collect your £1000.
If he tells you 7, then that's twice as likely to be the 2D6 talking as the D12, and you should shift your prior to 1:3.
If you've got a prior of 1:3, then your guess (that it's the 2D6) is now worth £750, on average.
So when you get a new number, your prior shifts, the bet changes value. Average over all the cases and that's what you'll pay to know the first number.
Using this reckoning, I thought the answer to the puzzle was £125.
But now I'm not so sure, because the same reasoning tells you that if, for whatever reason, you start out 9:1 in favour of the 1D12, then the value of the new information is zero. (Because whatever the new information is, it won't be enough to change your mind).
But can that really be true? Because that implies that if Omega keeps making you the same offer for £1, then you should keep turning it down.
But if he told you a hundred numbers, you'd be damned sure which piece of paper he'd brought. So surely they have some value over £1?
But maybe you say: "Well, you can't put a value on the information unless you know how many extra opportunities you'll get."
Really? I'm sure that I'd pay £1 for the number in the original problem, and sure that I wouldn't pay £1000.
Where am I mis-thinking, and how should I calculate the answer to my puzzle?
Edit:
Just to clarify, if you buy the first number and it's a 2, and then you buy the second number and it's a 12, then I think you're now back in the same situation with a prior of 9:1 and an expected gain of £900.
I think you'd be mad to stop buying numbers at this point, since there's £100 you're not certain of yet. But if I don't believe that the price is £0, why do I believe that the price for the first one is £125?
Edit II:
It seems that the opinion of most people is that the problem is under-determined, in the sense that you don't know what options are coming. Fair enough.
In which case, what's wrong with the intuition that your beliefs alone determine the worth of your option to guess?
And in the more specific version where Oswald charges a price of one penny for every result, and you can keep buying them one-by-one until you decide you're certain enough and guess, what criterion do you use to stop guessing?