Here is a doc explaining a Bayesian search algorithm; not sure if it's precisely what GP has in mind.

https://github.com/Ealdwulf/BBChop/blob/master/BBChop/doc/Ba...

(Edit- had wrong link originally)

Thanks!

For Bayesian Inference, the example in the Wikipedia article is good (who doesn't like cookies?): https://en.m.wikipedia.org/wiki/Bayesian_inference#Examples

When gathering more evidence, you'd use your new belief about which cookie bowl Fred has as P(H1)=0.6 and P(H2)=0.4

That just explains Bayesian inference in general, which is useful, but not what I'm after.

I was specifically interested in the application to binary search / bisection in the presence of flaky tests.

You apply the same process, but your hypotheses are "bug is before/after this bisection point". Your "probability of evidence given hypothesis before/after" are where you incorporate your guess about the tests flakiness. Still works even if you don't have "true" numbers for the tests flakiness, just won't converge as quickly

J

H

The Probabilistic Bisection Algorithm by Horstein, original paper is "Sequential transmission using noiseless feedback," IEEE Trans. Inform. Theory, 9(3):136–143. https://ieeexplore.ieee.org/document/1057832

Here's a nice presentation on an analysis of the method, references start on slide 47

https://people.orie.cornell.edu/pfrazier/Presentations/2014....

Paraphrasing the theorem from Jedynak, Frazier, Sznitman (2011):

Suppose [flake probability] is constant, known, and bounded away from 1/2, and we use the entropy loss function. ... The policy that chooses [next test point] at the median of [current posterior distribution] is optimal.

And some python code that implements a version of the analysis

https://github.com/choderalab/thresholds/blob/master/thresho...

Thanks!