In probability theory, the Lindley equation, Lindley recursion or Lindley process[1] is a discrete-time stochastic process An where n takes integer values and:
An + 1 = max(0, An + Bn).
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]
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.
Wn + 1 = max(0,Wn + Un)where
The first customer does not need to wait so W1 = 0. Subsequent customers will have to wait if they arrive at a time before the previous customer has been served.
The evolution of the queue length process can also be written in the form of a Lindley equation.
Lindley's integral equation is a relationship satisfied by the stationary waiting time distribution F(x) in a G/G/1 queue.
F(x)=
| infty | |
| \int | |
| 0- |
K(x-y)F(dy) x\geq0
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]