Lindley equation

The reflected random-walk recursion W_(n+1)=max(0,W_n+X_n), canonically describing successive waiting times in a single-server queue.

Version

v2 · 2026-09-19 · History

Domain-specific #

5331

Domain group

Formal Sciences

Origin domain

Operations Research

Subdomains

Queueing Theory, Waiting Time Recursions → Operations Research

Core Idea

The Lindley equation recursively updates a workload or waiting time by adding an increment and truncating negative values at zero. Unfinished work carries forward, new net input changes the workload, and an idle server reflects the process at zero rather than permitting negative waiting time. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

The load-bearing residual is not the broad topic of queueing theory. It is one-sided reflected random walk modeling queue workload. That residual remains recognizable when examples, notation, scale, or implementation change, but it disappears if the carrier is mistyped, the condition that the next state is exactly the positive part of current state plus the declared increment, with dependence and stationarity assumptions stated separately fails, a neighboring object is substituted, or notation and topical resemblance replace the constitutive test.

How would you explain it like I'm…

Never-Below-Zero Line

Think of a pile of chores waiting for one helper. Each turn, new chores get added and the helper finishes some. If the helper finishes everything, the pile is just empty; it can never be less than empty. The Lindley equation is the rule for figuring out the next pile size.

Waiting Line Update Rule

The Lindley equation is a rule for tracking how much waiting or unfinished work a queue has. You take the current amount of work, add new work that arrives, and subtract the work that gets done. If that number would go below zero, you just set it to zero, because a server with nothing to do can't have negative work. Doing this step after step shows how the line grows and shrinks over time.

Reflected Workload Recursion

The Lindley equation is a rule for updating the waiting time or workload in a queue: W_next = max(0, W + X), where X is the net change (new work arriving minus work served). Unfinished work carries over, and the 'max with zero' means that when the server runs out of work it sits idle instead of the wait going negative. Mathematically this is a random walk that is 'reflected' at zero—it can bounce off the floor but never go below it. Assumptions about whether the increments are independent or stable over time are stated separately from the rule itself. That separation matters: the equation is exactly this positive-part update, not general queueing theory.

 

The Lindley equation is the recursion W_{n+1} = max(0, W_n + X_n), where W_n is the workload or waiting time and X_n is a declared increment, such as the next service time minus the next interarrival time. Unfinished work carries forward, net input changes it, and truncation at zero represents an idle server rather than allowing negative waiting. Structurally, the waiting-time process is a one-sided random walk reflected at zero. Its defining condition is exactly that the next state is the positive part of current state plus increment. Assumptions about dependence and stationarity of the increments are separate and must be stated explicitly; they determine what can be derived, such as long-run behavior. This distinguishes the Lindley equation from queueing theory in general: it is a specific reflected recursion.

Scope of Application

Lindley equation belongs to queueing theory and is useful where the analyst can specify a nonnegative state W_n, increments from service and interarrival times or a general sequence X_n, discrete steps, reflection at zero and stability or stationary-distribution conditions, then evaluate the next state is exactly the positive part of current state plus the declared increment, with dependence and stationarity assumptions stated separately. The scope is broad within that domain but bounded by the need for the next state is exactly the positive part of current state plus the declared increment, with dependence and stationarity assumptions stated separately. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity

The abstraction clarifies a crowded vocabulary by making the next state is exactly the positive part of current state plus the declared increment, with dependence and stationarity assumptions stated separately the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Lindley equation can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Lindley equation. Lindley equation compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning

1. Identify the carrier. State what the elements, states, objects, or observations are: a nonnegative state W_n, increments from service and interarrival times or a general sequence X_n, discrete steps, reflection at zero and stability or stationary-distribution conditions. Reject examples whose alleged carrier belongs to a different problem.
2. Lock the constitutive rule. Express the next state is exactly the positive part of current state plus the declared increment, with dependence and stationarity assumptions stated separately independently of one notation or implementation.

Knowledge Transfer

Knowledge transfers strongly among subfields of queueing theory because they reuse a nonnegative state W_n, increments from service and interarrival times or a general sequence X_n, discrete steps, reflection at zero and stability or stationary-distribution conditions, Unfinished work carries forward, new net input changes the workload, and an idle server reflects the process at zero rather than permitting negative waiting time., and type the carrier, state every parameter and convention in the definition, test that the next state is exactly the positive part of current state plus the declared increment, with dependence and stationarity assumptions stated separately, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions

Current abstraction Lindley equation Domain-specific

Parents (1) — outgoing typed relations

• Lindley equation is a kind of Recursion Prime

  Each waiting state is generated recursively from the prior state and a reflected increment.

Hierarchy path (1) — routes to 1 parentless root

• Lindley equation → is a kind of Recursion

Neighborhood in Abstraction Space

Lindley equation sits in a moderately populated region (48^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Stochastic Processes & Markov Dynamics (29 abstractions)

Nearest neighbors

• Polling system — 0.88
• Running total — 0.86
• Asymmetric simple exclusion process — 0.86
• Asymptotic analysis — 0.85
• Quality of service — 0.85

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