Binary chop with uncertain test
Oct. 5th, 2013 06:04 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackSuppose I have a sequence of N stages, one of which is anomalous, and I can test one of the stages which tells me if the anomalous stage is before or after that stage. The natural way to isolate the anomalous stage is a binary chop: to test the middle stage, finding out which half is anomalous, and then divide that half into two, etc.
However, if my test is only p=90% accurate, is any other method better? My instinct says "do the same thing, but repeat the test until you're effectively certain". But I always wonder if something else works better.
I'm thinking of debugging. To a mathematician, debugging (or any scientific method) is a MASSIVELY COMPLICATED binary chop. But I always feel like I'm getting the level of certainty wrong. Either I'm not 100% certain I'm testing the right thing and need to go over, or I'm wasting too much time when the problem would have become apparent if I ploughed ahead even if I wasn't sure my test was accurate.
However, if my test is only p=90% accurate, is any other method better? My instinct says "do the same thing, but repeat the test until you're effectively certain". But I always wonder if something else works better.
I'm thinking of debugging. To a mathematician, debugging (or any scientific method) is a MASSIVELY COMPLICATED binary chop. But I always feel like I'm getting the level of certainty wrong. Either I'm not 100% certain I'm testing the right thing and need to go over, or I'm wasting too much time when the problem would have become apparent if I ploughed ahead even if I wasn't sure my test was accurate.
no subject
Date: 2013-10-07 09:26 pm (UTC)What you *actually* want to do is minimize the number of subsequent queries, but I'd be a bit surprised if there was a tractable way to do that exactly.