Binary chop with uncertain test

[jack]

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

Comments

[simont]

This is straight off the top of my head and I haven't proved it optimal, but intuitively it seems like a plausible starting point:

Keep track of the probability, for each stage, that that stage is the faulty one. Initially, you have no idea, so they're all set at probability 1/N, and after every test you do a Bayesian update which of course preserves the invariant that they all sum to 1. Now, at every step, divide the stages such that as close as possible to half the total probability lies before the stage you test, and half lies after it. So the first test will be in the middle, as with an ordinary binary chop, but the second test will be skewed just a little towards the centre from the 1/4 or 3/4 point, to account for the fact that some probability still remains in the half that the test believed clean, and so on.

[mair_in_grenderich]

damn, I've done something very similar this to solve some problem in the past, but now I can't remember what the problem was. Now that's annoying me.

[mairs_book_reviews]

(this, possibly: http://jack.dreamwidth.org/722173.html)

[simont]

Mmm, yes, that did occur to me as similar to this question. Though of course this one is easier, due to the more restricted forms of question available.

[jack]

Doh! How did I completely forget that (which looks to be exactly the same...) Thanks for finding it.

[mair_in_grenderich]

had a vague memory of sitting in a canadian cafe while an alsation walked by with a pink teddy bear, scratching in my notebook in pencil. me scratching, not the alsation. that narrowed down the time quite precisely, so i had a look at your posts from that time in case it was one of your problems i was thinking of and turned out it was.

in other ambiguity news i saw this headline "muslims in china fed pork", misread it as "muslims in china-fed pork" and thought the muslims were in the pork. (see also: soylent green). it turned out to be rather less devastating than that, but may have been a consequence of sleepy brain not genuine ambiguity.

[ciphergoth]

Intuitively the right dividing line to choose is the one that maximises the expected information from the query.

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.