<p>This is addressed in the following paper of Karp and Kleinberg:</p>

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

<p>You can find a copy <a href="https://www.cs.cornell.edu/~rdk/papers/karpr2.pdf" rel="nofollow noreferrer">on Kleinberg's website</a>.</p>

CC BY-SA 4.0
2020-03-15T22:06:07.083Z
2020-03-15T22:06:07.083Z
Clement C.
<p>Let <span class="math-container">$f:[0,1] \to [0,1]$</span> be a smooth, monotonically increasing function.  I want to find the smallest <span class="math-container">$x$</span> such that <span class="math-container">$f(x) \ge 1/2$</span>.</p>

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

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

<p>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?</p>

<hr>

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

<p>I suspect something like the following might be better, for some constant <span class="math-container">$1/2 &lt; \alpha &lt; 1$</span>:</p>

<ol>
<li>Set <span class="math-container">$x := 1/2$</span> and <span class="math-container">$d := \alpha$</span>.</li>
<li>Repeat some fixed number of times:

<ul>
<li>Query the black box on <span class="math-container">$x$</span>.  If it returns 1, set <span class="math-container">$x := x + d$</span>, otherwise set <span class="math-container">$x := x - d$</span>.</li>
<li>Clip <span class="math-container">$x$</span> to the range <span class="math-container">$[0,1]$</span>.  Set <span class="math-container">$d := \alpha d$</span>.</li>
</ul></li>
</ol>

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

<p>Is there a good way to choose <span class="math-container">$\alpha$</span>?  Or, is there a better strategy?</p>

<pr.probability><randomized-algorithms><st.statistics>
Binary search on coin heads probability
D.W.
# Binary search on coin heads probability

(Asked by: username_0 on 2020-03-15)

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 < \alpha < 1$:

1. Set $x := 1/2$ and $d := \alpha$.
2. 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?

**Tags:** pr.probability, randomized-algorithms, st.statistics


---

## 1 answers

### Answer by username_1 on 2020-03-15. Score: 4 | Accepted answer

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](https://www.cs.cornell.edu/~rdk/papers/karpr2.pdf).


---

