GRENOUILLE

2013-06-21T21:03:19Z

198.129.37.70: /* Theory */

In [[probability theory]], the '''Lindley equation''', '''Lindley recursion''' or '''Lindley processes'''<ref name="asmussen">{{cite book|title=Applied probability and queues|first=Søren|last=Asmussen|publisher=Springer|year=2003|isbn=0-387-00211-1|page=23|doi=10.1007/0-387-21525-5_1}}</ref> 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 [[queueing theory|queue]] or evolution of a queue length over time. The idea was first proposed in the discussion following [[David George Kendall|Kendall]]'s 1951 paper.<ref>{{cite doi|10.1007/s11134-009-9147-4}}</ref><ref>{{cite journal|last=Kendall|first=D. G.|authorlink=David George Kendall|year=1951|title=Some problems in the theory of queues|journal=Journal of the Royal Statistical Society, Series B|volume=13|pages=151–185|mr=MR47944|jstor=2984059}}</ref>

==Waiting times==
In [[Dennis Lindley]]'s first paper on the subject<ref>{{cite journal | last = Lindley | first = D. V. | author-link = Dennis Lindley | doi = 10.1017/S0305004100027638 | mr = 0046597 | issue = 2 | journal = Mathematical Proceedings of the Cambridge Philosophical Society | pages = 277–289 | title = The theory of queues with a single server | volume = 48 | year = 1952}}</ref> 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 ''n''th and (''n''+1)th arrivals,
* ''S''''n'' is the service time of the ''n''th customer, and
* ''U''''n'' = ''S''''n'' − ''T''''n''
* ''W''''n'' is the waiting time of the ''n''th customer.

The first customer does not need to wait so ''W''1 = 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]].

::<math>F(x) = \int_{0^-}^\infty K(x-y)F(\text{d}y) \quad x \geq 0</math>

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 ''k''th customers. The [[Wiener–Hopf method]] can be used to solve this expression.<ref>{{cite doi|10.1007/978-3-642-80838-8_5}}</ref>

==Notes==
{{Reflist}}

{{Queueing theory}}

{{DEFAULTSORT:Lindley equation}}
[[Category:Queueing theory]]

{{mathapplied-stub}}

formulasearchengine - User contributions [en]

GRENOUILLE