# Bayesian Binary Search
## 2 Methodology
### Probabilistic Bisection Step
To prove that this algorithm converges, we know that as \(n\) approaches \(\infty\), \(2^{-n}\) approaches \(0\). Thus, as \(n\) approaches \(\infty\), the length of the interval approaches \(0\). Therefore, because \(\epsilon>0\), we know this algorithm converges. The rate of convergence depends on the probability distribution function. The algorithm is described below:
```
1 Num-Steps(\(Q,s,\epsilon\))
2\(i\gets 0\)
3\((p_{\text{lo}},p_{\text{hi}})\leftarrow(0,1)\)while\(Q(p_{hi})-Q(p_{lo})>\epsilon\)do
4\(p_{\text{mid}}\leftarrow\frac{p_{\text{hi}}+p_{\text{lo}}}{2}\)
5\(m\gets Q(p_{\text{mid}})\)
6 if\(s(m)=-1\)then
7\(p_{\text{lo}}\gets p_{\text{mid}}\)
8 else
9\(p_{\text{hi}}\gets p_{\text{mid}}\)
10\(i\gets i+1\)
11 return\(i\)
```

**Algorithm A1**Number of Steps Required for Bayesian Binary Search Convergence
#### a.3.3 Proving Worst-Case Time Complexity of BBS on Normal Distribution

The worst case of BBS on the normal distribution is when the target \(t\) approaches the left or right tail of the normal distribution. The proofs below assume that the target approaches \(Q(0)\). However, the same methods can be trivially applied to \(t\to Q(1)\). Given that the length of the probability interval is \(2^{-k}\) at iteration \(k\), if target \(t\to Q(0)\), then \(\mathcal{N}_{\text{conv}}\) can be found via

\[\mathcal{N}_{\text{conv}} =\operatorname*{argmin}_{n}\sum_{i=1}^{n}\Bigl{(}Q(2^{-(i-1)})-Q (2^{-i})\Bigr{)}\leq Q(1)-\epsilon\] \[=\operatorname*{argmin}_{n}Q(2^{-n})\leq\epsilon\]

After the first iteration, \(p_{hi_{1}}\) becomes \(2^{-1}\) and is repeatedly halved on each subsequent iteration. At each iteration \(k\), the searchable domain space is reduced by the quantity of the domain space to the right of \(Q(p_{hi_{2}})\). Subtracting the length of the domain space by the summation of the domain space reduced up to iteration \(k\) is equal to the length of the interval in terms of the domain space. Technically, \(Q(1)\) extends to positive infinity for the normal distribution; however, it is canceled out in the proof below. The proof below proves that the summation is equivalent to the simplified expression below it. **Proof by Induction**

Let \(P(n)\) be the statement

\(Q(1)-\sum_{i=1}^{n}\Bigl{(}Q(2^{-(i-1)})-Q(2^{-i})\Bigr{)}=Q(2^{-n})\) for all positive integers \(n\). **Basis step:**\(P(1)\) is true. \[P(1) =Q(1)-\sum_{i=1}^{1}\Bigl{(}Q(2^{-(i-1)})-Q(2^{-i})\Bigr{)}\] \[\frac{N}{2^{k}}\leq\epsilon\]0 \[\frac{N}{2^{k}}\leq\epsilon\]1

**Inductive step:** Assume \(P(k)\) is true for some integer \(k\geq 1\). Now, we show that \(P(k+1)\) must also be true:

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

\(\therefore\) We have shown using the principle of mathematical induction that \(P(n)\) is true for all positive integers \(n\). To prove \(t\to Q(0)\) and \(t\to Q(1)\) are the worst cases in terms of time complexity for targets in the normal distribution, we will prove that no other target takes longer to converge. **Theorem A1**. : _For a standard normal distribution with CDF \(F(x)\) and quantile function \(Q(x)=F^{-1}(x)\), the number of binary search steps required to achieve convergence within precision \(\epsilon\) is maximized when the target approaches \(Q(0)\) or \(Q(1)\)._

Proof. : We proceed by establishing several key properties of the quantile function and showing how they determine the convergence behavior of binary search. Let us first establish our framework. For any target \(t=Q(p)\) where \(p\in(0,1)\), the binary search algorithm maintains an interval \([p_{\text{lo}},p_{\text{hi}}]\) in probability space, corresponding to the interval \([Q(p_{\text{lo}}),Q(p_{\text{hi}})]\) in the domain space. **Lemma A1**. : _The derivative of the quantile function \(Q(x)\) is strictly increasing in magnitude as \(|x|\) increases toward the tails of the distribution._

Proof of Lemma A1.