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$ I'm not sure you can do anything substantive without further assumptions. $\endgroup$ – Yuval Filmus May 22 '17 at 20:27

If you knew the distribution of $n^*$, you could find an optimal binary decision tree (there are several $O(n\log n)$ algorithms) in terms of expected number of queries (you can't beat binary search if you care about worst case). There are also two simple algorithms which are nearly optimal. I will describe them as algorithms for locating $n^*$ given queries of the form "$n^* \leq x$", which you can easily implement by checking $f(x)$. We assume that the probability that $n^* = i$ is $p_i$.

Gilbert–Moore algorithm: Partition the unit interval $[0,1]$ into intervals of length $p_i$, and let $x_i$ be the midpoint of the $i$th interval. We locate $n^*$ by doing binary search on $[0,1]$. For an interval $I \subseteq [0,1]$, denote by $X(I)$ the midpoints $x_i$ which are found in $I$. We first ask whether $n^* \in X([0,1/2])$. Depending on the answer, we ask whether $n^* \in X([0,1/4])$ or whether $n^* \in X([1/2,3/4])$; and so on. Eventually we reach an interval $I$ such that $X(I)$ is a singleton, and we have found $n^*$.

Horibe's algorithm: Find $x$ that minimizes $|\Pr[n^* \leq x] - 1/2|$, and ask whether $n^* \leq x$. Denote by $I$ the values of $n^*$ conforming to the answer. Find $x$ that minimizes $|\Pr[n^* \leq x \mid n^* \in I] - 1/2|$, and ask whether $n^* \leq x$. Update $I$, and repeat until $I$ becomes a singleton.

Both algorithms find $n^*$ using at most $H(n^*)+2$ queries on average (where $H(n^*)$ is the entropy of $n^*$), compared to the trivial lower bound $H(n^*)$, so they're pretty good.

In your case, you don't know the distribution of $n^*$, but you can make a guess, use one of these algorithms, and hope for the best. If you have several distributions in mind, you can choose one of them to construct an algorithm, and then check their performance on the other distributions, comparing the expected number of queries to the trivial lower bound.

You could also want to optimize some other quantity – for example, the 99th percentile of the number of queries. In that case the algorithms described above will probably still be pretty reasonable.

  • $\begingroup$ much appreciate your answer. I am not a CS person, so it will take me a few minutes to understand the algorithm. If I don't have an "exact" probability distribution, can I still use the algorithms you mentioned? i.e. if I just knew that the optimal value is most likely to occur within +/-25 around 72 ($\hat{n}$), is it still feasible to apply these algorithms? i.e. are the algorithms robust enough to tolerate if the assumed cumulative density function turns out to be only qualitatively correct, but inexact $\endgroup$ – Krishna May 22 '17 at 20:51
  • $\begingroup$ The input to the algorithms is a distribution. You can empirically test their robustness by "training" them on one distribution and "testing" on another. $\endgroup$ – Yuval Filmus May 22 '17 at 21:44

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.