The "weighted ensemble" path sampling method is statistically exact for a broad class of stochastic processes and binning procedures

Bin W. Zhang; Daniel M. Zuckerman; David Jasnow

Source-linked AI summary

The "weighted ensemble" path sampling method is statistically exact for a broad class of stochastic processes and binning procedures

Bin W. Zhang, Daniel M. Zuckerman, David Jasnow

arXiv:0810.1963v3Oct 10, 2008physics.comp-phphysics.chem-ph

TL;DR

Rare-event path sampling needs rigorous methods that remain valid beyond Markovian dynamics and fixed binning. This paper recasts weighted ensemble as path-space resampling and shows that it is statistically exact for broad Markovian and non-Markovian dynamics, with arbitrary changing bins also valid. Numerical examples include adaptive bins that find a target state in a simple model.

Problem
Earlier weighted-ensemble studies considered Markovian dynamics, leaving its validity for non-Markovian processes and changing bin procedures to establish.
Method
The paper derives weighted ensemble using path-probability ideas and interprets it as resampling trajectories at occasional time points.
Results
WE produces unbiased results for a broad class of Markovian and non-Markovian dynamics, while bins can be changed during simulation.
Takeaways & Limitations
Adaptive bin redefinition can proceed without knowledge of the target state and eventually lead to successful transitions in a toy system.

Abstract

from arXiv · show

The "weighted ensemble" method, introduced by Huber and Kim, [G. A. Huber and S. Kim, Biophys. J. 70, 97 (1996)], is one of a handful of rigorous approaches to path sampling of rare events. Expanding earlier discussions, we show that the technique is statistically exact for a wide class of Markovian and non-Markovian dynamics. The derivation is based on standard path-integral (path probability) ideas, but recasts the weighted-ensemble approach as simple "resampling" in path space. Similar reasoning indicates that arbitrary nonstatic binning procedures, which merely guide the resampling process, are also valid. Numerical examples confirm the claims, including the use of bins which can adaptively find the target state in a simple model.

I. INTRODUCTION

The paper establishes that weighted ensemble produces unbiased results for broad Markovian and non-Markovian dynamics, while permitting arbitrary bins that can change during simulation. It recasts WE as path-space resampling, including adaptive binning that can eventually find a target state.

Contributions: The paper aims to establish two facts about weighted ensemble: unbiasedness for broad stochastic dynamics and validity of changing bins.These claims extend the method beyond the Markovian setting and static binning considered in earlier studies.
Contributions: WE produces unbiased results for a broad class of stochastic dynamics, including non-Markovian processes.The authors therefore describe the original “weighted ensemble Brownian dynamics” title as overly restrictive.
Resampling interpretation: WE resampling generates an alternative but statistically equivalent trajectory sample without biasing future evolution.Because dynamical information derives from the trajectory ensemble, the resulting results are fully unbiased.
Flexible binning: Bins control resampling but may be dynamically redefined during simulation, including adaptively without prior knowledge of the target state.A simple model demonstrates adaptive redefinition that eventually leads to successful transitions.
Flexible binning: The adaptive approach opens the possibility of exploring configurational changes not already described by experimental structures.This consequence is stated within the paper’s discussion of adaptive target finding.

II. THEORY

Weighted ensemble divides state or configuration space into bins, propagates weighted trajectories, and resamples them to enrich rare-event information while preserving total probability weight.

Procedure: WE divides real or configurational space into arbitrary bins that may change during simulation.For exposition, the paper sometimes assumes static bins leading sequentially toward a target state.
Procedure: Trajectories are initialized with weights, propagated for short intervals, and repeatedly resampled according to their current bins.The procedure repeats until the desired information is obtained.
Procedure: Trajectories entering new bins are split into identical daughters sharing the parent’s weight and history.When bins contain too many trajectories, probabilistic killing maintains a total weight of one and no more than NM trajectories across N bins.
Outputs: The weighted trajectory ensemble contains information for transition rates, transition probabilities, evolving configurational distributions, and intermediate states.Arrival probability can provide the rate in simple cases, while the ensemble also supports structural analysis.
Outputs: A steady-state WE procedure can also calculate transition rates.The paper notes this as a more general alternative to estimating rates from an arrival-probability plateau.

B. Resampling

Resampling replaces an initial sample with a statistically equivalent weighted sample, allowing elements to be discarded, duplicated, or reweighted without changing the represented distribution.

Examples: Discarding half of zero-mean Gaussian numbers on the left and doubling their weights preserves correct resampling.Duplicating right-side numbers with half weights is another valid procedure, and both procedures may be combined.
Examples: Repeated simulation shows that sparse left-side and dense right-side samples can still represent the original distribution correctly.The validity follows by averaging over repeated sample-generation and resampling processes.
Definition: Resampling creates an alternative but statistically equivalent sample of a fixed probability distribution.The new sample may contain a subset of original elements with different frequencies and compensating weights.
Definition: The resampled sample may be larger or smaller than the original, depending on the desired procedure.This flexibility is part of the general resampling construction.
Path-space application: Resampling applies to arbitrary-dimensional objects, including vectors representing dynamical processes or discretized trajectory histories.This makes trajectory distributions natural objects for resampling in path space.

C. Statistical description of discretized, stochastic trajectories

The paper represents discretized stochastic trajectories through conditional dynamics and their path probabilities, treating trajectory distributions as high-dimensional probability distributions suitable for path-integral analysis.

Discretized dynamics: The discretized dynamics select the current configuration x_j probabilistically from the trajectory’s previous history.The conditional distribution depends on the previous k trajectory steps.
Discretized dynamics: The special case k = 1 is Markovian, whereas k > 1 permits dependence on multiple previous steps.For j < k, an operational initialization rule is required.
Path probability: The full n-step trajectory probability is constructed from the initial distribution and subsequent conditional probabilities.This explicit path-probability description applies to dynamics governed by the stated history-dependent rule.
Path probability: Trajectory distributions can be treated as high-dimensional equilibrium distributions, enabling path-integral methods.The paper identifies this representation as the basis for analyzing stochastic trajectories.
Configuration-space distribution: The configuration-space distribution at time n is obtained by integrating the path probability over all possible histories.For continuous-time Markov processes, this is the distribution calculated from Fokker–Planck solutions.

D. Resampling a distribution of trajectories

The paper recasts weighted-ensemble simulation as resampling a high-dimensional distribution of trajectories while preserving their correct probabilities. Because resampling preserves the trajectory distribution at the resampling time, subsequent evolution and configurational distributions remain correct.

Trajectory probabilities form an ordinary, high-dimensional distribution that can be resampled using weighted deletions and duplications of entire trajectories.The remaining trajectories retain correct weights, and the procedure mirrors resampling for equilibrium distributions.
Resampling at time step n preserves the trajectory distribution Ppath(x0, ...xn), so trajectories evolving afterward retain the correct distribution.The future dynamics are equivalent to propagating the original dynamics from step n to step n+m.
WE performs occasional resampling among trajectories at the same time, while ordinary brute-force dynamics operate between resampling events.Replication divides a trajectory’s weight among identical-history copies; combination transfers the summed weight to one trajectory according to relative weights.
The two WE resampling operations preserve the correct trajectory probability distribution at the resampling time and at all future times.The correct configurational distribution follows from the preserved trajectory distribution.

F. Resampling in WE simulation can be achieved with arbitrary, dynamically changing

Weighted-ensemble resampling remains valid when bins are arbitrary and change during a simulation, because binning only guides statistically correct resampling. Numerical examples confirm this for colored-noise dynamics.

F. Resampling in WE simulation can be achieved with arbitrary, dynamically changing: In its simplest form, WE divides configuration space into fixed bins and resamples to equalize the number of trajectories in visited bins.The paper then argues that this fixed-binning description is not a requirement for correctness.
F. Resampling in WE simulation can be achieved with arbitrary, dynamically changing: The authors argue that resampling can be performed correctly in many ways and that any correct procedure preserves the stochastic dynamics.This generality allows WE simulations to use bin choices that change during the simulation.
F. Resampling in WE simulation can be achieved with arbitrary, dynamically changing: Bin choices may be adjusted during a simulation, and changing the binning produces different but statistically correct resamplings.The bins guide resampling rather than alter the underlying stochastic dynamics.
F. Resampling in WE simulation can be achieved with arbitrary, dynamically changing: For any s ≫1, white- and colored-noise results are dramatically different, and the WE method reproduces those effects in detail.

B. Myopic self-avoiding walk

The paper tests WE on a myopic self-avoiding walk whose transition probabilities depend on the complete previous history. WE reproduces brute-force transition-duration distributions and agrees on the successful-transition probability.

B. Myopic self-avoiding walk: Walkers start at (0, 0) between absorbing walls at x = −1 and x = 15, and reaching the right wall before the left defines a successful transition.
B. Myopic self-avoiding walk: The myopic self-avoiding walk chooses uniformly among unvisited nearest neighbors, or among least-visited neighbors when none are unvisited.This rule prevents the walk from becoming trapped while retaining history-dependent dynamics.
B. Myopic self-avoiding walk: WE and brute-force simulations produce transition-duration distributions that match very well.The comparison is shown in the right panel of Fig. 2.
B. Myopic self-avoiding walk: 10.865 ± 0.015% of walkers reached the right absorbing wall successfully in the WE simulation, agreeing with brute force.

C. WE method with random number of bins

The WE method can use a randomly changing number of bins during resampling. In a double-well transition experiment, fluctuating bins reproduce the static-bin result.

C. WE method with random number of bins: The WE method can use arbitrary bins that change over time, including a random number of bins selected before each resampling.The modified program randomly chooses N from a range before splitting and combination.
C. WE method with random number of bins: The modified WE simulation studies transition durations for a Brownian particle in a double-well potential.The regions x < −1 and x > 1 serve as the first and last bins, while −1 ≤x ≤1 is divided into N −2 evenly spaced bins.
C. WE method with random number of bins: Fluctuating bins yield excellent agreement with the result from static bins.The right panel of Fig. 3 shows that the modified program reproduces the static-bin result.

D. WE method with adaptive Voronoi bins

Adaptive WE bins can follow the evolving probability distribution using Voronoi reference configurations, while preserving the transition-duration result obtained with static bins. In a toy double-well system, the adaptive procedure found the target without target-state information.

Adaptive bin construction: Adaptive WE uses bins that follow the evolving probability distribution during simulation.The bins can be constructed from Voronoi diagrams based on reference configurations and adjusted during the simulation.
Adaptive bin construction: Reference configurations are selected by maximizing the minimum distance from previously chosen references.The first reference is randomly selected, then each subsequent reference maximizes Dmin(i), promoting even coverage of configurational space.
Toy-system test: The adaptive method was tested on a two-dimensional double-well system with two distinct pathways and an approximately 15kBT barrier.Initial and final states were defined as low-potential regions in the left and right wells.
Toy-system test: Dynamic Voronoi bins reproduced the transition-duration distribution obtained with static bins.Both dynamic and static WE simulations were used to estimate transition-event durations.
Target discovery: The adaptive strategy found the target spontaneously after approximately 200τ without using information about the target state.Here, τ is the interval between resampling operations.

IV. DISCUSSION

WE resampling can increase the chance of observing rare transitions by reallocating trajectories toward productive regions, but it trades away precision in sampling the initial state. This trade-off is acceptable when the goal is transition sampling rather than initial-state characterization.

Target quantity: WE can improve estimation of dynamical quantities such as transition rates and transition paths, rather than sampling the initial state.The discussion frames transition sampling as the typical objective of WE simulations.
Efficiency mechanism: WE resampling increases transition observations by replicating trajectories on the productive side of a reaction-coordinate minimum.In the example, roughly 75 trajectories occupy the productive side after resampling instead of roughly 50 without resampling.
Efficiency mechanism: Repeated resampling across bins covering the reaction coordinate produces a form of statistical ratcheting.The procedure maintains the total trajectory count through splitting and combination with appropriate reweighting.
Trade-off: The efficiency gain is accompanied by decreased precision in sampling the initial state, especially when the transition rate out of state A is low.This is the stated price of increased efficiency for dynamical quantities.

B. Improved efficiency is not guaranteed

WE does not guarantee greater efficiency: its performance depends on how resampling places trajectories. The method remains rigorous for history-dependent dynamics and permits binning rules to change during simulation.

Efficiency limitation: The method’s efficiency can be more or less than brute force depending on the particular random-walk problem.Thus, increasing the number of trajectories alone does not necessarily improve characterization of a dynamical process.
Efficiency limitation: WE can be less efficient than brute-force simulation when resampling leaves too few trajectories in the transition region.A poorly chosen resampling strategy may place more trajectories away from the reactive region.
Efficiency limitation: Optimizing WE efficiency involves practical judgment even when the resampling itself is rigorous.The discussion describes a certain amount of “art” in selecting effective resampling strategies.
Generality: WE accounts for trajectory history and therefore applies to non-Markovian dynamics.Failure to account for trajectory history would prevent an exact description of such dynamics.
Generality: The method applies to a broad class of Markovian and non-Markovian dynamics, and its bins may be changed during simulation.Numerical tests also demonstrated adaptive bin changes without requiring knowledge of the target state.