Lindley’s Recursion and the G/G/1 Queue

Lindley’s recursion gives a useful formula relating waiting times in a queue to general inter-arrival and service times.

Consider a FIFO single-server queue. We define:

  • \tau_n as the inter-arrival time between the nth and (n+1)th arrivals;
  • \sigma_n as the service time of the nth arrival;
  • W_n as the waiting time of the nth arrival; and
  • S_n:=\sum_{j=0}^n(\sigma_j-\tau_j), with S_{-1}:=0.

Lindley’s Recursion

The waiting time of the (n+1)th arrival satisfies

\displaystyle W_{n+1}=\max\{0,W_n+\sigma_n-\tau_n\}.

If W_0=0, then

\displaystyle W_{n+1}=S_n-\min_{-1\leq j\leq n}S_j=S_n-\min\{0,S_0,\ldots,S_n\}.

The process S_n is a random walk. Lindley’s recursion therefore allows us to convert questions about the G/G/1 queue into questions about a random walk and its running minimum.

Lindley’s recursion. Whenever the random walk attempts to become negative, it is pushed back to zero. Equivalently, the process is reflected at zero so that it remains non-negative.

Proof

Immediately after the nth job arrives, the workload is W_n+\sigma_n. During the following inter-arrival time, the server can process \tau_n units of work. If the queue does not empty before the next arrival, then

\displaystyle W_{n+1}=W_n+\sigma_n-\tau_n.

If the queue empties, then W_n+\sigma_n-\tau_n<0 and the next arrival finds an empty queue, so W_{n+1}=0. Combining the two cases gives

\displaystyle W_{n+1}=\max\{0,W_n+\sigma_n-\tau_n\}.

Lindley’s recursion when the queue remains busy and when the queue empties.

For the second statement, iterate the recursion backwards from W_0=0:

\displaystyle \begin{aligned}W_{n+1}&=\max\{0,W_n+\sigma_n-\tau_n\}\\&=\max\{0,\sigma_n-\tau_n,\sigma_n-\tau_n+\sigma_{n-1}-\tau_{n-1},\ldots,\sum_{j=0}^n(\sigma_j-\tau_j)\}\\&=\max\{S_n-S_n,S_n-S_{n-1},\ldots,S_n-S_{-1}\}\\&=S_n-\min_{-1\leq j\leq n}S_j.\end{aligned}

This proves the result.

□

 

Leave a comment