Archive

Archive for the ‘Probability’ Category

That bet on P vs NP

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.