- 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.
In Dennis Lindley's first paper on the subject 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)
- Tn is the time between the nth and (n+1)th arrivals,
- Sn is the service time of the nth customer, and
- Un = Sn − Tn
- Wn is the waiting time of the nth customer.
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.
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.
- Asmussen, Søren (2003). Applied probability and queues. Springer. p. 23. doi:10.1007/0-387-21525-5_1. ISBN 0-387-00211-1.
- Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems. 63: 3–4. doi:10.1007/s11134-009-9147-4.
- Kendall, D. G. (1951). "Some problems in the theory of queues". Journal of the Royal Statistical Society, Series B. 13: 151–185. JSTOR 2984059. MR MR47944.
- Lindley, D. V. (1952). "The theory of queues with a single server". Mathematical Proceedings of the Cambridge Philosophical Society. 48 (2): 277–289. doi:10.1017/S0305004100027638. MR 0046597.
- Prabhu, N. U. (1974). "Wiener-Hopf Techniques in Queueing Theory". Mathematical Methods in Queueing Theory. Lecture Notes in Economics and Mathematical Systems. 98. pp. 81–90. doi:10.1007/978-3-642-80838-8_5. ISBN 978-3-540-06763-4.