Installation

Install from PyPI:

$ pip install pba_waeber2013

Usage

This module provides a single public function:

>>> from pba_waeber2013 import pba_waeber2013
>>> pba_waeber2013(
...         f, a, b, *
...         tol=None,
...         rtol=None,
...         alpha=0.05,
...         p_c=0.65,
...         maxiter=1000,
...         check_bounds=False,
...         slope=None,
...         args=None,
...         kwargs=None,
... )

Below are brief descriptions of the parameters:

f

The stochastic function of interest. This function can take any number of arguments (see args and kwargs), but the first should be the x coordinate to evaluate the function at.

a b

The lower and upper bounds, respectively, on where the root can occur. There must be exactly one root in this interval.

tol

How narrow the confidence interval needs to be in order for the algorithm to be converged. Note that if neither tol nor rtol are specified, the algorithm will just run for the maximum number of iterations.

rtol

Similar to tol, but multiplied by the estimated root.

alpha

A parameter controlling the width of the confidence intervals. Specifically, the confidence level is given by 1 − alpha. In other words, for 95% confidence intervals, set alpha to 0.05.

p_c

Repeatedly evaluate the function at each x coordinate until we can reject the null hypothesis that f(x) = 0 with probability p_c. At that point, the sign of f(x) will be taken as whichever sign we observed most often.

maxiter

The maximum number of function calls to make.

check_bounds

Evaluate the function at the bounds a and b before starting the bisection. This achieves two things. First, it checks that the bounds have different signs. If this is not the case, then there are either 0 or >1 roots in the interval, and so this algorithm is not applicable. Second, it determines the slope of the function. If the bounds are not checked, the slope parameter must be manually specified.

slope

+1 if the function is increasing (i.e. negative before the root and positive after) or -1 if the function is decreasing. A slope must be given unless check_bounds is True (in which case it will be calculated internally).

args

Any extra arguments to pass to the function on each evaluation.

kwargs

Any extra keyword arguments to pass to the function on each evaluation.

The return value is an object with the following attributes:

x

The location of the root.

x_obs

All of the x coordinates where the function was evaluated.

f_obs

The result of evaluating the function at each of the above x coordinates.

x_post

The bin edges of the posterior distribution.

log_p_post

The natural logarithms of the bin heights of the posterior distribution. Logarithms are used to avoid multiplication overflows.

ci

The confidence interval evaluated independently after a sign is determined for each coordinate. Note that these intervals can grow and shrink over time. See [Waeber2013] §3.3 for more information.

ci_seq

The sequential confidence interval. Unlike the ci intervals, these are guaranteed to never expand. For that reason, these are the intervals used to check for convergence.

converged

True if the algorithm terminated because the confidence interval grew narrower than the given tolerance, False if the algorithm terminated because it reached the maximum number of iterations.

References

• Waeber R. (2013) “Probabilistic bisection search for stochastic root-finding.”

• Frazier PI, Henderson SG, Waeber R (2016) “Probabilistic bisection converges almost as quickly as stochastic approximation”, arXiv:1612.03964

• Robbins H and Siegmund D. (1974) “The expected sample size of some tests of power one”, The Annals of Statistics, 2(3), pp. 415–436. doi:10.1214/aos/1176342704.