ec429 comments on Positive Bias: Look Into the Dark

• Thought ex­per­i­ment. Sup­pose you have two or­a­cles, and your task is to find out whether or not they have the same rule. If each or­a­cle is con­sid­ered as “A lookup table pro­duced by a coin flip for each pos­si­ble in­put, ex­cept that there’s a 50% chance that the sec­ond is just a copy of the first” then of course any in­put is as likely as any other to ex­hibit a differ­ence, and you can eas­ily com­pute the prob­a­bil­ity of no differ­ence af­ter n tests fail to ex­hibit one. But if you have an as­sump­tion that sim­pler rules are more likely (eg. your prior is 2^-com­plex­ity) then what’s your op­ti­mal strat­egy?

A plau­si­ble strat­egy is to fol­low the same strat­egy as you would if you had to find the rule of a sin­gle or­a­cle; you always send the in­put that gives you the most bits about Or­a­cle A’s rule. That way, you max­imise the prob­a­bil­ity of ex­hibit­ing a differ­ence given that one ex­ists. So if you can gen­er­ate an in­put which, un­der your cur­rent model of the space of A’s pos­si­ble rules (and the prob­a­bil­ity of each), has ex­actly a 50% chance of match­ing A, then it also has a 50% chance of match­ing B; more­over these prob­a­bil­ities are in­de­pen­dent, so you have 25%+25%=50% chance of ex­hibit­ing a differ­ence. If in­stead you picked an in­put with a 30% chance of match­ing A, your chance of ex­hibit­ing a differ­ence is 21%+21%=42%.