Lorden's Inequality¶

Lorden's inequality bounds the mean excess at first crossing of any nonnegative threshold by a positive-part second moment divided by the positive drift of iid increments.

Version: v2 · 2026-10-03 · History
Domain-specific #: 13402
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Renewal Theory, Sequential Analysis → Mathematics
Aliases: Lorden Overshoot Inequality

Core Idea¶

Let independent, identically distributed increments \(Z_1,Z_2,\ldots\) form a random walk \(S_n=\sum_{i=1}^{n}Z_i\). For a threshold \(a\geq0\), stop at the first \(T(a)\) with \(S_{T(a)}>a\). The overshoot \(R_a=S_{T(a)}-a\) is the excess above the line at that first crossing. If the mean increment \(m=E[Z]\) is positive and the positive part \(Z^+=\max(Z,0)\) has finite second moment, Lorden's inequality gives \(\sup_{a\geq0}E[R_a]\leq E[(Z^+)^2]/m\). The ceiling depends on the increment law but not on the position of the threshold.^[1]^[2]

For nonnegative renewal increments \(X\), the positive part is just \(X\), so the familiar form is \(E[R_a]\leq E[X^2]/E[X]\). That is the frozen seed's statement, but it is narrower than Lorden's original positive-drift random-walk theorem: increments may also be negative. The broader form matters when a running log-likelihood score can step down as well as up.^[2]^[3]

This is an expectation bound, not an almost-sure cap on each sample path. A rare large increment can produce an overshoot larger than the right-hand side on one realization while the mean remains bounded.

Structural Signature¶

Sig role-phrases:

Iid positive-drift increments: repeated steps share a law and have \(m>0\); signed values are allowed in the full result.
First strict passage: \(T(a)\) selects the earliest index with \(S_n>a\), not an arbitrary stopping time or a hit at exactly \(a\).
Excess variable: \(R_a\) measures how far the stopped sum passes the threshold, not how likely crossing is.
Moment ceiling: \(E[(Z^+)^2]/m\) controls \(E[R_a]\) uniformly over all \(a\geq0\), provided it is finite.
Optional stopping-time translation: Wald's identity, when its conditions hold, links the overshoot to expected crossing count through \(mE[T(a)]=a+E[R_a]\).^[2]

Condensed: iid upward-drifting random walk + first boundary crossing + finite positive-part second moment → threshold-uniform mean-excess ceiling.

What It Is Not¶

Not restricted to positive increments. That is the renewal special case; Lorden's original result allows backward steps while retaining positive mean drift.^[2]
Not a bound on every realized jump. It bounds a mean, not a maximum pathwise overshoot.
Not a general inequality for dependent increments. Identical distribution and independence are part of the cited theorem.
Not a claim that a fixed second moment automatically makes the bound sharp. Particular increment laws can admit tighter estimates.^[3]
Not any quantity called overshoot. Control-system transient amplitude or convective overshoot is not this first-passage random-walk variable.

Scope of Application¶

In renewal theory, nonnegative interarrival or lifetime increments make \(S_n\) the sequence of renewal epochs. At horizon \(a\), the first renewal after it occurs at \(S_{T(a)}\); \(R_a\) is the forward excess beyond the horizon. The inequality bounds its expectation across all nonnegative horizons from only a first and second moment. Spouge's later original study explicitly identifies this nonnegative-iid case as the renewal form.^[3]

In sequential testing, each observation may add a log-likelihood-ratio increment. Under a hypothesis for which the score has positive mean, individual observations can still decrease it. Crossing an upper evidence threshold generates an overshoot; the positive-part moment form is appropriate to that signed walk. Lorden's 1970 abstract names sequential probability-ratio testing, and a later detailed theorem exposition derives the corresponding passage-time link. This does not mean every two-boundary test is itself the one-sided \(T(a)\); application to a full test requires the extra stopping-rule argument.^[1]^[2]

The result is useful precisely when calculating a threshold-specific overshoot distribution would be expensive or unavailable. If an application needs a precise expected residual for one known distribution, a direct renewal calculation may be more informative than a uniform ceiling.

Clarity¶

Three numbers should not be conflated: the threshold \(a\), the first-passage index \(T(a)\), and the excess \(R_a\). Raising \(a\) generally raises the expected time to crossing, but Lorden's result keeps the expected excess past the threshold bounded by the same distributional constant. Wald's relation then translates that ceiling into an upper bound on \(E[T(a)]\), under the identity's own assumptions.^[2]

The sign distinction is equally important. For renewal times \(X\geq0\), a sum can only advance. For a log-likelihood walk, evidence may move backward before later crossing. Replacing the positive-part second moment by a generic \(E[Z^2]\) in the latter case is a looser quantity and obscures the theorem's exact shape.

Manages Complexity¶

The inequality collapses a family of first-passage problems indexed by every threshold into one moment check. This is powerful for planning sequential sample sizes or bounding residual waiting time: no separate integration over each overshoot distribution is required. The cost is loss of threshold- and distribution-specific sharpness. It tells a user that the mean excess is controlled, not its exact value, variance, or tail probability.^[1]^[2]

It also exposes which assumption makes the compression possible. Without positive drift, the crossing-time behavior can change fundamentally; without a finite positive-part second moment, the stated finite constant is absent. An attractive-looking ratio should not be applied after dropping those hypotheses.

Abstract Reasoning¶

At first passage, \(S_{T(a)}=a+R_a\). Under the conditions for Wald's equation, expected stopped sum is \(mE[T(a)]\), hence \(E[T(a)]=(a+E[R_a])/m\). Lorden's uniform ceiling yields \(E[T(a)]\leq a/m+E[(Z^+)^2]/m^2\). Thus the expected sample count is its drift-based leading term plus a bounded overshoot correction. The original Caltech abstract states this route to a mean stopping-time bound; Bartroff and Tartakovsky give the exact theorem and relation.^[1]^[2]

The result is not a simple “each step is at most the constant” argument. Steps may be arbitrarily large if their positive-part second moment remains finite. Uniformity emerges after averaging and using the iid positive-drift structure.

Knowledge Transfer¶

The mathematical mapping from renewal epochs to sequential evidence is exact at the level of a first-passage random walk: increments, cumulative sum, threshold and excess each have identifiable roles. But the increment support changes. Renewal intervals cannot be negative; log-likelihood contributions can. The broader \(Z^+\) form carries across, while the renewal-only \(X^2\) shorthand should not be mistaken for the original scope.^[2]

An insurance or inventory “threshold trigger” could fit the same mathematics only if its increments are actually iid with positive drift and the crossing rule matches this one. A verbal threshold analogy is insufficient.

Examples¶

Renewal inspection horizon¶

Suppose nonnegative iid component lifetimes or interarrival times have positive finite mean and second moment. Renewal epochs are cumulative sums. At an inspection horizon \(a\), the first epoch after \(a\) exceeds it by the forward residual \(R_a\). Lorden's renewal special case says the expected excess is at most \(E[X^2]/E[X]\) at every horizon. It does not predict the exact next-failure time for a particular component.^[3]^[2]

Mapped back: lifetimes are iid positive-drift increments; the horizon is the first-passage threshold; the time from horizon to next renewal is the overshoot; the moment ratio is the uniform mean ceiling; Wald can additionally bound the expected number of intervals through the crossing when applicable.

Sequential evidence crossing¶

Under an alternative hypothesis, iid log-likelihood-ratio contributions may have positive mean even though individual contributions are negative. Their cumulative score first crossing an upper threshold is a signed-increment version of Lorden's setup. The result controls the average excess score at that passage. A complete sequential probability-ratio test has a second boundary and needs an additional argument to translate this one-sided passage bound into its total sample number.^[1]^[2]

Mapped back: log-likelihood steps are iid signed increments with positive drift under the selected hypothesis; the upper evidence level is the threshold; excess log evidence at the first crossing is \(R_a\); \(E[(Z^+)^2]/E[Z]\) is the relevant ceiling; Wald's relation concerns the one-sided crossing count under its conditions.

Pathwise-cap near miss¶

Even when the theorem applies, a single large positive jump can cross the threshold by more than the moment ratio. The result bounds the average across sample paths, not the maximum of each path. This is a negative scope check, not an extra positive application.

Structural Tensions¶

Uniform control versus sharp local estimate. The two-moment ceiling works for every threshold and avoids calculating a full overshoot law. It may be conservative for a known increment distribution and one threshold. Exact renewal analysis can be tighter but demands more distribution-specific work; insisting on exactness can be unnecessary for a safe upper bound. Diagnostic: is a guaranteed threshold-independent ceiling enough, or must the application know the actual residual expectation at a particular level?^[2]^[3]

Simple renewal intuition versus signed-walk reach. With \(X\geq0\), the overshoot is literally the residual interval after a renewal horizon and the formula \(E[X^2]/E[X]\) is memorable. Restricting the theorem to that case hides its sequential-analysis utility; using the signed form without checking positive drift and \(E[(Z^+)^2]\) risks a false application. Diagnostic: can the cumulative score step backward, and have the exact signed-increment hypotheses been verified?^[1]^[2]

Structural–Framed Character¶

This inequality lies strongly at the structural/formal end: its first-passage variable, moment assumptions and uniform bound can be checked without a social ranking of outcomes. Evaluative weight appears when a practitioner treats the ceiling as sufficiently safe or too loose for a decision. Human practice selects a renewal or testing model and decides whether observations are plausibly iid; no institution makes the inequality true by declaration. The name honors Lorden's 1970 theorem, and later expositions transmit its vocabulary, but the formula travels literally from renewal intervals to signed evidence increments only when the role map and assumptions are preserved. Importing “overshoot bound” to a different threshold process without proving those conditions is analogy, not recognition. Its character: a named, assumption-sensitive first-passage expectation theorem with a portable mathematical role map but no universal guarantee outside its probability model.

Structural Core vs. Domain Accent¶

The skeletal relation is cross a boundary for the first time, then bound expected excess independently of where the boundary was placed. That may suggest a broad threshold-control pattern. The domain-bound mechanism is essential: iid random-walk increments, positive drift, finite positive-part second moment and a specific expectation inequality. Removing those leaves only a metaphor of “not exceeding too far.” The named result does not clear the prime bar as a general abstraction because its exact ratio and proof depend on probability assumptions not shared by every overshoot or threshold. Stopping Time and Renewal Theory are live domain concepts; the former provides the stopping-rule object, the latter a special setting, but strict DAG parentage is left for review.

This entry presupposes Stopping time.

The live Stopping Time entry is a strict prerequisite under composition/presupposes: first threshold passage fixes the nonanticipating random index whose overshoot the inequality bounds. The theorem is not a subtype of a stopping rule. Renewal Theory supplies the nonnegative-increment application, not the full signed theorem's parent; Overshoot and Collapse is a conceptual neighbor, not this quantitative bound.

Relationships to Other Abstractions¶

Current abstraction Lorden's Inequality Domain-specific

Parents (1) — more general patterns this builds on

Lorden's Inequality presupposes Stopping time Domain-specific

Lorden's overshoot inequality requires a nonanticipating first-passage stopping time.

Hierarchy path (1) — routes to 1 parentless root

Lorden's Inequality → Stopping time → Threshold

Neighborhood in Abstraction Space¶

Lorden's Inequality sits in a sparse region of the domain-specific corpus (65^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Foundations of Probability & Inference (29 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Wald's equation: converts an expected stopped sum into an expected stopping count under separate conditions. Renewal residual-life formulas: can give distribution-specific or limiting values; Lorden supplies a uniform bound. Tail or almost-sure bounds: stronger/different claims not entailed by a mean inequality. Nonidentically distributed overshoot bounds: later extensions requiring their own hypotheses. Convective or control-system overshoot: same English word, different state variables.^[1]^[2]^[3]

References¶

[1] Gary Lorden, On Excess over the Boundary, Annals of Mathematical Statistics 41 (1970), Caltech original-paper archive and abstract; archive PDF text was not retrievable here. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[2] Bartroff and Tartakovsky, Beyond Boundaries: Gary Lorden's Groundbreaking Contributions to Sequential Analysis, §2.2 Theorem 2.3 and equations 2.24–2.25, author-hosted scholarly exposition. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[3] John L. Spouge, Inequalities on the Overshoot beyond a Boundary for Independent Summands with Differing Distributions, original research introduction comparing renewal and later extensions. registry ↩a ↩b ↩c ↩d ↩e ↩f