Lindley equation

In probability theory, the Lindley equation, Lindley recursion or Lindley process^[1] is a discrete-time stochastic process A_n where n takes integer values and:

A_n + 1 = max(0, A_n + B_n).

Processes of this form can be used to describe the waiting time of customers in a queue or evolution of a queue length over time. The idea was first proposed in the discussion following Kendall's 1951 paper.^[2][3]

Waiting times

In Dennis Lindley's first paper on the subject^[4] the equation is used to describe waiting times experienced by customers in a queue with the First-In First-Out (FIFO) discipline.

W_n + 1 = max(0,W_n + U_n)

where

• T_n is the time between the nth and (n+1)th arrivals,
• S_n is the service time of the nth customer, and
• U_n = S_n − T_n
• W_n is the waiting time of the nth customer.

The first customer does not need to wait so W₁ = 0. Subsequent customers will have to wait if they arrive at a time before the previous customer has been served.

Queue lengths

The evolution of the queue length process can also be written in the form of a Lindley equation.

Integral equation

Lindley's integral equation is a relationship satisfied by the stationary waiting time distribution F(x) in a G/G/1 queue.

${\displaystyle F(x)=\int _{0^{-}}^{\infty }K(x-y)F({\text{d}}y)\quad x\geq 0}$

Where K(x) is the distribution function of the random variable denoting the difference between the (k - 1)th customer's arrival and the inter-arrival time between (k - 1)th and kth customers. The Wiener–Hopf method can be used to solve this expression.^[5]