ec429 comments on Positive Bias: Look Into the Dark - Less Wrong

45 Post author: Eliezer_Yudkowsky 28 August 2007 03:55AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (53)

Sort By: Old

You are viewing a single comment's thread.

Comment author: ec429 16 September 2011 01:25:42AM 2 points [-]

Thought experiment. Suppose you have two oracles, and your task is to find out whether or not they have the same rule. If each oracle is considered as "A lookup table produced by a coin flip for each possible input, except that there's a 50% chance that the second is just a copy of the first" then of course any input is as likely as any other to exhibit a difference, and you can easily compute the probability of no difference after n tests fail to exhibit one. But if you have an assumption that simpler rules are more likely (eg. your prior is 2^-complexity) then what's your optimal strategy?

A plausible strategy is to follow the same strategy as you would if you had to find the rule of a single oracle; you always send the input that gives you the most bits about Oracle A's rule. That way, you maximise the probability of exhibiting a difference given that one exists. So if you can generate an input which, under your current model of the space of A's possible rules (and the probability of each), has exactly a 50% chance of matching A, then it also has a 50% chance of matching B; moreover these probabilities are independent, so you have 25%+25%=50% chance of exhibiting a difference. If instead you picked an input with a 30% chance of matching A, your chance of exhibiting a difference is 21%+21%=42%.