0
$\begingroup$

A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$

The goal is to search for $n\ast$. The bounds $n_{min}$ and $n_{max}$ are known apriori.

A salient property of $n\ast$ is that it has a higher probability of lying in a region around $\hat{n}$ (known apriori). The exact probability distribution, although unknown, (probably doesn't matter) can be considered as continuous CDF having a higher weighting factor around $\hat{n}$

I have already implemented a simple binary search, but I am looking for more efficient solutions that somehow account for the given probability information (i.e. $n\ast$ is concentrated around $\hat{n}$), I am looking for an efficient algorithm to find $n\ast$. without losing accuracy.

I know that Binary search is worst-case $\mathcal{O}(log\ n)$, but $f(n)$ is so computationally expensive that I can't afford even this.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ What is "boolean search"? Do you mean binary search? If you know the CDF on the current range $[a,b]$ to which $n^*$ is known to belong, say the CDF is $F_{[a,b]}$, the optimal place to bisect is $F_{[a,b]}^{-1}(\frac12)$, which is around $\hat n$ at the beginning. As with binary search, the idea is that every step halves the worst-case (expected) number of possibilities. $\endgroup$ – Kirill May 22 '17 at 16:01
  • $\begingroup$ @Kirill, Edited the question to say 'Binary search'...But, If I begin bisection as per your suggestion, surely, I am bound to miss out if $n\ast$ happens to be outside this narrow search interval. I am looking for a robust algorithm that guarantees to find the answer, with a less than $\mathcal{O}(log\ n)$ worst-case iterations when searching in the neighbourhood of $\hat{n}$, but can accept worse performance in the region outside, i.e. the boundaries must not be permanently shifted inwards such that $\hat{n}$ bisects the reduced interval to start the search. $\endgroup$ – Krishna May 22 '17 at 20:06
  • 2
    $\begingroup$ I don't follow, what do you mean by narrow search interval? You do the same binary search, but each time you pick the bisector so that the probability of answer being on the left/right is $\frac12$ each. The resulting number of iterations will be roughly the binary entropy of your distribution. $\endgroup$ – Kirill May 22 '17 at 20:23
2
$\begingroup$

Since you have no derivatives for your function, you cannot beat bisection search in some asymptotic sense. But you can try to find good starting points for the bisection search.

For example, find $x_0$ so that $F(x_0)=\frac 12$ -- i.e., the most likely point for the switch point. Then, if $f(x_0)=0$, use $x_0$ as the left end point of your starting interval for the bisection search; otherwise, use it as the right starting point. In any case, $x_0$ is likely to be close to the final solution.

For the other starting point of your interval, let's assume for a moment that you had $f(x_0)=1$ -- i.e., that we are looking for a left end point $a_0$ of the interval, with $b_0=x_0$ being the right one. Try, for example, $\alpha$ as the point that is one standard deviation away from $b_0$, i.e., choose $\alpha$ so that $F(\alpha)=(1-0.95)=0.05$. If indeed $f(\alpha)=0$, then set $a_0=\alpha$ and you know that the switch point is in the interval $[a_0,b_0]$. If on the other hand, $f(\alpha)=1$, then the switch point is in fact to the left of $\alpha$, and you would set $b_0=\alpha$ and try again with $\alpha$ so that $F(\alpha)=(1-0.95)^2=0.05^2$. Then repeat until you finally have a starting interval where $f(a_0)\neq f(b_0)$. With this, you would then start your bisection search.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.