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.

  • $\begingroup$ To minimize the number of evaluations of $f(n)$ you want to divide an interval into two equal probability partitions. Normally a binary search assumes a uniform distribution, which means dividing an interval length by 2 gives two equi-probable partitions. In your case dividing line will be closer to $\hat{n}$ than to other end of the interval. To know where to optimally pick that line requires a CDF or PDF. But you could guess and say, for example, that partition is $\frac{1}{3}$ interval length from $\hat{x}$. Then try algorithm with different values besides $\frac{1}{3}$. $\endgroup$ – Χpẘ May 22 '17 at 21:07
  • $\begingroup$ Why was this marked 'convex-optimization'? $\endgroup$ – Michael Grant May 23 '17 at 4:42

Your Answer

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

Browse other questions tagged or ask your own question.