Lindley equation

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

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]

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 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.

Queueing theory

Single queueing nodes	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 Pollaczek–Khinchine formula Matrix analytic method M/G/k queue G/M/1 queue G/G/1 queue Kingman's formula Lindley equation Fork–join queue Bulk queue

Arrival processes	Poisson process Markovian arrival process Rational arrival process

Queueing networks	Jackson network Traffic equations Gordon–Newell theorem Mean value analysis Buzen's algorithm Kelly network G-network BCMP network

Service policies	FIFO LIFO Processor sharing Round-robin Shortest job first Shortest remaining time

Key concepts	Continuous-time Markov chain Kendall's notation Little's law Product-form solution Balance equation Quasireversibility Flow-equivalent server method Arrival theorem Decomposition method Beneš method

Limit theorems	Fluid limit Mean field theory Heavy traffic approximation Reflected Brownian motion

Extensions	Fluid queue Layered queueing network Polling system Adversarial queueing network Loss network Retrial queue

Information systems	Data buffer Erlang (unit) Erlang distribution Flow control (data) Message queue Network congestion Network scheduler Pipeline (software) Quality of service Scheduling (computing) Teletraffic engineering

Category

This article is issued from Wikipedia - version of the 8/29/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.