# Bayesian Binary Search
## 2 Methodology
### Probabilistic Bisection Step
The fact that the upper bound for the balanced tree (constructed by the bisection-like Rule II) is within a constant factor of this lower bound demonstrates the near-optimality of this simple algorithm. Recent work by [25] complements these findings by considering the scenario where the prediction of the distribution itself might be imperfect. They present an algorithm with a query complexity of \(O(H(p)+\log\eta)\), where \(H(p)\) is the entropy of the true distribution \(p\), and \(\eta\) is the Earth mover's distance (EMD) between \(p\) and the predicted distribution \(\beta\)[cite: 8]. This result shows that the search complexity depends not only on the entropy of the true distribution but also on the accuracy of the predicted distribution. Notably, they also provide a lower bound demonstrating that this query complexity is asymptotically tight. ### Theoretical Analysis: General Convergence Proof and Worst Case for Normal Distribution Terms:

Domain/Search Space: \(x\in[a_{0},b_{0}]\), where \(a_{0},b_{0}\in\mathbb{R}\) and \(a_{0}\leq b_{0}\);

Unknown Target: \(t\in[a_{0},b_{0}]\);

Sign Function: \(s(x)= \begin{cases}1&x>t\\ -1&x\leq t\end{cases} \);

Boundary Conditions: \(s(a_{0})=-1\), \(s(b_{0})=1\);

Tolerance: \(\epsilon>0\). ### Proof of Convergence of Bisection Method on Domain Space

Algorithm Description

The bisection method starts with an initial interval \([a_{0},b_{0}]\) such that \(s(a_{0})=-1\) and \(s(b_{0})=1\). The interval is halved at each step, and the new interval is chosen based on the sign of the function \(s\) at the midpoint. This process is repeated until the length of the interval is less than or equal to a specified tolerance \(\epsilon\), where \(\epsilon>0\). Let the length of the initial interval be \(N=b_{0}-a_{0}\). At each iteration, the interval is halved, so after \(k\) iterations, the length of the interval becomes

\[\text{Length of interval after $k$ iterations}=\frac{N}{2^{k}}\]

Stopping Condition

The method stops when the length of the interval is less than or equal to \(\epsilon\), i.e., when

\[\frac{N}{2^{k}}\leq\epsilon\]

Solving for \(k\), we get

\[2^{k}\geq\frac{N}{\epsilon}\]

Taking the logarithm (base 2) of both sides,

\[k\geq\log_{2}\biggl{(}\frac{N}{\epsilon}\biggr{)}\]

Thus, the number of iterations \(k\) required to achieve the desired tolerance \(\epsilon\) is

\[k=\biggl{\lceil}\log_{2}\biggl{(}\frac{N}{\epsilon}\biggr{)}\biggr{\rceil}\]Appendix A.3.2. Proof of Convergence of Bisection Method on Probability Density Space Algorithm Description

Given the same framework of terms as above, in addition to

\[\underset{\text{percentile}}{p=F(x)}=CDF(x)=\int_{-\infty}^{x}pdf(x)dx,p\in(0,1)\] (A1)

\[\underset{\text{domain value}}{\underline{x}}=Q(p)=F^{-1}(p)\] (A2)

Bisecting on probability density space is similar to the above method where we bisect on the domain space. The key difference is that rather than bisecting the domain space with an initial interval of \([a_{0},b_{0}]\), we will bisect the probability space with an initial interval of \((0,1)\), i.e., \((p_{l_{0o}},p_{li_{0}})\), where \(s(Q(p_{l_{0o}}))=-1\) and \(s(Q(p_{li_{0}}))=1\). Our search space then becomes \(p\in(0,1)\), and at each iteration, we will cut the percentile interval in half. Stopping Condition

Define the length of the interval as \(p_{hi_{n}}-p_{l_{0n}}\). At iteration \(0\), \(1-0=2^{0}\). At iteration \(1\), the interval could be \((0,0.5]\) or \([0.5,1)\), where the length of both ranges is \(2^{1}\). Because the percentile interval is cut in half at each iteration, we know that the length of the interval at iteration \(k\) is \(2^{-k}\). So, at iteration \(k\), the interval is equivalent to \([p_{l_{0k}},p_{l_{0k}}+2^{-k}]\). Note that the left or right side of the interval may remain open if \(p_{lo}\) remains \(0\) or \(p_{hi}\) remains \(1\) throughout the duration of the algorithm, respectively. We can then rewrite our stopping condition of \(Q(p_{hi_{n}})-Q(p_{l_{0n}})\leq\epsilon\) as \(Q(p_{l_{0n}}+2^{-n})-Q(p_{l_{0n}})\leq\epsilon\).