Back to search

Cornell University

Probabilistic Bisection Search For Stochastic Root-Finding

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research
Grantor
Cornell University
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Waeber, Rolf
Chair dc:contributor.chair
  • Henderson, Shane G.
Committee members dc:contributor.committeemember
  • Jarrow, Robert A.
  • Todd, Michael Jeremy

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
8267611

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Waeber, Rolf. Probabilistic Bisection Search For Stochastic Root-Finding. Doctor of Philosophy thesis, Cornell University, 2013. https://hdl.handle.net/1813/33929