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.