Walk in Envelopes: Efficient Branching Walk-on-Spheres via Certified Solution Bounds

Overview & Synopsis

Branching Walk-on-Spheres (WoS) solves semilinear PDEs without meshes, but its computational cost grows sharply near critical branching rates. We introduce Walk in Envelopes (WiE), which uses certified solution bounds to transform branching diffusion rather than prune existing trees. The transformation suppresses reproduction, introduces controlled termination, and preserves unbiasedness with an envelope-dependent variance bound. We realize the transformed process through exact rejection sampling using standard screened WoS kernels, supported by certified spline envelopes and adaptive sampling, and further prove that suitable harmonic envelopes yield bounded expected reproduction counts even as conventional BBM diverges.