Grid-Free Monte Carlo for Time-Dependent Diffusion
Abstract
Many scientific applications require modeling how diffusive systems evolve over time, not merely their eventual steady states. While conventional steady-state analysis of partial differential equations (PDEs) on complex geometries is already hindered by costly volumetric meshing, transient analysis further requires sequential time stepping and careful step size selection. Grid-free Monte Carlo solvers such as walk on spheres (WoS) and walk on stars (WoSt) avoid this meshing bottleneck but remain largely limited to steady-state problems. We generalize WoS, for pure Dirichlet problems, and WoSt, for mixed Dirichlet--Neumann problems, to heat equations with initial conditions and time-dependent source and boundary data. We equip each random walk with a finite time budget and sample an exit time at every spatial step. If the exit time exceeds the remaining budget, the walk samples an interior point and evaluates the initial condition; otherwise, it continues with a reduced budget, accumulating source and boundary contributions. Our main technical contribution is a suite of kernel sampling and variance reduction techniques, including a low-bias, tabulation-free exit time sampler and efficient rejection samplers. Unlike grid-based transient solvers, our method directly estimates the solution at any requested time without volumetric meshing or sequential time marching. It also retains the parallel, progressive, and output-sensitive evaluation of WoS and WoSt while eliminating time step selection and temporal discretization bias entirely. Finally, we show how sharing walks enables efficient estimates at multiple target times.
Related
- Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Sampler
- Steering Diffusion Models to Rare Events with Sequential Monte Carlo
- Markov Chain Monte Carlo with Diffusion Paths
- Transfer Learning of Multiobjective Indirect Low-Thrust Trajectories Using Diffusion Models and Markov Chain Monte Carlo
- Sign-problem-free Bosonic Auxiliary Field Quantum Monte Carlo
BibTeX
@misc{zhou2026gridfree,
title = {{Grid-Free Monte Carlo for Time-Dependent Diffusion}},
author = {Zihong Zhou and Rohan Sawhney and Eugene d'Eon and Wojciech Jarosz},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12306},
eprint = {2609.12306},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12306},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Grid-Free Monte Carlo for Time-Dependent Diffusion
AU - Zihong Zhou
AU - Rohan Sawhney
AU - Eugene d'Eon
AU - Wojciech Jarosz
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12306
UR - https://arxiv.org/abs/2609.12306
AB - Many scientific applications require modeling how diffusive systems evolve over time, not merely their eventual steady states. While conventional steady-state analysis of partial differential equations (PDEs) on complex geometries is already hindered by costly volumetric meshing, transient analysis further requires sequential time stepping and careful step size selection. Grid-free Monte Carlo solvers such as walk on spheres (WoS) and walk on stars (WoSt) avoid this meshing bottleneck but remain largely limited to steady-state problems. We generalize WoS, for pure Dirichlet problems, and WoSt, for mixed Dirichlet--Neumann problems, to heat equations with initial conditions and time-dependent source and boundary data. We equip each random walk with a finite time budget and sample an exit time at every spatial step. If the exit time exceeds the remaining budget, the walk samples an interior point and evaluates the initial condition; otherwise, it continues with a reduced budget, accumulating source and boundary contributions. Our main technical contribution is a suite of kernel sampling and variance reduction techniques, including a low-bias, tabulation-free exit time sampler and efficient rejection samplers. Unlike grid-based transient solvers, our method directly estimates the solution at any requested time without volumetric meshing or sequential time marching. It also retains the parallel, progressive, and output-sensitive evaluation of WoS and WoSt while eliminating time step selection and temporal discretization bias entirely. Finally, we show how sharing walks enables efficient estimates at multiple target times.
ER -