Recursive Estimation of a Failure Probability for a Lipschitz Function

Let $g:\Omega=[0,1]^d\to\Bbb{R}$ denote a Lipschitz function that can be evaluated at each point, but at the price of a heavy computational time. Let $X$ stand for a random variable with values in $\Omega$ such that one is able to simulate, at least approximately, according to the restriction of the law of $X$ to any subset of $\Omega$. For example, thanks to Markov chain Monte Carlo techniques, this is always possible when $X$ admits a density that is known up to a normalizing constant. In this context, given a deterministic threshold $T$ such that the failure probability $p:=\Bbb{P}(g(X)>T)$ may be very low, our goal is to estimate the latter with a minimal number of calls to $g$. In this aim, we propose a recursive and optimal algorithm that selects on the fly areas of interest and estimate their respective probabilities. This is a joint work with Lucie Bernard, Albert Cohen, and Florent Malrieu.