Binary search on coin heads probability Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function.  I want to find the smallest $x$ such that $f(x) \ge 1/2$.

If I had a way to compute $f(x)$ given $x$, I could simply use binary search on $x$.  However, I don't have a way to compute $f(x)$.  Instead, I have a black box that, on input $x$, flips a biased coin and outputs 1 with probability $f(x)$ and 0 with probability $1-f(x)$.  I can invoke the black box as many times as I want.

I'm looking for a query-efficient strategy to approximate $x^* = \min \{x : f(x) \ge 1/2\}$.  Is there an efficient algorithm?  I would be happy with strategies where we assume a fixed upper bound on $f'(x)$.

Informally, we can summarize the problem as: I have a coin whose heads probability depends in some unknown but monotonic way on a parameter; how can I choose the minimum value of that parameter to ensure the coin is biased in my favor?



A naive approach is to estimate $f(x)$ for any $x$ by invoking the black box $k$ times on the same input $x$, then use binary search with this estimator.  However, I suspect this makes more queries than necessary.  Intuitively, it makes many queries in regimes where $|x-1/2|$ is large, and the estimator for $f(x)$ doesn't use information from the black box on queries $x'$ that are near to $x$.

I suspect something like the following might be better, for some constant $1/2 &lt; \alpha &lt; 1$:


Set $x := 1/2$ and $d := \alpha$.
Repeat some fixed number of times:


Query the black box on $x$.  If it returns 1, set $x := x + d$, otherwise set $x := x - d$.
Clip $x$ to the range $[0,1]$.  Set $d := \alpha d$.



However I'm not sure how to set $\alpha$ or how to analyze this approach.  (Note that if $\alpha=1/2$ and the black box returned whether or not $f(x)\ge 1/2$, this strategy would devolve to binary search.)

Is there a good way to choose $\alpha$?  Or, is there a better strategy?
This is addressed in the following paper of Karp and Kleinberg:


  Karp, Richard M.; Kleinberg, Robert. Noisy binary search and its applications. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 881--890, ACM, New York, 2007. 


You can find a copy on Kleinberg's website.