Lindley equation
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]
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.
- Wn + 1 = max(0,Wn + Un)
where
- 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.
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.
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]
Notes
- ^ 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 0047944.
- ^ 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. Vol. 98. pp. 81–90. doi:10.1007/978-3-642-80838-8_5. ISBN 978-3-540-06763-4.
- v
- t
- e
- D/M/1 queue
- M/D/1 queue
- M/D/c queue
- M/M/1 queue
- Burke's theorem
- M/M/c queue
- M/M/∞ queue
- M/G/1 queue
- M/G/k queue
- G/M/1 queue
- G/G/1 queue
- Kingman's formula
- Lindley equation
- Fork–join queue
- Bulk queue
- Data buffer
- Erlang (unit)
- Erlang distribution
- Flow control (data)
- Message queue
- Network congestion
- Network scheduler
- Pipeline (software)
- Quality of service
- Scheduling (computing)
- Teletraffic engineering
![](http://upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/16px-Symbol_category_class.svg.png)