How does renewal theory generalise the Poisson process?

It replaces the exponential interarrival times of the Poisson process with arbitrary independent identically distributed times, so the process retains the renewal structure but loses the memoryless property.

What is Little's law?

It states that the average number of customers in a stable system equals the arrival rate times the average time a customer spends there, independent of the arrival or service distributions.

Renewal and Queueing Theory

Renewal theory analyses processes that probabilistically restart at recurrence epochs, and queueing theory applies it to systems where customers arrive, wait, and are served.

Definition

Renewal theory studies counting processes whose interarrival times are independent and identically distributed, generalising the Poisson process, while queueing theory models service systems by combining arrival and service processes to study waiting times, queue lengths, and utilisation.

Scope

This area covers renewal processes and the renewal function, the elementary and key renewal theorems, regenerative processes and the renewal-reward framework, the structure and equilibrium of Markovian queues such as M/M/1 and M/M/c, Little's law relating average numbers and waiting times, and networks of interacting queues with product-form solutions.

Sub-topics

Core questions

How does generalising exponential interarrival times to arbitrary distributions extend the Poisson process?
What do the renewal theorems say about long-run rates and asymptotic behaviour?
How are average queue length and waiting time related in equilibrium?
When do networks of queues admit tractable product-form solutions?

Key theories

Renewal theorems and renewal-reward: The elementary and key renewal theorems give the long-run rate of renewals and the limiting behaviour of solutions to the renewal equation, and the renewal-reward theorem expresses long-run average reward as expected reward per cycle divided by expected cycle length.
Little's law: In any stable queueing system the long-run average number of customers present equals the arrival rate times the average time each customer spends in the system, a distribution-free identity relating throughput, occupancy, and delay.

Clinical relevance

Renewal and queueing theory underpin the design and analysis of telephone and data networks, call centres, manufacturing lines, computer systems, transportation, and healthcare service capacity, quantifying delays, throughput, and resource utilisation in systems with random demand.

History

Erlang founded queueing theory between 1909 and 1920 with his telephone-traffic formulas, renewal theory was developed by Feller, Smith, and Cox in the 1940s and 1950s, and Little's 1961 proof of the queue-length identity and Jackson's network results of 1957 extended the theory to complex service systems.

Key figures

Agner Krarup Erlang
William Feller
David Cox
John Little

Seminal works

asmussen2003

Frequently asked questions

How does renewal theory generalise the Poisson process?: It replaces the exponential interarrival times of the Poisson process with arbitrary independent identically distributed times, so the process retains the renewal structure but loses the memoryless property.
What is Little's law?: It states that the average number of customers in a stable system equals the arrival rate times the average time a customer spends there, independent of the arrival or service distributions.