Hairer and Weare (Comm. Pure Appl. Math. 67, 2014) introduced Ticketed Diffusion Monte Carlo (TDMC), a branching-particle algorithm for Feynman–Kac-type expectations whose weight contains a discrete stochastic integral, and proved that it is unbiased and has lower estimator and workload variance than standard DMC in every regime. The paper explicitly raises one open issue and leaves three linked issues unresolved: (1) the design of the biasing potential VV — the authors suspect, without proof, that at small step size the optimal choice is the oracle potential V(k,x)=−log⁡P(y2∈B∣ykϵ=x)V(k,x)=-\log\mathbf{P}(y_2\in B\mid y_{k\epsilon}=x), and practical near-optimal choices, including low-temperature (γ→0\gamma\to0) asymptotic designs, are undeveloped; (2) the ensemble self-normalization used to stabilize the particle count in their filtering experiments introduces an MM-dependent bias whose quantitative behavior and correction are uncharacterized; (3) beyond the companion Brownian-fan analysis of a toy random walk, no rigorous finite-step-size error bounds or scaling analysis exists for TDMC on general dynamics and observation models; (4) no analysis exists of when to branch versus accumulate particle weights. The problem is to resolve these four components and thereby give TDMC a principled, rigorous design theory.

Background

Diffusion Monte Carlo (DMC) is a branching-particle Monte Carlo method, popularized in quantum chemistry for computing ground-state energies, that is built on the Feynman–Kac formula: expectations of functionals of a Markov process weighted by an exponential can represent solutions of certain linear PDEs. In discrete time, one targets ⟨f⟩t=E(f(yt)exp⁡(−∑tk≤tχ(ytk,ytk+1)))\langle f\rangle_t=\mathbf{E}\Big(f(y_t)\exp\Big(-\sum_{t_k\le t}\chi(y_{t_k},y_{t_{k+1}})\Big)\Big) for a Markov process yy, a test function ff, and a two-point weight χ\chi. A population of MM particles evolves under yy; at each step every particle is replaced by a random number of copies with mean e−χ(x,y)e^{-\chi(x,y)} (branching; in the sequential Monte Carlo (SMC) and particle-filtering literature the analogous step is called resampling), and the resulting unweighted ensemble estimates ⟨f⟩t\langle f\rangle_t unbiasedly. The general theory of such Feynman–Kac particle approximations is due to Del Moral (2004).

Hairer and Weare (2014) studied natural choices of χ\chi beyond the quantum-chemical one: for rare-event simulation, χ(x,y)=V(y)−V(x)\chi(x,y)=V(y)-V(x) (formally a stochastic integral), and for high-frequency filtering, χ\chi proportional to a squared innovation. For such weights the typical size of χ\chi per step of size ϵ\epsilon is O(ϵ)O(\sqrt{\epsilon}), so the probability that a particle dies or spawns at each step is itself O(ϵ)O(\sqrt{\epsilon}); as ϵ→0\epsilon\to0 the particle count fluctuates wildly (in the simplest random-walk example the second moment of the population at time 1 grows like ϵ−1/2\epsilon^{-1/2}) and the estimator variance explodes. Their remedy, Algorithm TDMC ("Ticketed DMC"), attaches to each particle an independent ticket θ∈(0,1)\theta\in(0,1): a particle is eliminated exactly when its path violates its ticket value, which restricts the region of state space the particle may visit, and children of a branching event inherit adjusted tickets. This mechanism is inspired by the RESTART (repetitive simulation trials after reaching thresholds) and DPR (dynamics probability redistribution) rare-event algorithms, which copy trajectories when they cross thresholds of an importance function toward the rare set and restrict where the copies may wander. Hairer and Weare prove that TDMC is unbiased (their Theorem 4.1) and that both the estimator variance and the variance of the workload (the total number of particle time-steps) never exceed those of standard DMC (Theorem 4.3 and the subsequent comparison) — lower variance per unit of expected computational work in every regime. Numerically, they compute the escape probability for a seven-particle, two-dimensional Lennard-Jones cluster (particles interacting through a pair potential ∼r−12−r−6\sim r^{-12}-r^{-6}, evolving by overdamped Langevin dynamics — gradient drift plus noise of strength set by a temperature parameter γ\gamma — with time step ϵ=10−4\epsilon=10^{-4}) and reconstruct a noisy Lorenz-63 signal (the famous chaotic ODE system, here driven by noise) from high-frequency observations with only M=10M=10 particles.

The biasing potential VV (equivalently, the importance function) determines where the algorithm concentrates particles: the branching step creates more copies where VV decreases. The paper's experiments use V(x)=(λ/γ)min⁡i≥2∥xi−17∑jxj∥V(x)=(\lambda/\gamma)\min_{i\ge2}\|x_i-\frac{1}{7}\sum_j x_j\| with parameters λ\lambda and γ\gamma, and the authors state this choice "is certainly far from optimal". For splitting-type algorithms, Dean and Dupuis (2011) identified optimal choices of the importance function in the small-noise limit for a generalized RESTART/DPR scheme, and Vanden-Eijnden and Weare (2012) constructed small-noise rare-event estimators with vanishing relative error; adapting such results to TDMC was left open. The companion paper (Hairer and Weare, 2015, "The Brownian Fan") rigorously analyzes TDMC only in the small-ϵ\epsilon limit of the simplest toy model — a random walk biased by a linear potential — where the rescaled branching genealogy converges to a newly constructed random object, the Brownian fan. A short corrigendum to the main paper appeared in 2015. The four questions below concern issues the source paper raises but leaves unresolved: the biasing-potential conjecture is stated explicitly as an open item, the population-control bias and the branching schedule are acknowledged or noted only heuristically in the text, and no rigorous finite-step-size analysis beyond the companion's toy model exists.

Problem Statement

The problem is to give the Ticketed Diffusion Monte Carlo (TDMC) algorithm of Hairer and Weare (2014) a rigorous and principled design theory — turning TDMC from a heuristically motivated algorithm into a method with analyzable accuracy, cost, and design rules — by resolving the following four issues. Central is the source's explicitly stated open question, the conjectured optimal biasing potential (component 1); the other three build on issues the source acknowledges but does not analyze (the population-control bias and the branching schedule) and on the absence of a rigorous finite-step-size analysis beyond the companion's toy model:

  1. Optimal biasing potential. Make precise, then prove or refute, the authors' suspicion that, at least when the step-size parameter is small, the optimal choice of the biasing potential VV in the rare-event setting (where χ(x,y)=V(y)−V(x)\chi(x,y)=V(y)-V(x) and the target is PxA(y2∈B)\mathbf{P}_{x^A}(y_2\in B) for the seven-particle Lennard-Jones cluster under overdamped Langevin dynamics at temperature γ\gamma) is the oracle potential V(k,x)=−log⁡P(y2∈B∣ykϵ=x),V(k,x)=-\log\mathbf{P}(y_2\in B\mid y_{k\epsilon}=x), where optimality is understood in the paper's variance-per-workload sense (estimator variance relative to expected computational work), with the optimality criterion itself formalized over a stated class of time-dependent potentials. In addition, develop practical, provably near-optimal choices of VV, including asymptotically optimal designs in the low-temperature regime γ→0\gamma\to0, and determine whether, with poorly chosen VV, the cost of achieving a fixed relative accuracy necessarily grows exponentially in γ−1\gamma^{-1}.

  2. Population-control bias. Quantitatively characterize the MM-dependent bias introduced by the ensemble self-normalization used to stabilize the particle count in the source's filtering experiments — each particle's branching weight is multiplied by MM divided by the current ensemble average of the weights, so that the expected population stays at MM (equation (3.9) in the authors' final manuscript; numbered (3.10) in some versions) — namely its order and constants in the ensemble size MM and its dependence on the time step and the observation model.

  3. Rigorous finite-step analysis. Establish rigorous results on the accuracy and stability of TDMC beyond the toy random-walk-with-linear-potential case treated via the Brownian fan: finite-ϵ\epsilon error bounds for the TDMC estimator, and conditions on χ\chi, the underlying dynamics, and the observation model under which TDMC remains stable as ϵ→0\epsilon\to0, for general classes of dynamics and observation models.

  4. Branching schedule. Analyze the tradeoff the authors note only heuristically — performing the copying/killing (branching) steps less frequently while accumulating particle weights in the intervening intervals — and characterize when to branch versus accumulate weights so as to balance estimator variance against computational overhead.

These four components are jointly posed as the target of this problem.

References

  1. Martin Hairer and Jonathan Weare, 'Improved Diffusion Monte Carlo', Communications on Pure and Applied Mathematics 67(12):1995–2021, 2014. DOI: 10.1002/cpa.21526, https://doi.org/10.1002/cpa.21526 (the authors' final manuscript is arXiv:1207.2866v2, https://arxiv.org/abs/1207.2866)
  2. Martin Hairer and Jonathan Weare, 'Corrigendum: Improved Diffusion Monte Carlo', Communications on Pure and Applied Mathematics 68(8):1285–1286, 2015. DOI: 10.1002/cpa.21587, https://doi.org/10.1002/cpa.21587
  3. Martin Hairer and Jonathan Weare, 'The Brownian Fan', Communications on Pure and Applied Mathematics 68(1):1–60, 2015. DOI: 10.1002/cpa.21544, https://doi.org/10.1002/cpa.21544 (preprint arXiv:1404.2928, https://arxiv.org/abs/1404.2928)
  4. Thomas Dean and Paul Dupuis, 'The design and analysis of a generalized RESTART/DPR algorithm for rare event simulation', Annals of Operations Research 189:63–102, 2011. DOI: 10.1007/s10479-009-0664-7, https://doi.org/10.1007/s10479-009-0664-7
  5. Eric Vanden-Eijnden and Jonathan Weare, 'Rare Event Simulation of Small Noise Diffusions', Communications on Pure and Applied Mathematics 65:1770–1803, 2012. DOI: 10.1002/cpa.21428, https://doi.org/10.1002/cpa.21428
  6. Pierre Del Moral, 'Feynman–Kac Formulae: Genealogical and Interacting Particle Systems with Applications', Springer, Probability and its Applications, 2004. DOI: 10.1007/978-1-4684-9393-1, https://doi.org/10.1007/978-1-4684-9393-1
  7. Lek-Heng Lim and Jonathan Weare, 'Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra', SIAM Review 59(3):547–587, 2017. DOI: 10.1137/15M1040827, https://doi.org/10.1137/15M1040827
  8. Aaron R. Dinner, Jonathan C. Mattingly, Jeremy O. B. Tempkin, Brian Van Koten, and Jonathan Weare, 'Trajectory Stratification of Stochastic Dynamics', SIAM Review 60(4):909–938, 2018. DOI: 10.1137/16M1104329, https://doi.org/10.1137/16M1104329
  9. David Aristoff, 'An ergodic theorem for the weighted ensemble method', Journal of Applied Probability 59(1):152–166, 2022. DOI: 10.1017/jpr.2021.38, https://doi.org/10.1017/jpr.2021.38
  10. Robert J. Webber, 'Unifying Sequential Monte Carlo with Resampling Matrices', 2019. arXiv:1903.12583, https://arxiv.org/abs/1903.12583
  11. Grégoire Ferré and Gabriel Stoltz, 'Error estimates on ergodic properties of discretized Feynman–Kac semigroups', Numerische Mathematik 143:261–313, 2019. DOI: 10.1007/s00211-019-01059-1, https://doi.org/10.1007/s00211-019-01059-1
  12. Grégoire Ferré, Mathias Rousset, and Gabriel Stoltz, 'More on the long time stability of Feynman–Kac semigroups', Stochastics and Partial Differential Equations: Analysis and Computations 9:630–673, 2021. DOI: 10.1007/s40072-020-00178-3, https://doi.org/10.1007/s40072-020-00178-3
  13. Grégoire Ferré, 'Stochastic viscosity approximations of Hamilton–Jacobi equations and variance reduction', ESAIM: Mathematical Modelling and Numerical Analysis 57:2301–2318, 2023. DOI: 10.1051/m2an/2023042, https://doi.org/10.1051/m2an/2023042
  14. Zhizhang Wu, Renaud Raquépas, Jack Xin, and Zhiwen Zhang, 'Computing Large Deviation Rate Functions of Entropy Production for Diffusion Processes by an Interacting Particle Method', SIAM Journal on Scientific Computing 47:A3330–A3355, 2025. DOI: 10.1137/24M1720172, https://doi.org/10.1137/24M1720172
  15. Bastiaan J. Braams, 'A Diffusion Monte Carlo algorithm employing depth first traversal and a stack instead of a swarm', 2026. arXiv:2606.08946, https://arxiv.org/abs/2606.08946
  16. Nicolas Chopin and Omiros Papaspiliopoulos, 'Advanced Topics and Open Problems', in 'An Introduction to Sequential Monte Carlo', Springer Series in Statistics, pp. 371–376, 2020. DOI: 10.1007/978-3-030-47845-2_19, https://doi.org/10.1007/978-3-030-47845-2_19
  17. G. Lee Warren and Robert J. Hinde, 'Population size bias in descendant-weighted diffusion quantum Monte Carlo simulations', Physical Review E 73:056706, 2006. DOI: 10.1103/PhysRevE.73.056706, https://doi.org/10.1103/PhysRevE.73.056706
  18. Massimo Boninsegni and Saverio Moroni, 'Population size bias in diffusion Monte Carlo', Physical Review E 86:056712, 2012. DOI: 10.1103/PhysRevE.86.056712, https://doi.org/10.1103/PhysRevE.86.056712
  19. Jaron T. Krogel and David M. Ceperley, 'Population Control Bias with Applications to Parallel Diffusion Monte Carlo', ACS Symposium Series, vol. 1094 (Advances in Quantum Monte Carlo), pp. 13–26, 2012. DOI: 10.1021/bk-2012-1094.ch002, https://doi.org/10.1021/bk-2012-1094.ch002
  20. Khaldoon Ghanem, Niklas Liebermann, and Ali Alavi, 'Population control bias and importance sampling in full configuration interaction quantum Monte Carlo', Physical Review B 103:155135, 2021. DOI: 10.1103/PhysRevB.103.155135, https://doi.org/10.1103/PhysRevB.103.155135
  21. Joachim Brand, Mingrui Yang, and Elke Pahl, 'Stochastic differential equation approach to understanding the population control bias in full configuration interaction quantum Monte Carlo', Physical Review B 105:235144, 2022. DOI: 10.1103/PhysRevB.105.235144, https://doi.org/10.1103/PhysRevB.105.235144
  22. Pierre Del Moral, Arnaud Doucet, and Ajay Jasra, 'On adaptive resampling strategies for sequential Monte Carlo methods', Bernoulli 18(1):252–278, 2012. DOI: 10.3150/10-BEJ335, https://doi.org/10.3150/10-BEJ335
  23. Yichao Li, Wenshuo Wang, Ke Deng, and Jun S. Liu, 'Stratification and optimal resampling for sequential Monte Carlo', Biometrika 109:181–194, 2022. DOI: 10.1093/biomet/asab004, https://doi.org/10.1093/biomet/asab004