Lindley equation

In probability theory, the Lindley equation, Lindley recursion or Lindley processes[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]

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.

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.

Queue lengths

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

Notes

  1. ^ Asmussen, Søren (2003). Applied probability and queues. Springer. p. 23. ISBN 0387002111. 
  2. ^ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems 63: 3–4. doi:10.1007/s11134-009-9147-4.  edit
  3. ^ Kendall, D. G. (1951). "Some problems in the theory of queues". J. R. Statist. Soc. Ser. B 13: 151–185. JSTOR 2984059. MRMR47944. 
  4. ^ 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. MR0046597.