Capacities and efficient computation of first-passage probabilities

A reversible diffusion process is initialized at position $x_0$ and run until it first hits any of several targets. What is the probability that it terminates at a particular target? We propose a computationally efficient approach for estimating this probability, focused on those situations in which it takes a long time to hit any target. In these cases, direct simulation of the hitting probabilities becomes prohibitively expensive. On the other hand, if the timescales are sufficiently long, then the system will essentially “forget” its initial condition before it encounters a target. In these cases the hitting probabilities can be accurately approximated using only local simulations around each target, obviating the need for direct simulations. In empirical tests, we find that these local estimates can be computed in the same time it would take to compute a single direct simulation, but that they achieve an accuracy that would require thousands of direct simulation runs.

Figure 1

First-passage capacities allow efficient computation of hitting probabilities. We consider a reversible stochastic differential equation in an $n$-dimensional state space, initialized at some configuration $x_0$ inside a set $M$. What is the probability that the diffusion will reach region $A$ before $B$? We assume that the hitting probability is nearly the same for every initial condition $x_0\in M$—differing by at most $\varepsilon$ across all initial conditions. (See Theorem t5 for some sufficient conditions, involving small targets and/or high dimensions.) Theorem t4 establishes an approximation to the hitting probability that is accurate to within $\varepsilon +\sqrt{\varepsilon /2}$ and uses only “first-passage capacities.” These capacities can be computed from simulations that take place locally, meaning in the neighborhoods of the targets and entirely outside of $M$. Here we depict several examples. In each case, the first-passage capacities can be computed efficiently using simulations confined only to the areas shaded in gray.

Figure 2

Capacities and first-passage probabilities: Brownian motion. We consider three different cases (small, medium, and large), as illustrated on the left side. In each case we have two targets and are interested in the probability that a Brownian motion will first encounter target $A$ before target $B$. We consider 100 random initial locations, confined to be outside of the small black circles. For each location, we use 2000 runs of the diffusion to estimate the probability of hitting target $A$ before $B$. We plot these 100 estimates as a histogram. The histograms reveal that the hitting probabilities fall within a narrow range (0.0295, 0.0420, 0.1060 for small, medium, and large targets, respectively), especially when the targets are small. Moreover, we see that the location of this narrow range can be accurately predicted by the capacity-based approximation in Theorem t4 [$p_A$ from Eq. (9), shown as a dotted red line, 0.1104, 0.2219, 0.5000 for small, medium, and large targets, respectively]; the capacity-based approximation, derived from purely local computations within the neighborhoods of the targets, always falls inside the span of the histogram. We can further compare the capacity-based value to an estimate of the mean hitting probability for a process initialized at a random location, which is just the relative frequency of hitting $A$ before $B$ in 200 000 additional simulations from random initial conditions (shown as a solid red line, 0.0975, 0.2223, 0.4903 for small, medium, and large targets, respectively.)

Figure 3

Capacities and first-passage probabilities: nontrivial energy landscapes. See Fig. 2. The setup here is the same except that the targets $A$ and $B$ are only partially contained in $\mathrm{\Omega }$, and the energy landscapes become complicated near the targets. The histograms show that the first-passage probabilities are largely independent of starting location for the small and medium targets, as they were in the previous set of experiments. In contrast, the first-passage probabilities for the large targets depend strongly on starting location. This is expected, since these targets are substantially larger than the corresponding targets from the previous experiments. (The size difference is even bigger than it might appear, given that these figures represent two-dimensional slices of a five-dimensional region.) In contrast to the Brownian motion examples, the complex landscape in these examples precludes an exact evaluation of $p_A$ [Eq. (9)]. Hence the dotted red line represents the estimated value, ${\widehat{p}}_A$, computed using the shell method (cf. Fig. 2). Nonetheless, these estimates fall within the span of the respective histograms in all three examples. For small, medium, and large targets, the ranges of the 100 hitting probabilities are 0.0495, 0.0530, 0.6430, respectively; the capacity-based hitting probabilities (dotted lines) are 0.8217, 0.3815, 0.5219, respectively; the mean hitting probabilities (solid lines), estimated using 200 000 additional simulations from random initial conditions, are 0.8154, 0.3893, 0.5069, respectively.