Augmenting Automatic Differentiation for a Single-Server Queue via the Leibniz Integral Rule

Michael C. Fu

arxiv: 2604.02900 · v1 · submitted 2026-04-03 · 📡 eess.SY · cs.SY· math.PR

Augmenting Automatic Differentiation for a Single-Server Queue via the Leibniz Integral Rule

Michael C. Fu This is my paper

Pith reviewed 2026-05-13 19:48 UTC · model grok-4.3

classification 📡 eess.SY cs.SYmath.PR

keywords Leibniz integral ruleLindley equationsingle-server queuehigher-order derivativessample-path estimationautomatic differentiationqueueing timerecursive estimators

0 comments

The pith

Recursive estimators from the Lindley equation and Leibniz rule compute higher-order derivatives of mean waiting time from a single sample path in a first-come first-served single-server queue.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives new recursive estimators for higher-order derivatives of mean queueing time by applying the Leibniz integral rule directly to the Lindley recursion. These estimators operate on one sample path of interarrival and service times without requiring multiple replications or full distributional information. The approach augments existing automatic differentiation techniques for performance measures in queueing systems. A reader would care because it provides an efficient way to obtain sensitivity information for system design and optimization from observed data alone.

Core claim

Applying the Leibniz integral rule to the Lindley equation W_{n+1} = max(0, W_n + S_n - A_{n+1}) produces recursive estimators for the derivatives of the expected waiting time that can be computed along a single realization of the arrival and service processes.

What carries the argument

The recursive application of the Leibniz integral rule to the Lindley recursion, which updates both the state and its derivative estimators simultaneously from each successive observation.

If this is right

Higher-order derivative estimates become available recursively after each customer departs, using only the observed interarrival and service times.
The estimators augment automatic differentiation by supplying higher-order information that standard pathwise methods may not directly provide.
The method extends to any performance measure that can be expressed as an expectation over the same recursive state process.
Illustrative examples confirm that the recursion produces usable numerical values for the derivatives.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same Leibniz augmentation could be applied to other recursive state equations that arise in tandem queues or fork-join systems.
If the estimators remain consistent, they could support gradient-based optimization of queue parameters directly from streaming data.
The approach suggests a general template for converting any integral-based performance functional into a recursive derivative estimator when the underlying recursion is max-plus linear.

Load-bearing premise

The Leibniz integral rule applies directly to the recursive Lindley equation to yield unbiased or consistent higher-order derivative estimators without extra regularity conditions or bias corrections.

What would settle it

Run the estimators on an M/M/1 queue where closed-form expressions for the first three derivatives of mean waiting time are known and check whether the sample-path estimates converge to those values as the path length grows.

read the original abstract

New recursive estimators for computing higher-order derivatives of mean queueing time from a single sample path of a first-come, first-served single-server queue are presented, derived using the well-known Lindley equation and applying the Leibniz integral rule of differential calculus. Illustrative examples are provided.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Recursive higher-order derivative estimators for single-server queue waiting times via Leibniz on Lindley, but non-smooth max needs explicit regularity conditions.

read the letter

The paper gives recursive estimators for second- and higher-order derivatives of mean waiting time in a FCFS single-server queue. It starts from the Lindley recursion and applies the Leibniz integral rule repeatedly to produce single-path formulas. The illustrative examples are straightforward and show how the recursion unfolds in simple cases. That is the concrete contribution: a direct way to get higher-order sensitivities without multiple replications or finite differences. The approach stays within classical tools, which keeps it accessible for people already using sample-path methods in queues. The main soft spot is the max operator. Its non-differentiability at zero means the first derivative introduces an indicator and higher derivatives bring derivatives of that indicator. Without stated conditions ensuring the probability of hitting exactly zero is zero, or without bias corrections or smoothing, the interchange of derivative and expectation may not be valid. The abstract is silent on this, so the body needs to supply the justification or numerical checks that the estimators remain unbiased. This is for researchers in stochastic simulation and optimization who already work with Lindley recursions and want higher-order information for design or control. A reader comfortable with IPA-style estimators will see the value quickly. I would send it to referees because the core derivation is short and the target setting is standard; the math and examples can be checked directly even if revisions are needed on the regularity side.

Referee Report

2 major / 2 minor

Summary. The manuscript presents new recursive estimators for higher-order derivatives of mean queueing time (waiting time) in a single-server FCFS queue. These estimators are derived from the standard Lindley recursion by applying the Leibniz integral rule to enable differentiation under the recursion, and the approach is illustrated with examples.

Significance. If the central derivation holds with appropriate regularity conditions, the work would provide a sample-path method for computing gradient and higher-order sensitivity information in queueing systems without requiring multiple independent replications or finite-difference approximations. This could strengthen perturbation analysis techniques and support gradient-based optimization in stochastic systems.

major comments (2)

[Derivation (Lindley recursion and Leibniz application)] The derivation (beginning from the Lindley equation W_{n+1} = max(0, W_n + X_n)) applies the Leibniz integral rule without stating or verifying the regularity condition that P(W_n + X_n = 0) = 0 almost surely. Because the max operator is non-differentiable at the origin, the first derivative involves an indicator 1_{W_n + X_n > 0} and higher-order derivatives involve derivatives of that indicator; without this condition or an explicit smoothing argument, the resulting recursive estimators may be biased or inconsistent.
[Illustrative examples] No error analysis, bias bounds, or consistency proof is supplied for the higher-order estimators. The abstract and illustrative examples therefore leave open whether the estimators remain unbiased after the non-smoothness is handled.

minor comments (2)

[Notation] Notation for the recursive estimators should be introduced with explicit indexing (e.g., D^{(k)} W_n) to distinguish sample-path quantities from their expectations.
[Introduction] The paper should cite standard references on infinitesimal perturbation analysis and smoothed perturbation analysis for comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the insightful comments on the derivation and the need for supporting analysis. We address each point below and will incorporate revisions to strengthen the manuscript.

read point-by-point responses

Referee: The derivation (beginning from the Lindley equation W_{n+1} = max(0, W_n + X_n)) applies the Leibniz integral rule without stating or verifying the regularity condition that P(W_n + X_n = 0) = 0 almost surely. Because the max operator is non-differentiable at the origin, the first derivative involves an indicator 1_{W_n + X_n > 0} and higher-order derivatives involve derivatives of that indicator; without this condition or an explicit smoothing argument, the resulting recursive estimators may be biased or inconsistent.

Authors: We agree that the regularity condition P(W_n + X_n = 0) a.s. must be stated explicitly. The derivation assumes absolutely continuous interarrival and service time distributions, which ensures the probability is zero and the indicator is differentiable almost surely. We will add an explicit statement of this assumption together with a short justification in the revised derivation section, confirming that no additional smoothing is required. revision: yes
Referee: No error analysis, bias bounds, or consistency proof is supplied for the higher-order estimators. The abstract and illustrative examples therefore leave open whether the estimators remain unbiased after the non-smoothness is handled.

Authors: The present version emphasizes the recursive form and illustrative examples. We acknowledge the lack of formal bias or consistency analysis. In the revision we will insert a dedicated section that sketches the unbiasedness argument under the stated regularity conditions, drawing on standard sample-path derivative results for Lindley recursions, and we will note that consistency follows from ergodicity of the queueing process. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation applies classical Leibniz rule to standard Lindley equation

full rationale

The paper derives recursive higher-order derivative estimators directly from the standard Lindley recursion by applying the classical Leibniz integral rule of differential calculus. This constitutes a direct, first-principles application of an established external mathematical tool to a well-known queueing equation, with no reduction of the claimed estimators to fitted parameters, self-definitions, or load-bearing self-citations. The central claim remains independent of its own inputs and is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard Lindley recursion for waiting times and the applicability of the Leibniz integral rule to it; no free parameters or new entities are introduced in the abstract.

axioms (2)

domain assumption Lindley equation holds for waiting times in FCFS single-server queue
Basis for the recursive derivation of derivatives.
domain assumption Leibniz integral rule applies to the queueing recursion
Used to obtain higher-order derivative estimators.

pith-pipeline@v0.9.0 · 5330 in / 1198 out tokens · 33532 ms · 2026-05-13T19:48:51.723328+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

Aleksandrov, V. M., V. I. Sysoyev, and V. V. Shemeneva (1968). Stochastic optimization.Engineering Cybernetics 5, 11–16. Asmussen, S. and P. W. Glynn (2007).Stochastic Simulation: Algorithms and Analysis. Springer. Cassandras, C. G. and S. Lafortune (2021).Introduction to Discrete Event Systems(3rd ed.). Springer Nature. Fu, M. C. (1989). On the consisten...

work page 1968
[2]

Pflug, G. C. (1996).Optimization of Stochastic Models: The Interface Between Simulation and Optimization. Kluwer Academic. Puchhammer, F. and P. L’Ecuyer (2022). Likelihood ratio density estimation for simulation models. In2022 Winter Simulation Conference, pp. 109–120. IEEE. Reiman, M. and A. Weiss (1989). Sensitivity analysis for simulations via likeli-...

work page arXiv 1996

[1] [1]

Aleksandrov, V. M., V. I. Sysoyev, and V. V. Shemeneva (1968). Stochastic optimization.Engineering Cybernetics 5, 11–16. Asmussen, S. and P. W. Glynn (2007).Stochastic Simulation: Algorithms and Analysis. Springer. Cassandras, C. G. and S. Lafortune (2021).Introduction to Discrete Event Systems(3rd ed.). Springer Nature. Fu, M. C. (1989). On the consisten...

work page 1968

[2] [2]

Pflug, G. C. (1996).Optimization of Stochastic Models: The Interface Between Simulation and Optimization. Kluwer Academic. Puchhammer, F. and P. L’Ecuyer (2022). Likelihood ratio density estimation for simulation models. In2022 Winter Simulation Conference, pp. 109–120. IEEE. Reiman, M. and A. Weiss (1989). Sensitivity analysis for simulations via likeli-...

work page arXiv 1996