# Bayesian Binary Search
## 2 Methodology
### Probabilistic Bisection Step
## Appendix A

### BBS on Imperfect Search Space Density Estimation

The performance of BBS depends on the accuracy of the search space density estimation. To demonstrate the performance of BBS on varying degrees of accuracy in search space density estimation, we run experiments in which the estimated search space probability density function is a given Kullback-Leibler (KL) divergence from the target normal distribution of the search space. We derive a new normal distribution with a specified KL divergence to a target distribution below:Given
* Target distribution: \(N(\mu_{1},\sigma_{1}^{2})\);
* Desired KL divergence: \(D\). We want to find parameters \(\mu_{2}\) and \(\sigma_{2}\) for a new distribution \(N(\mu_{2},\sigma_{2}^{2})\), such that \[KL(N(\mu_{1},\sigma_{1}^{2})||N(\mu_{2},\sigma_{2}^{2}))=D\] The KL divergence between two normal distributions is given by \[KL(N(\mu_{1},\sigma_{1}^{2})||N(\mu_{2},\sigma_{2}^{2}))=\log\frac{\sigma_{2} }{\sigma_{1}}+\frac{\sigma_{1}^{2}+(\mu_{1}-\mu_{2})^{2}}{2\sigma_{2}^{2}}- \frac{1}{2}\] For simplicity, let us assume \(\sigma_{2}=\sigma_{1}\). Then, the equation simplifies to \[D=\frac{(\mu_{1}-\mu_{2})^{2}}{2\sigma_{1}^{2}}\] Solving for \(\mu_{2}\), \[D =\frac{(\mu_{1}-\mu_{2})^{2}}{2\sigma_{1}^{2}}\] \[2D\sigma_{1}^{2} =(\mu_{1}-\mu_{2})^{2}\] \[\sqrt{2D\sigma_{1}^{2}} =|\mu_{1}-\mu_{2}|\] \[\mu_{2} =\mu_{1}\pm\sqrt{2D\sigma_{1}^{2}}\] We choose the positive solution \[\mu_{2} =\mu_{1}+\sqrt{2D\sigma_{1}^{2}}\] Therefore, the parameters of the new distribution are Figure 2:0 Figure 2:1 This ensures that Figure 2:2



Figure A2: Bimodal Distribution: Basic vs. BBS Convergence Comparison. \begin{tabular}{l l l l} \hline \(\mathbf{c}\) & **Percent Decrease** & **Basic Mean Steps** & **Bayesian Mean Steps** \\ \hline
1 & 12.86\% & 16.87 \(\pm\) 0.34 & 14.70 \(\pm\) 1.41 \\
2 & 13.03\% & 16.00 \(\pm\) 0.00 & 13.91 \(\pm\)



Figure A3: Exponential Distribution: Basic vs. BBS Convergence Comparison. Figure A4: Beta Distribution: Basic vs. BBS Convergence Comparison. ### Binary Search Tree Visualization Comparison

To visualize the difference between the execution of BBS and standard binary search in a normally distributed search space \(\mu=5\), \(\sigma=1.15\), we show binary search trees (BSTs) for basic binary search and BBS over 10,000 iterations of the experiment. We observe a significantly higher percentage of BBS searches terminating at a depth of 2, where all basic searches in this experiment terminate at a depth of 3 or 4. The bracket represents the search interval, and the number below for internal nodes represents the median of that search interval. The number below the bracket for the green leaf nodes represents how many times the search terminated at that leaf. Figure 2:3 Binary Search Tree. Theoretical Foundations of Probabilistic Search

The \"bisection\" algorithm, a strategy where the root is chosen to equalize the total weight of the left and right subtrees as much as possible (Rule II in the paper), relevant to our discussion, was rigorously analyzed in [24]. [PERSON]'s Theorem 1 provides an upper bound on the weighted path length (\(P_{balanced}\)) of a tree constructed according to Rule II, in terms of the entropy (\(H\)) of the frequency distribution:

Figure 2:4

where \(H=\sum\beta_{i}\log(1/\beta_{i})+\sum a_{j}\log(1/a_{j})\) is the entropy of the frequency distribution. The value of \((1-\log(\sqrt[3]{5}-1))^{-1}\approx 1.44\). This result provides a worst-case guarantee on the performance of the bisection-based tree construction in relation to the inherent uncertainty (entropy) of the data. Furthermore, Theorem 2 in the paper establishes a lower bound on the weighted path length (\(P_{opt}\)) of any optimal binary search tree for the same frequency distribution:

Figure 2:5

This lower bound shows that the performance of any search tree cannot be arbitrarily better than the entropy of the distribution.