PaperlayerView exact revision on arXiv

Source-linked AI summary

Sign-Switched Antithetic Coupling for Signed Gradient-Particle Methods

Stephen Abkin, Prabir Daripa

arXiv:2610.01120v1math.NAcs.NA

TL;DR

Signed gradient-particle simulations can be costly to average accurately because independent runs reduce sampling error slowly. This paper couples runs by particle rank and mass sign, preserving each run’s law; in Burgers tests, sign-switched pairing met the error target with fewer simulations than independent or reflected sampling.

  • Problem

    Independent simulations reduce sampling error slowly, motivating methods that achieve a given accuracy with fewer runs.

    Source: §1 · p. 2

  • Method

    Sign-switched pairing matches particles by spatial rank and assigns opposite or equal diffusion increments according to their mass signs, while preserving each run’s probability law.

    Source: §1 · pp. 2–3, §5 · p. 31

  • Results

    4 simulations met the Burgers error target, compared with 65 for independent sampling and 34 for reflected pairing.

    Source: §5 · p. 31

  • Takeaways & Limitations

    For one-dimensional convection–diffusion equations, sign-switched pairing is an inexpensive way to improve repeated field estimates when opposite-sign particles are interleaved or meet.

    Source: §5 · p. 32

    For nonlinear fluxes, the paper leaves variance analysis over all stages and higher-dimensional spatial matching for future work.

    Source: §5 · pp. 31–32

Abstract

from arXiv · show

Gradient random-walk methods represent the spatial derivative of a solution by signed particles and recover the solution by summing their masses. We reduce the sampling error of such simulations for one-dimensional convection-diffusion equations by running them in pairs with particles matched in order of position. Reflected pairing, the standard antithetic choice, gives matched particles opposite displacements. In sign-switched pairing, matched particles of equal sign receive opposite displacements and those of opposite sign the same displacement. Each simulation keeps the probability distribution of the solver, so the pair average has the expectation and bias of one simulation. For a fixed matching, we prove that sign-switched pairing minimizes the variance contribution of each matched pair at the last diffusion step. We also derive an exact formula for the variance it removes relative to reflected pairing. For the heat equation both results extend to every step, and we measure the accumulated variance reduction numerically. In Burgers tests, with sample sizes chosen from pilot runs and checked on fresh runs, sign-switched pairing meets a mean-squared-error target with 4 simulations, compared with 65 for independent sampling and 34 for reflected pairing. Against within-sign pairing, which matches only particles of equal sign, it has about 26% lower variance with 8192 particles. With 2048 particles it meets a second target in about 40% less time. The gain persists for further profiles, later times, other viscosities, and a cubic flux, supporting sign-switched pairing as an inexpensive way to improve repeated field estimates where particles of opposite sign meet.

1 Introduction

The paper reduces sampling error in signed gradient-particle simulations by coupling two runs while preserving each run’s probability law. Its sign-based rule yields lower variance and fewer simulations for the reported Burgers error target.

1 Introduction

  • Gradient random-walk methods represent the solution derivative with weighted particles and reconstruct the field by summing their signed masses.The paper studies one-dimensional scalar convection–diffusion equations with fixed particle masses, including heat, Burgers, and cubic-flux test problems.Source: §1 · pp. 2, 4
  • Reflected pairing’s opposite displacements can cancel errors for equal-sign partners but add errors for opposite-sign partners.Opposite-sign partners can arise when neighboring particles exchange order in one simulation but not the other.Source: §1 · pp. 2–3
  • Sign-switched pairing preserves each simulation’s probability law, so the pair average has the expectation and numerical bias of one ordinary run.It retains spatial-rank matching and gives equal-sign partners opposite increments and opposite-sign partners the same increment.Source: §1 · p. 3
  • The coupling is distinct from methods that organize random inputs within one simulation: it averages two coupled runs, each distributed as an ordinary finite-particle run.When all masses have one sign, as for monotone data, sign-switched pairing coincides with reflected pairing.Source: §1 · pp. 3–4
  • 4 simulations met the Burgers error target, compared with 65 for independent sampling and 34 for reflected pairing.Against within-sign pairing, the method also had about 26% lower integrated variance with 8192 particles and met a second target in about 40% less execution time.Source: §1 · p. 4
  • At the final diffusion stage, the sign rule minimizes each matched pair’s variance contribution and gives an exact gain formula relative to reflected pairing.For the heat equation, the minimization and gain formula extend to every stage.Source: §1 · p. 4

2 Signed Gradient Particles for Convection–Diffusion Equations

The solver evolves signed particles representing the spatial derivative and reconstructs the field as a cumulative sum of their masses. It alternates transport and diffusion, then estimates the field by averaging independent simulations or coupled pairs and evaluates error through squared bias and integrated variance.

2 Signed Gradient Particles for Convection–Diffusion Equations

  • The solver combines signed cumulative reconstruction, transport–diffusion operator splitting, and deterministic initialization at midpoint quantiles.The explicit update separates the solver’s numerical bias, which coupling leaves unchanged, from sampling error.Source: §2 · p. 4

2.1 From the Field to its Gradient

  • The field is reconstructed as a step function with a jump equal to each particle’s signed mass, and a rightward move changes the field according to that mass’s sign.The method approximates the spatial derivative with point masses that move at the flux-dependent velocity and diffuse.Source: §2.1 · pp. 5–6

2.2 One Step of a Simulation

  • Each time step transports particles, sorts them by position, and applies independent Gaussian displacements for diffusion.The transport velocity uses the cumulative field; for Burgers’ equation it is that value, and for the cubic flux it is its square.Source: §2.2 · pp. 6–7

2.3 Estimators and Error

  • Integrated MSE separates into squared bias and variance, and averaging more realizations reduces the variance contribution while leaving bias unchanged.Integrated variance sums pointwise variances over the evaluation window; execution time is used to compare computational work.Source: §2.3 · p. 8

3 Coupling Two Simulations by Mass Sign

For a fixed particle matching, sign-switched coupling minimizes each matched pair’s field-variance contribution while preserving the original solver’s law and the pair average’s bias. Relative to reflected pairing, it removes terminal variance for opposite-sign partners, with the comparison extending to every stage for the heat equation.

3.1 What the Mass Signs Do to an Antithetic Pair

  • For a fixed matching, sign-switched pairing minimizes each matched pair’s conditional field-variance contribution at every x: reflect equal-sign masses and synchronize opposite-sign masses.The coupling acts through the covariance term; reflection is optimal when the mass product is positive, while synchronization is optimal when it is negative.Source: §3.1 · p. 10

3.2 The Coupling and Two Alternatives

  • Sign-switched pairing rank-matches particles, reflecting partners with equal-sign masses and synchronizing partners with opposite signs; reflected pairing always reflects, while within-sign pairing matches only equal signs.The sign rule adds one comparison per matched pair, or O(N) operations per stage, to the solver’s existing O(N log N) sort.Source: §3.2 · pp. 11–12

3.3 Each Simulation Keeps its Law

  • Under any admissible coupling, each simulation’s full trajectory has the law of an uncoupled simulation, and the pair average has the same bias as independent sampling.Only the joint law of the two trajectories changes, allowing the couplings to be compared through variance while sharing the same bias.Source: §3.3 · pp. 13–14
  • Reflected and sign-switched trajectories coincide until a matched pair has opposite-sign masses; if all masses share one sign, the two algorithms coincide throughout.Switching therefore takes effect only after opposite-sign particles meet or become interleaved in rank order.Source: §3.4 · pp. 14–15
  • The exact final-stage variance reduction is positive when any matched pair has opposite signs, and is greatest for nearby opposite-sign partners.Only opposite-sign pairs contribute to the reduction; its distance-dependent gap decreases as partner separation grows.Source: §3.4 · pp. 15–16
  • About 4% of the Burgers variance reduction came from switching only at the last stage; for a heat test, that stage alone gave 1.44%.Both comparisons are against switching at every stage, showing that most reduction accumulates over earlier stages.Source: §3.4 · pp. 16–17
  • Opposite increments negatively correlate partner contributions for equal-sign particles, while equal increments do so for opposite-sign particles.This monotone structure persists across stages for the heat equation, but nonlinear transport can reverse the later-field effect of a displacement.Source: §3.4 · p. 16
  • For the heat equation, sign-switched pairing minimizes every matched pair’s variance contribution at every stage, simultaneously for all x.The stagewise gain is positive whenever the entering state has opposite-sign partners.Source: §3.4 · pp. 16–17
  • Rank matching minimizes total absolute distance between partners among all bijections, whereas within-sign matching restricts the available partners.The result follows by removing crossed pairs in the ordered configurations.Source: §3.4 · p. 17
  • Variance reduction relative to independent increments decreases with partner separation for both reflected equal-sign pairs and synchronized opposite-sign pairs.This distance dependence explains why keeping spatial neighbors paired can outperform within-sign matching; terminal variance also depends on how paired states evolve.Source: §3.4 · p. 18

4 Numerical Results

The numerical tests examine how sign-switched pairing affects variance and observable error, and how its benefits depend on signed-particle structure and evaluation choices. They also consider computational costs, including when control preparation or field evaluation can outweigh variance reduction.

4.1 Test Configuration

  • A single sign-switched pair at N = 8192 followed the Burgers reference solution closely at the plotted scale.The test configuration used a two-pulse initial profile and also displayed the three initial profiles used in Test 4.Source: Figure 2 · p. 19, §4.1 · p. 19

4.2 Test 1: Variance Reduction Beyond Within-Sign Pairing

  • At N = 8192, sign-switched pairing’s integrated variance ratio was 0.0530 versus the average of two independent simulations, and 0.739 versus within-sign pairing.That is a 26% reduction versus within-sign pairing; switching errors largely cancel, with the reduction concentrated in steep-gradient regions, and its variance-times-cost ratio versus within-sign pairing was 0.697.Source: Table 1 · p. 20, §4.2 · pp. 20, 22

4.3 Test 2: Execution Time at a Target Accuracy

  • At target 7 × 10−6, sign-switched pairing met the MSE target with 4 simulations, versus 65 independent, 34 reflected, and 46 RQMC simulations.At target 2.5×10−5 and N = 2048, it also met the target with 2 pairs versus 3 for within-sign pairing, reducing measured execution time by about 40%; it was the fastest evaluated plan in both experiments.Source: Table 2 · p. 23, §4.3 · pp. 23–24

4.4 Test 3: Dependence on Signed Particle Structure

  • For alternating signs, switching reduced variance to about 5%–6% of reflected pairing; merging blocks roughly halved it, while separated blocks and one-sign cases were consistent with 1.Burgers results closely followed heat results, supporting the benefit of nearby opposite-sign partners with and without transport.Source: Table 3 · p. 25, §4.4 · p. 26

4.5 Test 4: Initial Profile, Observation Time, Viscosity, and Flux

  • Switching reduced variance across profiles and later times, reaching a 0.595 ratio versus within-sign pairing for the oscillatory profile at T = 2.Against reflected pairing, the variance ratio fell from 0.343 at ν = 0.02 to 0.0914 at ν = 0.5; against within-sign pairing, the reduction was 15%–31% for ν ≥ 0.05, while at ν = 0.02 the ratio was 0.915 [0.792, 1.04]. For cubic flux, the ratio versus within-sign pairing was 0.769, compared with 0.792 for Burgers; the gain is smallest when transport dominates diffusion.Source: §4.5 · pp. 26–28

4.6 Test 5: Conditional Evaluation and Control Variates

  • Test 5 examines conditional evaluation of the last diffusion stage and control variates using a second field with known mean.Conditional evaluation replaces terminal indicators with conditional expectations given pre-stage particle positions; the control variates use heat and velocity fields constructed from diffusion increments.Source: §4.6 · p. 28
  • For Burgers’ equation, switching and within-sign pairing each remove about four fifths of reflected-pairing variance, while velocity control removes about a third; after switching, either control changes variance by at most about 3.5%.Control preparation raises variance-times-cost, making switching without a control more efficient.Source: §4.6 · pp. 28–29, Figure 6 · p. 29
  • Conditional evaluation roughly halves variance again for both fluxes when combined with switching, and the combination has the lowest variance-times-cost.Its variance-times-cost ratio relative to switching alone rises from 0.613 at 201 evaluation points to 1.49 at 1601 points; conditional evaluation is advantageous at relatively few points, while switching alone is preferable at many.Source: §4.6 · p. 29, Figure 6 · p. 29

4.7 Test 6: Nonlinear Observables

  • For nonlinear observables, the mean of Q has the same expectation and bias for all couplings, whereas Q of the mean can have coupling-dependent bias.The test compares peak gradient and the location of the first downward crossing of level u = 0.25 to the right of the maximum.Source: §4.7 · p. 30
  • For the peak gradient, Q of the mean under switching has lower MSE than either alternative, with a ratio of 0.602 against within-sign pairing; switching also lowers level-crossing MSE relative to reflection.For level crossing, comparisons with within-sign pairing are consistent with 1 at this sample size.Source: §4.7 · p. 30, Table 4 · p. 30
  • For the peak gradient, Q of the mean has less than half the MSE of the mean of Q under every coupling, and about a fifth under switching.For the mean of Q under switching, 87% of MSE is squared bias, which is the same for every coupling; averaging fields before computing the peak reduces fluctuations and avoids retaining the upward bias of averaging individual maxima.Source: §4.7 · pp. 30–31

5 Conclusions

Sign-switched pairing reduces field-estimation variance while preserving each simulation’s law, expectation, and bias. The analysis and tests support it as an inexpensive option when opposite-sign particles meet, while identifying broader variance analyses as future work.

5 Conclusions

  • The coupling changes only variance, preserving the expectation and bias of one simulation.Each simulation retains the probability law of the underlying numerical method.Source: §5 · p. 31
  • At the final diffusion stage, sign-switched pairing minimizes each matched pair’s variance contribution; for the heat equation, this holds at every stage.The exact improvement over reflected pairing depends on the mass product, separation, and diffusion scale for opposite-sign pairs.Source: §5 · p. 31
  • 4 simulations meet the common error target, compared with 65 for independent sampling and 34 for reflected pairing.Against within-sign pairing, variance is about 26% lower in the two-pulse Burgers test with 8192 particles; gains also persist across other profiles, later times, viscosities from 0.05 to 0.5, and a cubic flux.Source: §5 · p. 31
  • The gain is largest when opposite-sign particles are interleaved or meet; for one-sign data, the rule coincides with reflected pairing.Coupling is most effective while sampling error dominates; once squared bias dominates, accuracy improves with more particles or a smaller time step.Source: §5 · p. 31
  • Further variance analysis for nonlinear fluxes should account for particle reordering and the relative scales of transport and diffusion.The authors also propose coupling velocity sampling in relaxation schemes and extending matching and reconstruction to higher dimensions.Source: §5 · pp. 31–32
  • For one-dimensional convection–diffusion equations, the method is presented as an inexpensive way to improve repeated field estimates when opposite-sign particles meet.The authors identify higher-dimensional spatial matching and field reconstruction as an extension, using minimum-distance assignment as the analogue of rank matching.Source: §5 · p. 32

Data and code availability

The solver, simulation data, and reproduction scripts are archived as version 1.0 at Zenodo.

Data and code availability

  • The solver, simulation data, and scripts for reproducing the tables and figures are archived as version 1.0 at Zenodo.The README gives reproduction commands and identifies the source data.Source: Data and code availability · p. 32

A Proofs

The appendix proves the stated coupling and distance results, including preservation of each simulation’s uncoupled law. It also checks the variance formulas numerically and measures how much of the accumulated reduction comes from late stages.

A Proofs

  • Each coupled simulation retains the uncoupled solver’s law because its signed, permuted Gaussian increments remain independent standard Gaussian vectors.The argument requires a predictable rule, a bijective permutation, and multipliers of ±1; the particular sign rule also requires nonzero masses.Source: §A.1 · p. 33
  • The proof of the distance identity uses an elementary kernel identity and exchanges integration and expectation under absolute integrability.The kernel is supported between its argument and zero; the proof invokes Fubini’s theorem and the identity in Lemma A.1.Source: §A.2 · pp. 33–34
  • At the final stage, conditional variance decomposes over matched ranks, and only opposite-sign pairs contribute a difference between reflection and synchronization.For such pairs, the difference is given by (3.8) and is strictly positive for positive diffusion scale; equal-sign pairs contribute nothing.Source: §A.3 · p. 34
  • For heat dynamics, the proof extends the variance comparison to every stage, with reflection and synchronization attaining the covariance bounds.The gain expression is positive and decreases with pair separation when the separation is positive.Source: §A.5 · pp. 35–36
  • The final-stage identity agreed with paired Monte Carlo checks within nominal 95% intervals and with adaptive quadrature to ten decimal places.For Burgers runs, the last-stage share of the all-stage reduction was 3.75% for a single Gaussian bump and 3.71% and 1.95% for the two-pulse profile at the two tested time steps.Source: §A.6 · p. 36
  • Under heat dynamics, summed closed-form variance terms matched empirical integrated variance for both switching and reflection.Along sign-switched runs, the last stage contributed 2.08% of the summed gains and the last ten stages 14.8%; switching only at the last stage gave 1.44% of the all-stage reduction.Source: §A.6 · p. 36

B Particle Ordering and the Field Response

Particle reordering can reverse how the terminal field responds to an initial particle displacement. The appendix also describes how order reversals can initiate different later coupling choices for initially separated sign regions.

B.1 A Two-Particle Monotonicity Counterexample

  • In a two-step Burgers example, increasing the initial position of a positive mass first lowers and then raises the terminal field.With Gaussian displacements restored, the reversal still holds in expectation: the probability that any displacement exceeds 10^-4 is less than exp(-5003).Source: §B.1 · pp. 36–37

B.2 Initially Separated Sign Regions

  • For initially separated opposite-sign neighbors, reflection can reverse the order in exactly one simulation, allowing later diffusion choices to differ.In 200 realizations, the couplings diverged in 58/200 under heat dynamics and 59/200 under Burgers; median first divergence was stage 187 of 200 among diverging runs.Source: §B.2 · p. 37

C Test Problems, Initialization and Reference Solutions

The appendix specifies particle initialization and test-profile configurations, then documents the numerical references used to assess field error.

Initialization

  • Smooth equal-far-field profiles place N/2 particles of each sign at midpoint quantiles, with masses ±TV(u0)/N, making initial states identical across methods.For the main two-pulse experiments, cumulative integrals are computed on [−12, 12] and inverted by linear interpolation.Source: C Test Problems, Initialization and… · p. 38
  • Test 4 initializes particles by rectangle-summing positive and negative profile parts on [−6, 6], then inverts the sums by linear interpolation.Masses are assigned from the two numerical integrals; the oscillatory profile has total signed mass about −2.34 × 10−7.Source: C Test Problems, Initialization and… · p. 38

Profiles

  • The bump, two-pulse, and oscillatory profiles have 2, 3, and 13 sign regions; four configurations test alternating, separated, merging, and one-sign particle layouts.The separated and merging configurations use N/2 particles of each sign; the one-sign configuration assigns mass −2/N to every particle.Source: C Test Problems, Initialization and… · p. 38

References

  • Burgers references include a Cole–Hopf solution, while quadratic and cubic fluxes use Fourier pseudospectral references; refining the cubic reference changes it by 1.6 × 10−13 in maximum norm.The Cole–Hopf formula agrees with the spectral solution to 5.57 × 10−14 in maximum norm at reconstruction points.Source: C Test Problems, Initialization and… · p. 38

D Additional Estimator Constructions

The appendix describes conditional Monte Carlo, known-mean controls, and randomized quasi-Monte Carlo as additional estimator constructions.

D.1 Conditional Evaluation and Known-Mean Controls

  • Conditional Monte Carlo averages over selected random inputs while holding others fixed, then averages the resulting terminal-field expression across both simulations.The conditional expectation replaces an estimator, and the two simulation expressions are averaged.Source: §D.1 · p. 39
  • Heat and velocity controls follow particles by identity, with velocity fixed from the initial state; each particle’s accumulated displacement has distribution N(0, 2νT).The displacement distribution follows from summing K independent N(0, σ2) increments.Source: §D.1 · p. 39
  • A single field-wide control coefficient is estimated from 16 pilot pairs and held fixed during evaluation, subtracting a multiple of a correlated quantity with known mean.The coefficient adapts the pointwise optimal coefficient, and preparation cost is allocated across 64 realizations.Source: §D.1 · p. 39

D.2 Randomized Quasi-Monte Carlo Implementation

  • Each randomized quasi-Monte Carlo realization scrambles a two-dimensional Sobol’ sequence and uses successive blocks of N points across time steps.Its changed dependence between particles is why total error is evaluated with a separate bias estimate.Source: §D.2 · pp. 39–40

E Uncertainty Methodology and its Calibration

The appendix reports variance and observable comparisons alongside the allocation, timing, and interval procedures used to assess uncertainty and calibrate the estimates.

Experimental Allocation and Timing

  • Experiment II selected 1.96, 2.83, and 17.8 pairs for sign-switched, within-sign, and reflected pairing; at N = 2048, sign-switched cost was 0.908 times within-sign cost.The selected plans were checked on fresh runs, and the measured time ratio was 0.599.Source: §E.2 · p. 40

Variance comparisons

  • Variance ratios of sign-switched to reflected pairing were 0.152 at N = 1600, h = 0.0025; 0.134 at N = 6400, h = 0.005; and 0.0986 at N = 6400, h = 0.0025.The corresponding crossover R⋆ values were 35.3, 4.5, and 10.3, respectively; at N = 6400, halving h lowered common squared bias from 1.71 × 10−6 to 5.66 × 10−7.Source: §E.2 · p. 41

Pointwise and Nonlinear Observables

  • Pointwise sign-switched/reflected variance ratios were 0.143 at x = −0.7 and 0.093 at x = 0.1; over |x| ≤ 1, the sign-switched/within-sign variance ratio was 0.66.Over the nearly flat flanks |x| > 1, the integrated ratio was 1.01.Source: §E.3 · p. 41
  • For peak gradient, mean Q exceeded reference 1.29 by 0.10–0.11 under every coupling; MSE ratio (Q of mean / mean of Q) was 0.43, 0.38, and 0.21 for reflected, within-sign, and sign-switched pairing.Subtracting the sampling term from the plug-in squared bias lowers each reported bias share by at most 0.02.Source: §E.3 · p. 41

Intervals for the Evaluation of the Plans

  • The joint upper error bound uses a Bonferroni-adjusted one-sided t interval with nominal confidence of at least 97.5%, assuming the t approximation; individual estimates can exceed the target.The bound assesses mean error over repeated estimates.Source: §E.4 · p. 41

Calibration of the Variance-Ratio Intervals

  • Synthetic checks gave nominal-interval coverage of 0.949–0.982 for F intervals and 0.921–0.950 for percentile bootstrap intervals, which the authors treat as approximate at these sample sizes.The tests used 1500 synthetic datasets with n = 48 per sample and imposed variance ratios of 0.15 and 0.75.Source: §E.5 · p. 42

F Tables for Tests 4 and 5

The appendix provides tables for Test 4 variance and matching comparisons, viscosity variation, and Test 5 variance-reduction comparisons across two fluxes.

Test 4

  • Table F.1 reports the integrated variance ratio of sign-switched to within-sign pairing for Burgers at N = 2048 and h = 0.005.The table uses 48 independent realizations per method and bootstrap intervals.Source: Table F.1 · p. 42
  • Table F.2 compares mean partner distances under rank and within-sign matching on the same paired states immediately before the last diffusion stage.It averages per-realization ratios from 24 independent realizations at N = 2048.Source: Table F.2 · p. 42
  • Table F.3 reports integrated variance ratios for sign-switched pairing at T = 1 across viscosities, using N = 2048 and 48 independent realizations per method.The ν = 0.1 row is an independent run of the Table F.1 setting and agrees with that entry within the intervals.Source: Table F.3 · p. 43

Test 5

  • Table F.4 compares variance-reduction methods for Burgers and cubic flux at N = 1600, with shared random draws and bootstrap resampling across methods.Its v×cost column reports variance times per-realization cost relative to reflected pairing, including allocated preparation cost.Source: Table F.4 · p. 43
Loading 2610.01120v1…