Archive for August, 2010

That bet on P vs NP

21 August 2010 Leave a comment

Amid the recent brouhaha about Vinay Deolalikar’s purported proof of P≠NP (latest news here), the most interesting sideshow has been Scott Aaronson‘s 200,000$ bet against the validity of the proof. While some characterised it as nasty or irrational, I side with those who consider that there’s nothing nasty in stating one’s opinion clearly, and the purpose of this post is to show that’s it’s reasonable to assume the rationality of the bet and that it allows to derive a not-too-imprecise estimate of the probability of the correctness of the proof.

First, betting something against nothing, as Aaronson apparently did, is obviously irrational. However, the simple act of making the bet has already earned him peace of mind and online rep, so if he wins his bet, he’ll have made a net gain . It’s usually difficult to give a monetary equivalent for this, but here we can use the fact that he stated that he seriously considered cancelling his holiday, and thus assume that, to him, making the bet is worth the same as carrying on with his holiday plans, which in turn must be worth at least what he paid or intended to pay for it – let’s say 2,000$. This means that the implied odds for the bet are C = 1.01 (I’m using “continental” or “decimal” odds), or, to put it in another way, that Aaronson’s expectation is positive iff his probability of winning the bet is higher than 1/1.01 = 99.01\%.

However, the expectation doesn’t tell the whole story. The high risk associated with the bet means that it would be irrational to offer it if the expectation were just barely positive. The best way to quantify this is to use the so-called Kelly criterion, which states that the optimal fraction of the bankroll to bet is x = (Cp - 1)/(C - 1), where C is the odds for the bet and p is the true probability of winning the bet. Note that applying it implies the dubious, but not obviously false, assumption that Aaronson’s gain is proportional to his stake. In this case, the bankroll is roughly Aaronson’s total borrowing capacity, so let’s say that x = 0.5. To find the probability P he assigned to the correctness of the claimed proof, we just need to invert the Kelly formula: 1-P = (1 + (C-1)x)/C so P = (C-1)(1-x)/C

So, we finally get P = 0.5\%, which seems reasonable, now that we know that there are very good reasons to believe that Vinay Deolalikar is nowhere close to actually proving P≠NP.

Categories: Probability