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%.
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%.