Probabilistic Bisection Search For Stochastic Root-Finding

Other Titles


The goal of a stochastic root-finding algorithm is to locate a point x* such that g (x* ) = 0 for a given function g that can only be observed with noise. In this thesis we investigate the performance of the Probabilistic Bisection Algorithm (PBA), which is a one-dimensional stochastic root-finding algorithm motivated by the wellknown bisection search method. In each step, the PBA queries the function g as to whether the root lies to the left or right of a prescribed point x. Due to observational noise, the answer to each query has probability 1 [-] p(x) of being incorrect. To account for such possibilities of incorrect observations, the algorithm updates in each iteration a probability density that represents, in some sense, one's belief about the true location of the root x* . The PBA was first introduced in Horstein (1963) under the setting where p([MIDDLE DOT]) is constant and known. While the method works extremely well in this case, very little is known to date about its theoretical properties or potential extensions beyond the current setting for p([MIDDLE DOT]). The first part of this thesis provides several key findings about the PBA where p([MIDDLE DOT]) is constant and known. Collectively, they lead to the first main conclusion that the expected absolute residuals of successive search results converge to 0 at a geometric rate. In the second part, we consider the case where p([MIDDLE DOT]) is unknown and varies with x. At each query point, the function g is evaluated repeatedly until a lower bound on the probability of obtaining a correct updating signal is achieved. We first construct a true confidence interval for x* and prove that its length converges to 0 in the number of query points. Next, we show that, provided a reasonable conjecture ˆ holds, the PBA can be used to construct a sequence of estimators (XT )T such that ˆ the expected absolute residuals E[|XT [-] x* |] converge to 0 at the rate O(T [-]1/2+[epsilon] ) for any [epsilon] > 0, where T is the number of overall function evaluations. This rate is only slightly slower than O(T [-]1/2 ), which is the well-established upper bound on the convergence rate of stochastic root-finding problems.

Journal / Series

Volume & Issue



Date Issued




Probabilistic Bisection; Stochastic Root-Finding; Simulation-Optimization


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Henderson, Shane G.

Committee Co-Chair

Frazier, Peter

Committee Member

Jarrow, Robert A.
Todd, Michael Jeremy

Degree Discipline

Operations Research

Degree Name

Ph. D., Operations Research

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record